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, $p$ and $q$ , and compute their product $n = pq$ . In practice, one chooses both $p$ and $q$ to have at least 100 digits and $p,q$ 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 $p,q$ will make it practically impossible to determine $p,q$ given $n$ . Choose an integer $e$ with $0<e<n$ and $gcd(e,(p-1)(q-1))=1$ . Find the multiplicative inverse of $e$ modulo $(p-1)(q-1)$ , call it $d$ . The values $e$ and $d$ are called the public and private exponents, respectively. The public key is the pair $(n, e)$ . The private key is $(n, d)$ .

Suppose Alice wants to send a message $m$ to Bob. We assume in this section that $gcd(m,n)=1$ . We also assume that Alice and Bob have found a way to secretly share the private key $(n, d)$ .

step 1: Alice creates the enciphered message (``ciphertext'') $c$ by exponentiating the message: $c \equiv m^e ({\rm mod} n)$ , where $e$ and $n$ are Bob's public key. In other words, in the notation of (1.4) the encryption map is $E(m)=m^e ({\rm mod} n)$ .

step 2: She sends $c$ to Bob.

step 3: To decrypt, Bob also exponentiates: $m \equiv c^d ({\rm mod} n)$ . The relationship between $e$ and $d$ (namely, $de \equiv 1 ({\rm mod} (p-1)(q-1))$ ) ensures that Bob correctly recovers $m$ . Since $d$ is kept secret, no one else can (easily) decrypt this message without knowing $d$ (or $p,q$ , from which one can determine $d$ ).

Example 1.8.12   Let $p=3$ , $q=7$ , so $\phi(n)=\phi(21)=12$ . Let $e=11$ (the public exponent), so $d=11$ (the private exponent). Let $m=10$ be the message. The ``cipher text'' is $c=19$ since $m^e=10^{11} \equiv 19 ({\rm mod} 21)$ .

Example 1.8.13   Let $p=17$ , $q=19$ , so $\phi(n)=\phi(323)=288$ . Let $e=97$ (the public exponent), so $d=193$ (the private exponent). Let $m=100$ be the message. The ``cipher text'' is $c=168$ since $m^e=100^{97} \equiv 168 ({\rm mod} 323)$ .