Low encryption or decryption exponents are tempting because they speed up encryption or decryption. However, there are certain dangers that must be avoided. One pitfall of using $e=3$ is given in Computer Problem 14. Another difficulty is discussed in Chapter 23 (Lattice Methods). These problems can be avoided by using a somewhat higher exponent. One popular choice is $e=65537=2^{16}+1$. This is prime, so it is likely that it is relatively prime to $(p-1)(q-1)$. Since it is one more than a power of 2, exponentiation to this power can be done quickly: To calculate $x^{65537}$, square $x$ sixteen times, then multiply the result by $x$.

The decryption exponent $d$ should of course be chosen large enough that brute force will not find it. However, even more care is needed, as the following result shows. One way to obtain desired properties of $d$ is to choose $d$ first, then find $e$ with $de\equiv 1(\text{mod}\varphi (n))$.

Suppose Bob wants to be able to decrypt messages quickly, so he chooses a small value of $d$. The following theorem of M. Wiener [Wiener] shows that often Eve can then find $d$ easily. In practice, if the inequalities in the hypotheses of the proposition are weakened, then Eve can still use the method to obtain $d$ in many cases. Therefore, it is recommended that $d$ be chosen fairly large.

A common use of RSA is to transmit keys for use in DES, AES, or other symmetric cryptosystems. However, a naive implementation could lead to a loss of security. Suppose a 56-bit DES key is written as a number $m\approx {10}^{17}$. This is encrypted with RSA to obtain $c\equiv m^e(\text{mod}n)$. Although $m$ is small, the ciphertext $c$ is probably a number of the same size as $n$, so perhaps around 200 digits. However, Eve attacks the system as follows. She makes two lists:

1. $c{x}^{-e}(\text{mod}n)$ for all $x$ with $1\le x\le {10}^9$.

2. $y^e(\text{mod}n)$ for all $y$ with $1\le y\le {10}^9$.

She looks for a match between an element on the first list and an element on the second list. If she finds one, then she has $c{x}^{-e}\equiv y^e$ for some $x\text{,}y$. This yields

so $m\equiv xy(\text{mod}n)$. Is this attack likely to succeed? Suppose $m$ is the product of two integers $x$ and $y$, both less than ${10}^9$. Then these $x\text{,}y$ will yield a match for Eve. Not every $m$ will have this property, but many values of $m$ are the product of two integers less than ${10}^9$. For these, Eve will obtain $m$.

This attack is much more efficient than trying all ${10}^{17}$ possibilities for $m$, which is nearly impossible on one computer, and would take a long time even with several computers working in parallel. In the present attack, Eve needs to compute and store a list of length ${10}^9$, then compute the elements on the other list and check each one against the first list. Therefore, Eve performs approximately $2\times {10}^9$ computations (and compares with the list up to ${10}^9$ times). This is easily possible on a single computer. For more on this attack, see [Boneh-Joux-Nguyen].

It is easy to prevent this attack. Instead of using a small value of $m$, adjoin some random digits to the beginning and end of $m$ so as to form a much longer plaintext. When Bob decrypts the ciphertext, he simply removes these random digits and obtains $m$.

A more sophisticated method of preprocessing the plaintext, namely Optimal Asymmetric Encryption Padding (OAEP), was introduced by Bellare and Rogaway [Bellare-Rogaway2] in 1994. Suppose Alice wants to send a message $m$ to Bob, whose RSA public key is $(n\text{,}e)$, where $n$ has $k$ bits. Two positive integers $k_0$ and $k_1$ are specified in advance, with $k_0+k_1<k$. Alice’s message is allowed to have $k-k_0-k_1$ bits. Typical values are $k=1024$, $k_0=k_1=128$, $k-k_0-k_1=768$. Let $G$ be a function that inputs strings of $k_0$ bits and outputs strings of $k-k_0$ bits. Let $H$ be a function that inputs $k-k_0$ bits and outputs $k_0$ bits. The functions $G$ and $H$ are usually constructed from hash functions (see Chapter 11 for a discussion of hash functions). To encrypt $m$, Alice first expands it to length $k-k_0$ by adjoining $k_1$ zero bits. The result is denoted $m{0}^{k_1}$. She then chooses a random string $r$ of $k_0$ bits and computes

If the concatenation $x_1||x_2$ is a binary number larger than $n$, Alice chooses a new random number $r$ and computes new values for $x_1$ and $x_2$. As soon as she obtains $x_1||x_2<n$ (this has a probability of at least 1/2 of happening for each $r$, as long as $G(r)$ produces fairly random outputs), she forms the ciphertext

To decrypt a ciphertext $c$, Bob uses his private RSA decryption exponent $d$ to compute $c^d(\text{mod}n)$. The result is written in the form

where $y_1$ has $k-k_0$ bits and $y_2$ has $k_0$ bits. Bob then computes

The correctness of this decryption can be justified as follows. If the ciphertext is the encryption of $m$, then

Therefore,

and

Bob removes the $k_1$ zero bits from the end of $m{0}^{k_1}$ and obtains $m$. Also, Bob has check on the integrity of the ciphertext. If there are not $k_1$ zeros at the end, then the ciphertext does not correspond to a valid encryption.

This method is sometimes called plaintext-aware encryption. Note that the padding with $x_2$ depends on the message $m$ and on the random parameter $r$. This makes chosen ciphertext attacks on the system more difficult. It also is used for ciphertext indistinguishability. See Section 4.5.

For discussion of the security of OAEP, see [Shoup].

Another type of attack on RSA and similar systems was discovered by Paul Kocher in 1995, while he was an undergraduate at Stanford. He showed that it is possible to discover the decryption exponent by carefully timing the computation times for a series of decryptions. Though there are ways to thwart the attack, this development was unsettling. There had been a general feeling of security since the mathematics was well understood. Kocher’s attack demonstrated that a system could still have unexpected weaknesses.

Here is how the timing attack works. Suppose Eve is able to observe Bob decrypt several ciphertexts $y$. She times how long this takes for each $y$. Knowing each $y$ and the time required for it to be decrypted will allow her to find the decryption exponent $d$. But first, how could Eve obtain such information? There are several situations where encrypted messages are sent to Bob and his computer automatically decrypts and responds. Measuring the response times suffices for the present purposes.

We need to assume that we know the hardware being used to calculate $y^d(\text{mod}n)$. We can use this information to calculate the computation times for various steps that potentially occur in the process.

Let’s assume that $y^d(\text{mod}n)$ is computed by an algorithm given in Exercise 56 in Chapter 3, which is as follows:

Let $d=b_1{b}_2\dots b_w$ be written in binary (for example, when $x=1011$, we have $b_1=1\text{,}{b}_2=0\text{,}{b}_3=1\text{,}{b}_4=1$). Let $y$ and $n$ be integers. Perform the following procedure:

1. Start with $k=1$ and $s_1=1$.

2. If $b_k=1$, let $r_k\equiv s_{k}y(\text{mod}n)$. If $b_k=0$, let $r_k=s_k$.

3. Let $s_{k+1}\equiv r_k^2(\text{mod}n)$.

4. If $k=w$, stop. If $k<w$, add 1 to $k$ and go to (2).

Then $r_w\equiv y^d(\text{mod}n)$.

Note that the multiplication $s_{k}y$ occurs only when the bit $b_k=1$. In many situations, there is a reasonably large variation in how long this multiplication takes. We assume this is the case here.

Before we continue, we need a few facts from probability. Suppose we have a random process that produces real numbers $t$ as outputs. For us, $t$ will be the time it takes for the computer to complete a calculation, given a random input $y$. The mean is the average value of these outputs. If we record outputs $t_1\text{,}\dots \text{,}{t}_n$, the mean should be approximately $m=(t_1+\cdots t_n)/n$. The variance for the random process is approximated by

The standard deviation is the square root of the variance and gives a measure of how much variation there is in the values of the $t_i$’s.

The important fact we need is that when two random processes are independent, the variance for the sum of their outputs is the sum of the variances of the two processes. For example, we will break the computation done by the computer into two independent processes, which will take times $t^{\prime }$ and $t^{\prime \prime }$. The total time $t$ will be $t^{\prime }+t^{\prime \prime }$. Therefore, $\text{Var}(\{t_i\})$ should be approximately $\text{Var}(\{t_i^{\prime }\})+\text{Var}(\{t_i^{″}\})$.

Now assume Eve knows ciphertexts $y_1\text{,}\dots \text{,}{y}_n$ and the times that it took to compute each $y_i^d(\text{mod}n)$. Suppose she knows bits $b_1\text{,}\dots \text{,}{b}_{k-1}$ of the exponent $d$. Since she knows the hardware being used, she knows how much time was used in calculating $r_1\text{,}\dots \text{,}{r}_{k-1}$ in the preceding algorithm. Therefore, she knows, for each $y_i$, the time $t_i$ that it takes to compute $r_k\text{,}\dots \text{,}{r}_w$.

Eve wants to determine $b_k$. If $b_k=1$, a multiplication $s_{k}y(\text{mod}n)$ will take place for each ciphertext $y_i$ that is processed. If $b_k=0$, there is no such multiplication.

Let $t_i^{\prime }$ be the amount of time it takes the computer to perform the multiplication $s_{k}y(\text{mod}n)$, though Eve does not yet know whether this multiplication actually occurs. Let $t_i^{″}=t_i-t_i^{\prime }$. Eve computes $\text{Var}(\{t_i\})$ and $\text{Var}(\{t_i^{″}\})$. If $\text{Var}(\{t_i\})>\text{Var}(\{t_i^{″}\})$, then Eve concludes that $b_k=1$. If not, $b_k=0$. After determining $b_k$, she proceeds in the same manner to find all the bits.

Why does this work? If the multiplication occurs, $t_i^{″}$ is the amount of time it takes the computer to complete the calculation after the multiplication. It is reasonable to assume $t_i^{\prime }$ and $t_i^{″}$ are outputs that are independent of each other. Therefore,

If the multiplication does not occur, $t_i^{\prime }$ is the amount of time for an operation unrelated to the computation, so it is reasonable to assume $t_i$ and $t_i^{\prime }$ are independent. Therefore,

Note that we couldn’t use the mean in place of the variance, since the mean of $\{-t_i\}$ would be negative, so the last inequality would not hold. All that can be deduced from the mean is the total number of nonzero bits in the binary expansion of $d$.

The preceding gives a fairly simple version of the method. In practice, various modifications would be needed, depending on the specific situation. But the general strategy remains the same. For more details, see [Kocher]. For more on timing attacks, see [Crosby et al.].

A similar attack on RSA works by measuring the power consumed during the computations. See [Kocher et al.]. Another method, called acoustic cryptanalysis, obtains information from the high-pitched noises emitted by the electronic components of a computer during its computations. See [Genkin et al.]. Attacks such as these and the timing attack can be prevented by appropriate design features in the physical implementation.

Timing attacks, power analysis, and acoustic cryptanalysis are examples of side-channel attacks, where the attack is on the implementation rather than on the basic cryptographic algorithm.