## Application: RSA encryption

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 ).

Example 1.8.12   Let , , so . Let (the public exponent), so (the private exponent). Let be the message. The cipher text'' is since .

Example 1.8.13   Let , , so . Let (the public exponent), so (the private exponent). Let be the message. The cipher text'' is since .

Subsections

david joyner 2008-04-20