Ron Rivest, Adi Shamir, and Leonard Adleman developed RSA in 1977 [RSA]1.8. Two excellent expository accounts can be found in Cosgrave [Co] and Wardlaw [Wa].
In this section, we assume that you have somehow translated the message you wish to send into an integer (i.e., a finite sequence of digits which does not start with a 0 ).
RSA works as follows: Take two large primes, and , and compute their product . In practice, one chooses both and to have at least 100 digits and are kept secret (the sender of the message). Because factoring very large integers seems to be such a very hard problem, it is widely believed that such a choice of will make it practically impossible to determine given . Choose an integer with and . Find the multiplicative inverse of modulo , call it . The values and are called the public and private exponents, respectively. The public key is the pair . The private key is .
Suppose Alice wants to send a message to Bob. We assume in this section that . We also assume that Alice and Bob have found a way to secretly share the private key .
step 1: Alice creates the enciphered message (``ciphertext'') by exponentiating the message: , where and are Bob's public key. In other words, in the notation of (1.4) the encryption map is .
step 2: She sends to Bob.
step 3: To decrypt, Bob also exponentiates: . The relationship between and (namely, ) ensures that Bob correctly recovers . Since is kept secret, no one else can (easily) decrypt this message without knowing (or , from which one can determine ).