Coppersmith's attack

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article needs more citations. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Coppersmith's attack" – news · newspapers · books · scholar · JSTOR (April 2024) (Learn how and when to remove this message) This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (April 2024) (Learn how and when to remove this message) (Learn how and when to remove this message)

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, when the private key d is small, or when partial knowledge of a prime factor of the secret key is available.

Overview

The public key in the RSA cryptosystem is a pair of integers ${\displaystyle (N,e)}$, where ${\displaystyle N=pq}$ is a product of two primes with Euler totient ${\displaystyle \varphi (N)=(p-1)(q-1)}$, and ${\displaystyle e<\varphi (N)}$ is chosen to be coprime with ${\displaystyle \varphi (N)}$.

The secret key is given by an integer ${\displaystyle d}$ satisfying ${\displaystyle ed\equiv 1\ ({\text{mod }}\varphi (N))}$. A message is an integer ${\displaystyle M<N}$ (for example the binary representation of a string), and encryption produces a ciphertext ${\displaystyle C\equiv M^{e}\ ({\text{mod }}N)}$, which can be decrypted using ${\displaystyle d}$ by computing ${\displaystyle M\equiv C^{d}({\text{mod }}N)}$. Such exponentiation may be performed by exponentiation by squaring and requires a number of arithmetic operations linear in the number of bits of ${\displaystyle e}$ and ${\displaystyle d}$.

In order to improve encryption and decryption speeds, smaller values of ${\displaystyle e}$ and ${\displaystyle d}$ are desired. A safe reduction which gives a mathematically equivalent and faster decryption algorithm is known as CRT-RSA. In this scheme, the secret is given by two smaller integers, ${\displaystyle d_{p}\equiv d\ ({\text{mod }}p-1)}$ and ${\displaystyle d_{q}\equiv d\ ({\text{mod }}q-1)}$. Encryption is performed as before, but decryption is formed by computing ${\displaystyle M_{p}=C^{d_{p}}\ ({\text{mod }}p)}$ and ${\displaystyle M_{q}=C^{d_{q}}\ ({\text{mod }}q)}$ and applying the Chinese remainder theorem to combine ${\displaystyle M_{p},M_{q}}$ into the message ${\displaystyle M}$.

Coppersmith's attack primarily concerns the case when the exponents ${\displaystyle e}$ or ${\displaystyle d}$ are chosen to be too small. For example, ${\displaystyle e}$ is often chosen to be one of the Fermat primes ${\displaystyle 3,17}$ or ${\displaystyle 65537}$. Prime values for ${\displaystyle e}$ are desirable because they can be quickly checked if they are coprime with ${\displaystyle \varphi (N)}$, leading to faster key generation.

Employing small values of ${\displaystyle d}$ leads to complete attacks such as Wiener's attack, a sort of instance of the Coppersmith method , while small values of ${\displaystyle e}$ (such as ${\displaystyle e=3}$) still leads to attacks in certain situations. For example, the simplest possible instance of the attack would be when both ${\displaystyle e}$ and the message ${\displaystyle M}$ are too small, such as ${\displaystyle e=3}$ and ${\displaystyle M<N^{1/3}}$. In this case, the ciphertext satisfies ${\displaystyle C=M^{3}}$ as integers (not merely as a congruence), and the message ${\displaystyle M}$ may be recovered as the integer cube root of ${\displaystyle C}$. The Coppersmith method generalizes this case by considering polynomials other than ${\displaystyle M^{e}}$, such as those resulting from padding or polynomials on the public key itself.

Coppersmith's theorem

A simplified version of Coppersmith's theorem is stated as follows. All polynomials will be assumed to have integer coefficients, and we say a polynomial is monic modulo ${\displaystyle N}$ if its leading coefficient is ${\displaystyle 1}$ mod ${\displaystyle N}$.

Let ${\displaystyle N}$ be an integer. If ${\displaystyle f(x)}$ is a polynomial of degree ${\displaystyle d}$ which is monic modulo ${\displaystyle N}$, then the modular equation ${\displaystyle f(x)\equiv 0\ ({\text{mod }}N)}$ may be efficiently solved for all "small" solutions ${\displaystyle x_{0}}$, more precisely those satisfying ${\displaystyle |x_{0}|<N^{\delta }}$ for a fixed ${\displaystyle \delta <1/d}$.

Note that we require the bound on ${\displaystyle \log _{N}x_{0}}$ to be bounded away from ${\displaystyle 1/d}$. The closer this bound is to ${\displaystyle 1/d}$, the less efficient the method becomes.

All instances of Coppersmith's attack involve expressing the message, or an essential piece of information about the cryptosystem, as a small root for some modular polynomial equation. The Chinese remainder theorem may be employed to obtain equations with larger moduli, thus increasing the threshold on the small root condition in Coppersmith's theorem.

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}$ to multiple people ${\displaystyle P_{1},P_{2},\ldots ,P_{k}}$, using distinct moduli ${\displaystyle N_{1},N_{2},\ldots ,N_{k}}$ but the same small public exponent, say ${\displaystyle e=3}$. Then if three ciphertexts are known, the message ${\displaystyle M}$ is no longer secure. Indeed, suppose Eve intercepts three of the ciphertexts, ${\displaystyle C_{1},C_{2},C_{3}}$ satisfying ${\displaystyle C_{i}\equiv M^{3}\ ({\text{mod }}N_{i})}$. By the Chinese remainder theorem, she may combine these into an integer ${\displaystyle 0\leq C<N_{1}N_{2}N_{3}}$ satisfying ${\displaystyle C\equiv M^{3}\ ({\text{mod }}N_{1}N_{2}N_{3})}$. Here we assume ${\displaystyle \gcd(N_{i},N_{j})=1}$, or else we may factor some ${\displaystyle N_{i}}$ and compute ${\displaystyle M}$ directly.

However, since ${\displaystyle M<N_{i}}$ for each ${\displaystyle i}$, we have ${\displaystyle M^{3}<N_{1}N_{2}N_{3}}$. Therefore, the congruence implies an actual equality ${\displaystyle C=M^{3}}$ over the integers, and Eve may efficiently compute the integer cube root of ${\displaystyle C}$ to obtain the message ${\displaystyle M}$.

For larger values of ${\displaystyle e}$, the same method allows Eve to compute ${\displaystyle M}$ with ${\displaystyle e}$ ciphertexts by use of an integer root algorithm.

Coppersmith’s short-pad attack

Like Håstad’s attack, 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 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. Then Eve may recover the message if the padding is too small.

More precisely, suppose Eve intercepted two ciphertexts based on two random paddings: ${\displaystyle M_{1}=2^{m}M+r_{1}}$ and ${\displaystyle M_{2}=2^{m}M+r_{2}}$, with corresponding ciphertext ${\displaystyle C_{i}\equiv M_{i}^{e}\ ({\text{mod }}N)}$. The key is to consider the two polynomials modulo ${\displaystyle N}$

${\displaystyle g_{1}(x)=x^{e}-C_{1},\quad g_{2}(x,y)=(x+y)^{e}-C_{2}}$.

The point is that ${\displaystyle y}$ will measure the difference in padding ${\displaystyle M_{2}-M_{1}=r_{2}-r_{1}}$. Supposing that ${\displaystyle y=\Delta =M_{2}-M_{1}}$ was known, then ${\displaystyle M_{1}}$ solves both ${\displaystyle x^{e}-C_{1}\equiv 0}$ and ${\displaystyle (x+\Delta )^{e}-C_{2}\equiv 0}$ mod ${\displaystyle N}$, so that ${\displaystyle x-M_{1}}$ divides both polynomials modulo ${\displaystyle N}$. One may then compute ${\displaystyle \gcd(x^{e}-C_{1},(x+\Delta )^{e}-C_{2})}$ using the Euclidean algorithm to recover ${\displaystyle M_{1}}$ (this method is known as the Franklin-Reiter attack).

Therefore, we wish to find ${\displaystyle \Delta =r_{2}-r_{1}}$. As ${\displaystyle g_{1}(x)}$ and ${\displaystyle g_{2}(x,\Delta )}$ have the common root ${\displaystyle M_{1}}$ (modulo ${\displaystyle N}$), the integer ${\displaystyle \Delta }$ is a root for the resultant ${\displaystyle f(y)={\text{res}}_{x}(g_{1}(x),g_{2}(x,y))}$ which has degree at most ${\displaystyle e^{2}}$. Therefore, if ${\displaystyle m<\lfloor \log _{2}(N)/e^{2}\rfloor }$ and ${\displaystyle r_{i}<2^{m}}$, we have ${\displaystyle |\Delta |<2^{m}<N^{1/e^{2}}}$, so that Coppersmith's theorem applies.

For example, if ${\displaystyle N}$ is 1024 bits long and ${\displaystyle e=3}$, then the method applies for paddings less than 113 bits long. For this reason, it is recommended to use the value ${\displaystyle e=65537}$ which is completely resistant to this particular attack.

Multivariate case and small private key attacks

There are several different ways in which the Coppersmith method can be applied to polynomial equations in several variables, such as the common bivariate case ${\displaystyle f(x,y)=0}$.

1. As in Coppersmith's short pad attack, Coppersmith's method may apply directly to a system of modular equations ${\displaystyle g_{1}(x,y),\ g_{2}(x,y)\equiv 0\ ({\text{mod }}N)}$ with a common small root ${\displaystyle (x_{0},y_{0})}$, by use of the resultant to reduce to the univariate case and then computing the gcd.
2. In favorable circumstances, another approach by Coppersmith involves solving a single equation ${\displaystyle g(x,y)=0}$ for a small root ${\displaystyle (x_{0},y_{0})}$ over the integers, by extending the equation to a system of equations and applying the LLL algorithm to get nontrivial equations with the same small root. Once another nontrivial equation is found, one can solve the system over the integers, using the resolvant and gcd as in the first approach. This method was employed by Coppersmith to factorize ${\displaystyle N}$ when enough high-order bits of one of its primes are known.
3. Finally, an approach heavily studied by May involves studying systems of modular polynomial equations ${\displaystyle g_{i}(x,y)\equiv 0\ ({\text{mod }}N)}$. In this case, just like in Coppersmith's method, one introduces extra polynomial equations with the same small root ${\displaystyle (x_{0},y_{0})}$ and applies the LLL algorithm to produce equivalent polynomial equations ${\displaystyle {\tilde {g}}_{i}(x,y)\equiv 0\ ({\text{mod }}N)}$ but with smaller coefficients. This allows one to remove the modulo condition if ${\displaystyle |{\tilde {g}}_{i}(x_{0},y_{0})|<N}$, and then solve the system with resultants as before. The method applies with more variables as well. It is possible for some resultant to be zero, for example if the polynomials are not algebraically independent, in which case the particular construction fails. However, it is often successful in practice.

The third approach is particularly useful in application to attacks on small private keys. The "small roots" condition in this approach becomes more subtle to describe, since it depends on the lattice being reduced by the LLL algorithm. In general, larger collections of modular polynomial equations may produce higher dimensional lattices, allowing the LLL algorithm to produce smaller polynomials.

For example, it is possible to obtain Wiener's attack by applying the Coppersmith method to the system of polynomials

${\displaystyle g_{1}(x,y)=ex+y,\ g_{2}(x,y)=Nx}$ modulo ${\displaystyle N}$,

where if ${\displaystyle ed=k\varphi (N)+1}$ then ${\displaystyle (d,k(N-\varphi (N))-1)}$ is a common root. More precisely, the two polynomials (with scaled coefficients) span a lattice, and the LLL algorithm is applied to obtain polynomial equations over the integers, which may be solved efficiently. This is used to prove that ${\displaystyle d}$ may be recovered if ${\textstyle d<{\frac {1}{3}}N^{1/4}}$ as in Wiener's attack.

More sophisticated polynomial systems can be used to improve this bound to ${\displaystyle d<N^{0.292}}$ (for suitably large ${\displaystyle N,e}$). In fact, even the CRT-RSA scheme can be broken with sophisticated lattices under the bounds ${\displaystyle d_{p},d_{q}<N^{0.122}}$.

See also

• ROCA attack

References