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