Coppersmith's attack

Low public exponent attack

In order to reduce encryption or signature verification time, it is useful to use a small public exponent (${\displaystyle e}$). In practice, common choices for ${\displaystyle e}$ are 3, 17 and 65537 ${\displaystyle (2^{16}+1)}$. These values for e are Fermat primes, sometimes referred to as ${\displaystyle F_0,F_2}$ and ${\displaystyle F_4}$ respectively ${\displaystyle (F_x=2^{2^x}+1)}$. They are chosen because they make the modular exponentiation operation faster. Also, having chosen such ${\displaystyle e}$, it is simpler to test whether ${\displaystyle gcd(e,p-1)=1}$ and ${\displaystyle gcd(e,q-1)=1}$ while generating and testing the primes in step 1 of the key generation. Values of ${\displaystyle p}$ or ${\displaystyle q}$ that fail this test can be rejected there and then. (Even better: if e is prime and greater than 2, then the test ${\displaystyle pmode\ne 1}$ can replace the more expensive test ${\displaystyle gcd(p-1,e)=1}$.)

If the public exponent is small and the plaintext ${\displaystyle m}$ is very short, then the RSA function may be easy to invert, which makes certain attacks possible. Padding schemes ensure that messages have full lengths, but additionally choosing the public exponent ${\displaystyle e=2^{16}+1}$ is recommended. When this value is used, signature verification requires 17 multiplications, as opposed to about 25 when a random ${\displaystyle e}$ of similar size is used. Unlike low private exponent (see Wiener's attack), attacks that apply when a small ${\displaystyle e}$ is used are far from a total break, which would recover the secret key d. The most powerful attacks on low public exponent RSA are based on the following theorem, which is due to Don Coppersmith.

Håstad's broadcast attack

The simplest form of Håstad's attack is presented to ease understanding. The general case uses the Coppersmith method.

Suppose one sender sends the same message ${\displaystyle M}$ in encrypted form to a number of people ${\displaystyle P_1;P_2;\dots ;P_k}$, each using the same small public exponent ${\displaystyle e}$, say ${\displaystyle e=3}$, and different moduli ${\displaystyle ⟨N_i,e⟩}$. A simple argument shows that as soon as ${\displaystyle k\ge 3}$ ciphertexts are known, the message ${\displaystyle M}$ is no longer secure: Suppose Eve intercepts ${\displaystyle C_1,C_2}$, and ${\displaystyle C_3}$, where ${\displaystyle C_i\equiv M^3(\mathrm{mod}{N}_i)}$. We may assume ${\displaystyle gcd(N_i,N_j)=1}$ for all ${\displaystyle i,j}$ (otherwise, it is possible to compute a factor of one of the numbers ${\displaystyle N_i}$ by computing ${\displaystyle gcd(N_i,N_j)}$.) By the Chinese remainder theorem, she may compute ${\displaystyle C\in {\mathbb{Z}}_{N_1{N}_2{N}_3}^{\ast }}$ such that ${\displaystyle C\equiv C_i(\mathrm{mod}{N}_i)}$. Then ${\displaystyle C\equiv M^3(\mathrm{mod}{N}_1{N}_2{N}_3)}$; however, since ${\displaystyle M<N_i}$ for all ${\displaystyle i}$, we have ${\displaystyle M^3<N_1{N}_2{N}_3}$. Thus ${\displaystyle C=M^3}$ holds over the integers, and Eve can compute the cube root of ${\displaystyle C}$ to obtain ${\displaystyle M}$.

For larger values of ${\displaystyle e}$, more ciphertexts are needed, particularly, ${\displaystyle e}$ ciphertexts are sufficient.

Generalizations

Håstad also showed that applying a linear padding to ${\displaystyle M}$ prior to encryption does not protect against this attack. Assume the attacker learns that ${\displaystyle C_i=f_i(M{)}^e}$ for ${\displaystyle 1\le i\le k}$ and some linear function ${\displaystyle f_i}$, i.e., Bob applies a pad to the message ${\displaystyle M}$ prior to encrypting it so that the recipients receive slightly different messages. For instance, if ${\displaystyle M}$ is ${\displaystyle m}$ bits long, Bob might encrypt ${\displaystyle M_i=i{2}^m+M}$ and send this to the ${\displaystyle i}$-th recipient.

If a large enough group of people is involved, the attacker can recover the plaintext ${\displaystyle M_i}$ from all the ciphertext with similar methods. In more generality, Håstad proved that a system of univariate equations modulo relatively prime composites, such as applying any fixed polynomial ${\displaystyle g_i(M)\equiv 0(\mathrm{mod}{N}_i)}$, could be solved if sufficiently many equations are provided. This attack suggests that randomized padding should be used in RSA encryption.

Franklin–Reiter related-message attack

Franklin and Reiter identified an attack against RSA when multiple related messages are encrypted: If two messages differ only by a known fixed difference between the two messages and are RSA-encrypted under the same RSA modulus ${\displaystyle N}$, then it is possible to recover both of them. The attack was originally described with public exponent ${\displaystyle e=3}$, but it works more generally (with increasing cost as ${\displaystyle e}$ grows).

Let ${\displaystyle ⟨N;e_i⟩}$ be Alice's public key. Suppose ${\displaystyle M_1;M_2\in {\mathbb{Z}}_N}$ are two distinct messages satisfying ${\displaystyle M_1\equiv f(M_2)(\mathrm{mod}N)}$ for some publicly known polynomial ${\displaystyle f\in {\mathbb{Z}}_N[x]}$. To send ${\displaystyle M_1}$ and ${\displaystyle M_2}$ to Alice, Bob may naively encrypt the messages and transmit the resulting ciphertexts ${\displaystyle C_1;C_2}$. Eve can easily recover ${\displaystyle M_1;M_2}$, given ${\displaystyle C_1;C_2}$, by using the following theorem: Let ${\displaystyle g_1(x)=f(x{)}^e-C_1\in {\mathbb{Z}}_N[x]}$ and ${\displaystyle g_2(x)=x^e-C_2\in {\mathbb{Z}}_N[x]}$. Then ${\displaystyle (x-M_2)}$ is a factor of both ${\displaystyle g_1(x)}$ and ${\displaystyle g_2(x)}$. In most cases, computing the polynomial GCD reveals the message directly:

${\displaystyle gcd(g_1(x),g_2(x))=x-M_2(\mathrm{mod}N)}$

Once ${\displaystyle M_2}$ is found, ${\displaystyle M_1}$ is recovered by computing ${\displaystyle f(M_2)(\mathrm{mod}N)}$.

Coppersmith’s short-pad attack

Like Håstad’s and Franklin–Reiter’s attacks, this attack exploits a weakness of RSA with public exponent ${\displaystyle e=3}$. Coppersmith showed that if randomized padding suggested by Håstad is used improperly, then RSA encryption is not secure.

Suppose Bob sends a message ${\displaystyle M}$ to Alice using a small random padding before encrypting it. An attacker, Eve, intercepts the ciphertext and prevents it from reaching its destination. Bob decides to resend ${\displaystyle M}$ to Alice because Alice did not respond to his message. He randomly pads ${\displaystyle M}$ again and transmits the resulting ciphertext. Eve now has two ciphertexts corresponding to two encryptions of the same message using two different random pads.

Even though Eve does not know the random pad being used, she still can recover the message ${\displaystyle M}$ by using the following theorem, if the random padding is too short.