Alice wants to send a message to Bob, but they have not had previous contact and they do not want to take the time to send a courier with a key. Therefore, all information that Alice sends to Bob will potentially be obtained by the evil observer Eve. However, it is still possible for a message to be sent in such a way that Bob can read it but Eve cannot.

With all the previously discussed methods, this would be impossible. Alice would have to send a key, which Eve would intercept. She could then decrypt all subsequent messages. The possibility of the present scheme, called a public key cryptosystem, was first publicly suggested by Diffie and Hellman in their classic 1976 paper [Diffie-Hellman]. However, they did not yet have a practical implementation (although they did present an alternative key exchange procedure that works over public channels; see Section 10.4). In the next few years, several methods were proposed. The most successful, based on the idea that factorization of integers into their prime factors is hard, was proposed by Rivest, Shamir, and Adleman in 1977 and is known as the RSA algorithm.

It had long been claimed that government cryptographic agencies had discovered the RSA algorithm several years earlier, but secrecy rules prevented them from releasing any evidence. Finally, in 1997, documents released by CESG, a British cryptographic agency, showed that in 1970, James Ellis had discovered public key cryptography, and in 1973, Clifford Cocks had written an internal document describing a version of the RSA algorithm in which the encryption exponent $e$ (see the discussion that follows) was the same as the modulus $n$.

Here is how the RSA algorithm works. Bob chooses two distinct large primes $p$ and $q$ and multiplies them together to form

He also chooses an encryption exponent $e$ such that

He sends the pair $(n\text{,}e)$ to Alice but keeps the values of $p$ and $q$ secret. In particular, Alice, who could possibly be an enemy of Bob, never needs to know $p$ and $q$ to send her message to Bob securely. Alice writes her message as a number $m$. If $m$ is larger than $n$, she breaks the message into blocks, each of which is less than $n$. However, for simplicity, let’s assume for the moment that $m\text{ < }n$. Alice computes

and sends $c$ to Bob. Since Bob knows $p$ and $q$, he can compute $(p-1)(q-1)$ and therefore can find the decryption exponent $d$ with

As we’ll see later,

so Bob can read the message.

We summarize the algorithm in the following table.

For more examples, see Examples 24–30 in the Computer Appendices.

There are several aspects that need to be explained, but perhaps the most important is why $m\equiv c^d(\text{mod}n)$. Recall Euler’s theorem (Section 3.6): If $gcd(a\text{,}n)=1$, then $a^{\varphi (n)}\equiv 1(\text{mod}n)$. In our case, $\varphi (n)=\varphi (pq)=(p-1)(q-1)$. Suppose $gcd(m\text{,}n)=1$. This is very likely the case; since $p$ and $q$ are large, $m$ probably has neither as a factor. Since $de\equiv 1(\text{mod}\varphi (n))$, we can write $de=1+k\varphi (n)$ for some integer $k$. Therefore,

We have shown that Bob can recover the message. If $gcd(m\text{,}n)\ne 1$, Bob still recovers the message. See Exercise 37.

What does Eve do? She intercepts $n\text{,}e\text{,}c$. She does not know $p\text{,}q\text{,}d$. We assume that Eve has no way of factoring $n$. The obvious way of computing $d$ requires knowing $\varphi (n)$. We show later that this is equivalent to knowing $p$ and $q$. Is there another way? We will show that if Eve can find $d$, then she can probably factor $n$. Therefore, it is unlikely that Eve finds the decryption exponent $d$.

Since Eve knows $c\equiv m^e(\text{mod}n)$, why doesn’t she simply take the $e$th root of $c$? This works well if we are not working mod $n$ but is very difficult in our case. For example, if you know that $m^3\equiv 3(\text{mod}85)$, you cannot calculate the cube root of 3, namely $1.4422\dots \text{ ,}$ on your calculator and then reduce mod 85. Of course, a case-by-case search would eventually yield $m=7$, but this method is not feasible for large $n$.

How does Bob choose $p$ and $q$? They should be chosen at random, independently of each other. How large depends on the level of security needed, but it seems that they should have at least 300 digits. For reasons that we discuss later, it is perhaps best if they are of slightly different lengths. When we discuss primality testing, we’ll see that finding such primes can be done fairly quickly (see also Section 3.6). A few other tests should be done on $p$ and $q$ to make sure they are not bad. For example, if $p-1$ has only small prime factors, then $n$ is easy to factor by the $p-1$ method (see Section 9.3), so $p$ should be rejected and replaced with another prime.

Why does Bob require $gcd(e\text{,}(p-1)(q-1))=1$? Recall (see Section 3.3) that $de\equiv 1(\text{mod}(p-1)(q-1))$ has a solution $d$ if and only if $gcd(e\text{,}(p-1)(q-1))=1$. Therefore, this condition is needed in order for $d$ to exist. The extended Euclidean algorithm can be used to compute $d$ quickly. Since $p-1$ is even, $e=2$ cannot be used; one might be tempted to use $e=3$. However, there are dangers in using small values of $e$ (see Section 9.2, Computer Problem 14, and Section 23.3), so something larger is usually recommended. Also, if $e$ is a moderately large prime, then there is no difficulty ensuring that $gcd(e\text{,}(p-1)(q-1))=1$. It is now generally recommended that $e\ge 65537$. Among the data collected for [Lenstra2012 et al.] is the distribution of RSA encryption exponents that is given in Table 9.1.

Table 9.1 RSA Encryption Exponents

In the encryption process, Alice calculates $m^e(\text{mod}n)$. Recall that this can be done fairly quickly and without large memory, for example, by successive squaring. See Section 3.5. This is definitely an advantage of modular arithmetic: If Alice tried to calculate $m^e$ first, then reduce mod $n$, it is possible that recording $m^e$ would overflow her computer’s memory. Similarly, the decryption process of calculating $c^d(\text{mod}n)$ can be done efficiently. Therefore, all the operations needed for encryption and decryption can be done quickly (i.e., in time a power of $logn$). The security is provided by the assumption that $n$ cannot be factored.

We made two claims. We justify them here. Recall that the point of these two claims was that finding $\varphi (n)$ or finding the decryption exponent $d$ is essentially as hard as factoring $n$. Therefore, if factoring is hard, then there should be no fast, clever way of finding $d$.

Claim 1: Suppose $n=pq$ is the product of two distinct primes. If we know $n$ and $\varphi (n)$, then we can quickly find $p$ and $q$.

Note that

Therefore, we know $pq$ and $p+q$. The roots of the polynomial

are $p$ and $q$, but they can also be calculated by the quadratic formula:

This yields $p$ and $q$.

For example, suppose $n=221$ and we know that $\varphi (n)=192$. Consider the quadratic equation

The roots are

For another example, see Example 31 in the Computer Appendices.

Claim 2: If we know $d$ and $e$, then we can probably factor $n$.

In the discussion of factorization methods in Section 9.4, we show that if we have an exponent $r>0$ such that $a^r\equiv 1(\text{mod}n)$ for several $a$ with $gcd(a\text{,}n)=1$, then we can probably factor $n$. Since $de-1$ is a multiple of $\varphi (n)$, say $de-1=k\varphi (n)$, we have

whenever $gcd(a\text{,}n)=1$. The $a^r\equiv 1$ factorization method can now be applied.

For an example, see Example 32 in the Computer Appendices.

Claim 2’: If $e$ is small or medium-sized (for example, if $e$ has several fewer digits than $\sqrt{n}$) and we know $d$, then we can factor $n$.

We use the following procedure:

1. Compute $k=\lceil (de-1)/n\rceil$ (that is, round up to the nearest integer).

2. Compute

   $$\varphi (n)={\displaystyle \frac{de-1}{k}}\text{.}$$

3. Solve the quadratic equation

   $$X^2-(n+1-\varphi (n))X+n=0.$$

   The solutions are $p$ and $q$.

Why does this work? We know that $de\equiv 1(\text{mod}(p-1)(q-1))$, so we write $de=1+(p-1)(q-1)k$. Since $d<(p-1)(q-1)$, we know that

so $k<e$. We have

Usually, both $p$ and $q$ are approximately $\sqrt{n}$. In practice, $e$ and therefore $k$ (which is less than $e$) are much smaller than $\sqrt{n}$. Therefore, $(p+q-1)k$ is much smaller than $n$, which means that $(p+q-1)k/n<1$ and it rounds off to $0$.

Once we have $k$, we use $de-1=\varphi (n)k$ to solve for $\varphi (n)$. As we have already seen, once we know $n$ and $\varphi (n)$, we can find $p$ and $q$ by solving the quadratic equation.

One way the RSA algorithm can be used is when there are several banks, for example, that want to be able to send financial data to each other. If there are several thousand banks, then it is impractical for each pair of banks to have a key for secret communication. A better way is the following. Each bank chooses integers $n$ and $e$ as before. These are then published in a public book. Suppose bank A wants to send data to bank B. Then A looks up B’s $n$ and $e$ and uses them to send the message. In practice, the RSA algorithm is not quite fast enough for sending massive amounts of data. Therefore, the RSA algorithm is often used to send a key for a faster encryption method such as AES.

PGP (= Pretty Good Privacy) used to be a standard method for encrypting email. When Alice sends an email message to Bob, she first signs the message using a digital signature algorithm such as those discussed in Chapter 13. She then encrypts the message using a block cipher such as triple DES or AES (other choices are IDEA or CAST-128) with a randomly chosen 128-bit key (a new random key is chosen for each transmission). She then encrypts this key using Bob’s public RSA key (other public key methods can also be used). When Bob receives the email, he uses his private RSA exponent to decrypt the random key. Then he uses this random key to decrypt the message, and he checks the signature to verify that the message is from Alice. For more discussion of PGP, see Section 15.6.