Coppersmith's attack

Coppersmith's attack describes a class of cryptographic attacks on the public-key cryptosystem RSA based on the Coppersmith method. Particular applications of the Coppersmith method for attacking RSA include cases when the public exponent e is small or when partial knowledge of a prime factor of the secret key is available.

RSA basics[]

The public key in the RSA system is a tuple of integers ${\displaystyle (N,e)}$, where N is the product of two primes p and q. The secret key is given by an integer d satisfying ${\displaystyle ed\equiv 1{\pmod {(p-1)(q-1)}}}$; equivalently, the secret key may be given by ${\displaystyle d_{p}\equiv d{\pmod {p-1}}}$ and ${\displaystyle d_{q}\equiv d{\pmod {q-1}}}$ if the Chinese remainder theorem is used to improve the speed of decryption, see CRT-RSA. Encryption of a message M produces the ciphertext ${\displaystyle C\equiv M^{e}{\pmod {N}}}$, which can be decrypted using ${\displaystyle d}$ by computing ${\displaystyle C^{d}\equiv M{\pmod {N}}}$.

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 p{\bmod {e}}\neq 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 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.

Coppersmith method[]

Theorem 1 (Coppersmith)^[1]

Let N be an integer and ${\displaystyle f\in {\mathbb {Z} }[x]}$ be a monic polynomial of degree ${\displaystyle d}$ over the integers. Set ${\displaystyle X=N^{{\frac {1}{d}}-\epsilon }}$ for ${\displaystyle {\frac {1}{d}}>\epsilon >0}$. Then, given ${\displaystyle \left\langle N,f\right\rangle }$, attacker (Eve) can efficiently find all integers ${\displaystyle x_{0}<X}$ satisfying ${\displaystyle f(x_{0})\equiv 0{\pmod {N}}}$. The running time is dominated by the time it takes to run the LLL algorithm on a lattice of dimension O${\displaystyle (w)}$ with ${\displaystyle w=\min \left\{{\frac {1}{\epsilon }},\log _{2}N\right\}}$.

This theorem states the existence of an algorithm that can efficiently find all roots of ${\displaystyle f}$ modulo ${\displaystyle N}$ that are smaller than ${\displaystyle X=N^{\frac {1}{d}}}$. As ${\displaystyle X}$ gets smaller, the algorithm's runtime decreases. This theorem's strength is the ability to find all small roots of polynomials modulo a composite ${\displaystyle N}$.

Håstad's broadcast attack[]

The simplest form of Håstad's attack^[2] 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 \left\langle N_{i},e\right\rangle }$. A simple argument shows that as soon as ${\displaystyle k\geq 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}{\pmod {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}}^{*}}$ such that ${\displaystyle C\equiv C_{i}{\pmod {N_{i}}}}$. Then ${\displaystyle C\equiv M^{3}{\pmod {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\leq i\leq 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}=i2^{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{\pmod {N_{i}}}}$, could be solved if sufficiently many equations are provided. This attack suggests that randomized padding should be used in RSA encryption.

Theorem 2 (Håstad)

Suppose ${\displaystyle N_{1},\dots ,N_{k}}$ are relatively prime integers and set ${\displaystyle N_{\text{min}}=\min _{i}\{N_{i}\}}$. Let ${\displaystyle g_{i}(x)\in \mathbb {Z} /N_{i}[x]}$ be ${\displaystyle k}$ polynomials of maximum degree ${\displaystyle q}$. Suppose there exists a unique ${\displaystyle M<N_{\text{min}}}$ satisfying ${\displaystyle g_{i}(M)\equiv 0{\pmod {N_{i}}}}$ for all ${\displaystyle i\in \left\{1,\dots ,k\right\}}$. Furthermore, suppose ${\displaystyle k>q}$. There is an efficient algorithm that, given ${\displaystyle \left\langle N_{i},g_{i}(x)\right\rangle }$ for all ${\displaystyle i}$, computes ${\displaystyle M}$.

Proof

Since the ${\displaystyle N_{i}}$ are relatively prime the Chinese remainder theorem might be used to compute coefficients ${\displaystyle T_{i}}$ satisfying ${\displaystyle T_{i}\equiv 1{\pmod {N_{i}}}}$ and ${\displaystyle T_{i}\equiv 0{\pmod {N_{j}}}}$ for all ${\displaystyle i\neq j}$. Setting ${\displaystyle g(x)=\sum T_{i}\cdot g_{i}(x)}$, we know that ${\displaystyle g(M)\equiv 0{\pmod {\prod N_{i}}}}$. Since the ${\displaystyle T_{i}}$ are nonzero, we have that ${\displaystyle g(x)}$ is also nonzero. The degree of ${\displaystyle g(x)}$ is at most ${\displaystyle q}$. By Coppersmith’s theorem, we may compute all integer roots ${\displaystyle x_{0}}$ satisfying ${\displaystyle g(x_{0})\equiv 0{\pmod {\prod N_{i}}}}$ and ${\displaystyle \left|x_{0}\right|<\left(\prod N_{i}\right)^{\frac {1}{q}}}$. However, we know that ${\displaystyle M<N_{\text{min}}<\left(\prod N_{i}\right)^{\frac {1}{k}}<\left(\prod N_{i}\right)^{\frac {1}{q}}}$, so ${\displaystyle M}$ is among the roots found by Coppersmith's theorem.

This theorem can be applied to the problem of broadcast RSA in the following manner: Suppose the ${\displaystyle i}$-th plaintext is padded with a polynomial ${\displaystyle f_{i}(x)}$, so that ${\displaystyle g_{i}={\big (}f_{i}(x){\big )}^{e_{i}}-C_{i}{\bmod {N}}_{i}}$. Then ${\displaystyle g_{i}(M)\equiv 0{\bmod {N}}_{i}}$ is true, and Coppersmith’s method can be used. The attack succeeds once ${\displaystyle k>\max _{i}(e_{i}\cdot \deg f_{i})}$, where ${\displaystyle k}$ is the number of messages. The original result used Håstad’s variant instead of the full Coppersmith method. As a result, it required ${\displaystyle k=O(q^{2})}$ messages, where ${\displaystyle q=\max _{i}(e_{i}\cdot \deg f_{i})}$.^[2]

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 \left\langle N;e_{i}\right\rangle }$ 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}){\pmod {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:

Theorem 3 (Franklin–Reiter)^[1]

Let ${\displaystyle \left\langle N,e\right\rangle }$ be an RSA public key. Let ${\displaystyle M_{1}\neq M_{2}\in \mathbb {Z} _{N}^{*}}$ satisfy ${\displaystyle M_{1}\equiv f(M_{2}){\pmod {N}}}$ for some linear polynomial ${\displaystyle f=ax+b\in \mathbb {Z} _{N}[x]}$ with ${\displaystyle b\neq 0}$. Then, given ${\displaystyle \left\langle N,e,C_{1},C_{2},f\right\rangle }$, attacker (Eve) can recover ${\displaystyle M_{1},M_{2}}$ in time quadratic in ${\displaystyle e\cdot \log N}$.

Proof

Since ${\displaystyle C_{1}\equiv M_{1}^{e}{\pmod {N}}}$, we know that ${\displaystyle M_{2}}$ is a root of the polynomial ${\displaystyle g_{1}(x)=f(x)^{e}-C_{1}\in \mathbb {Z} _{N}[x]}$. Similarly, ${\displaystyle M_{2}}$ is a root of ${\displaystyle g_{2}(x)=x^{e}-C_{2}\in \mathbb {Z} _{N}[x]}$. Hence, the linear factor ${\displaystyle x-M_{2}}$ divides both polynomials. Therefore, Eve may calculate the greatest common divisor ${\displaystyle \gcd(g_{1},g_{2})}$ of ${\displaystyle g_{1}}$ and ${\displaystyle g_{2}}$, and if the ${\displaystyle \gcd }$ turns out to be linear, ${\displaystyle M_{2}}$ is found. The ${\displaystyle \gcd }$ can be computed in quadratic time in ${\displaystyle e}$ and ${\displaystyle \log N}$ using the Euclidean algorithm.

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.

Theorem 4 (Coppersmith)

Let ${\displaystyle \left\langle N,e\right\rangle }$ be a public RSA key, where ${\displaystyle N}$ is ${\displaystyle n}$ bits long. Set ${\displaystyle m=\left\lfloor {\frac {n}{e^{2}}}\right\rfloor }$. Let ${\displaystyle M\in \mathbb {Z} _{N}^{*}}$ be a message of length at most ${\displaystyle n-m}$ bits. Define ${\displaystyle M_{1}=2^{m}M+r_{1}}$ and ${\displaystyle M_{2}=2^{m}M+r_{2}}$, where ${\displaystyle r_{1}}$ and ${\displaystyle r_{2}}$ are distinct integers with ${\displaystyle 0\leq r_{1},r_{2}<2^{m}}$. If Eve is given ${\displaystyle \left\langle N,e\right\rangle }$ and the encryptions ${\displaystyle C_{1},C_{2}}$ of ${\displaystyle M_{1},M_{2}}$ (but is not given ${\displaystyle r_{1}}$ or ${\displaystyle r_{2}}$), she can efficiently recover ${\displaystyle M}$.

Proof^[1]

Define ${\displaystyle g_{1}(x,y)=x^{e}-C_{1}}$ and ${\displaystyle g_{2}(x,y)=(x+y)^{e}-C_{2}}$. We know that when ${\displaystyle y=r_{2}-r_{1}}$, these polynomials have ${\displaystyle x=M_{1}}$ as a common root. In other words, ${\displaystyle \Delta =r_{2}-r_{1}}$ is a root of the resultant ${\displaystyle h(y)=\operatorname {res} _{x}(g_{1},g_{2})\in \mathbb {Z} _{N}[y]}$. Furthermore, ${\displaystyle |\Delta |<2^{m}<N^{\frac {1}{e^{2}}}}$. Hence, ${\displaystyle \Delta }$ is a small root of ${\displaystyle h}$ modulo ${\displaystyle N}$, and Eve can efficiently find it using the Coppersmith method. Once ${\displaystyle \Delta }$ is known, the Franklin–Reiter attack can be used to recover ${\displaystyle M_{2}}$ and consequently ${\displaystyle M}$.

See also[]

• ROCA attack

References[]