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.

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}}}$.

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 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.

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 \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.

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.