If traditional cryptosystems are used, anyone who knows enough to encode a message will also know enough to decode an intercepted message. In 1976, W. Diffie and M. Hellman proposed public key cryptography, which is based on the observation that the encryption and decryption procedures need not have the same key. This removes the requirement that the encoding key be kept secret. The encoding function $f$ must be relatively easy to compute, but $f^{-1}$ must be extremely difficult to compute without some additional information, so that someone who knows only the encrypting key cannot find the decrypting key without prohibitive computation. It is interesting to note that to date, no system has been proposed that has been proven to be “one-way;” that is, for any existing public key cryptosystem, it has never been shown to be computationally prohibitive to decode messages with only knowledge of the encoding key.

The RSA cryptosystem introduced by R. Rivest, A. Shamir, and L. Adleman in 1978, is based on the difficulty of factoring large numbers. Though it is not a difficult task to find two large random primes and multiply them together, factoring a 150-digit number that is the product of two large primes would take 100 million computers operating at 10 million instructions per second about 50 million years under the fastest algorithms available in the early 1990s. Although the algorithms have improved, factoring a number that is a product of two large primes is still computationally prohibative.

The RSA cryptosystem works as follows. Suppose that we choose two random 150-digit prime numbers $p$ and $q$. Next, we compute the product $n= pq$ and also compute $\phi(n) = m = (p - 1)(q-1)$, where $\phi$ is the Euler $\phi$-function. Now we start choosing random integers $E$ until we find one that is relatively prime to $m$; that is, we choose $E$ such that $\gcd(E, m) = 1$. Using the Euclidean algorithm, we can find a number $D$ such that $DE \equiv 1 \pmod{m}$. The numbers $n$ and $E$ are now made public.

Suppose now that person B (Bob) wishes to send person A (Alice) a message over a public line. Since $E$ and $n$ are known to everyone, anyone can encode messages. Bob first digitizes the message according to some scheme, say $\mbox{A} = 00, \mbox{B} = 02, \ldots, \mbox{Z}= 25$. If necessary, he will break the message into pieces such that each piece is a positive integer less than $n$. Suppose $x$ is one of the pieces. Bob forms the number $y = x^E \mod n$ and sends $y$ to Alice. For Alice to recover $x$, she need only compute $x = y^D \bmod n$. Only Alice knows $D$.

##### Example7.5

Before exploring the theory behind the RSA cryptosystem or attempting to use large integers, we will use some small integers just to see that the system does indeed work. Suppose that we wish to send some message, which when digitized is 25. Let $p = 23$ and $q = 29$. Then \begin{equation*}n = pq = 667\end{equation*} and \begin{equation*}\phi(n) = m = (p - 1)(q - 1) = 616.\end{equation*} We can let $E = 487$, since $\gcd(616, 487) = 1$. The encoded message is computed to be \begin{equation*}25^{487} \bmod 667 = 169.\end{equation*} This computation can be reasonably done by using the method of repeated squares as described in Chapter 4. Using the Euclidean algorithm, we determine that $191 E = 1 + 151 m$; therefore, the decrypting key is $(n, D) = ( 667, 191)$. We can recover the original message by calculating \begin{equation*}169^{191} \bmod 667 = 25.\end{equation*}

Now let us examine why the RSA cryptosystem works. We know that $DE \equiv 1 \pmod{ m}$; hence, there exists a $k$ such that \begin{equation*}DE = km + 1 = k \phi(n) + 1.\end{equation*} There are two cases to consider. In the first case assume that $\gcd(x, n) = 1$. Then by Theorem 6.18, \begin{equation*}y^D = (x^E)^D = x^{DE} = x^{km + 1} = (x^{\phi(n)})^k x = (1)^k x = x \bmod n.\end{equation*} So we see that Alice recovers the original message $x$ when she computes $y^D \bmod n$.

For the other case, assume that $\gcd(x, n) \neq 1$. Since $n = pq$ and $x \lt n$, we know $x$ is a multiple of $p$ or a multiple of $q$, but not both. We will describe the first possibility only, since the second is entirely similar. There is then an integer $r$, with $r \lt q$ and $x = rp$. Note that we have $\gcd(x, q) = 1$ and that $m=\phi(n)=(p - 1)(q - 1)=\phi(p)\phi(q)$. Then, using Theorem 6.18, but now mod $q$, \begin{equation*}x^{km} = x^{k\phi(p)\phi(q)} = (x^{\phi(q)})^{k\phi(p)} = (1)^{k\phi(p)} = 1 \bmod q.\end{equation*} So there is an integer $t$ such that $x^{km}=1 + tq$. Thus, Alice also recovers the message in this case, \begin{equation*}y^D = x^{km + 1} = x^{km} x = (1 + tq) x = x + tq(rp) = x + trn = x \bmod n.\end{equation*}

We can now ask how one would go about breaking the RSA cryptosystem. To find $D$ given $n$ and $E$, we simply need to factor $n$ and solve for $D$ by using the Euclidean algorithm. If we had known that $667 = 23 \cdot 29$ in Example 7.5, we could have recovered $D$.

There is a problem of message verification in public key cryptosystems. Since the encoding key is public knowledge, anyone has the ability to send an encoded message. If Alice receives a message from Bob, she would like to be able to verify that it was Bob who actually sent the message. Suppose that Bob's encrypting key is $(n', E')$ and his decrypting key is $(n', D')$. Also, suppose that Alice's encrypting key is $(n, E)$ and her decrypting key is $(n, D)$. Since encryption keys are public information, they can exchange coded messages at their convenience. Bob wishes to assure Alice that the message he is sending is authentic. Before Bob sends the message $x$ to Alice, he decrypts $x$ with his own key: \begin{equation*}x' = x ^{D'} \bmod n'.\end{equation*} Anyone can change $x'$ back to $x$ just by encryption, but only Bob has the ability to form $x'$. Now Bob encrypts $x'$ with Alice's encryption key to form \begin{equation*}y' = {x'}^E \bmod n,\end{equation*} a message that only Alice can decode. Alice decodes the message and then encodes the result with Bob's key to read the original message, a message that could have only been sent by Bob.