Coppersmith's method
Solving a polynomial equation modulo an RSA modulus is as hard as factoring in general. Coppersmith showed in 1996 that it becomes easy when the root is small: any root below N1/d of a monic degree-d polynomial can be found in polynomial time, with lattice reduction. A remarkable number of practical RSA breaks are this one theorem applied to a different polynomial.
- Problem
- Given monic f of degree d and N of unknown factorisation, find every x0 with f(x0) ≡ 0 mod N and |x0| < X
- Reach
- X up to N1/d, in time polynomial in log N and d
- Tool
- LLL on a lattice of polynomials that all vanish at x0 modulo Nh
- Measured here
- 68 unknown bits of a message recovered from its e = 3 ciphertext under a 256-bit modulus, against a limit of 85
- Consequences
- Stereotyped messages with small e, factoring with half of p known, ROCA, Boneh–Durfee for d < N0.292
The idea
Finding roots of a polynomial over the integers is easy. Over Z/NZ with N composite it is not: square roots mod N alone are equivalent to factoring. The method's starting point is to move the problem from the first setting to the second.
Suppose f(x0) ≡ 0 mod N with |x0| < X. Howgrave-Graham's formulation of Coppersmith's idea builds many polynomials that also vanish at x0, modulo a power Nh: the shifted multiples xj Nh−i f(x)i. Any integer combination of them vanishes at x0 mod Nh too. If some combination g has coefficients so small that |g(x0)| < Nh is guaranteed for every |x0| < X, then g(x0), a multiple of Nh smaller than Nh, must be exactly zero. Now x0 is a root of g over the integers, and it can simply be found.
Finding a combination with small coefficients is a short-vector problem. Write each polynomial's coefficients, with the coefficient of xk multiplied by Xk, as a row of a matrix, and reduce it with LLL. The first reduced vector is short relative to the determinant of the lattice, and the determinant is easy to compute. That is why the method's reach can be predicted exactly, up to LLL's approximation factor.
A stereotyped message
The classic example is RSA with public exponent e = 3 and a message that is mostly known: a fixed header, a date, a template with a short secret in the last field. Write the message as M0 + x0, where M0 is known and x0 is the unknown low part. Then x0 is a small root of
and Coppersmith's bound says any x0 below N1/3 can be recovered: a third of the message, with no factoring and no private key. The code behind this page generated a 256-bit modulus from two 128-bit primes, and ran the attack with h = 1, 2 and 3, which give lattices of dimension 4, 7 and 10. For each size it searched for the largest number of unknown bits at which the attack recovered two fresh messages in a row. Every recovered message was re-encrypted and compared with the ciphertext.
| h | Dimension | Predicted | Recovered |
|---|---|---|---|
| 1 | 4 | 42.7 | 40 |
| 2 | 7 | 61.0 | 60 |
| 3 | 10 | 68.3 | 68 |
The predicted column comes from the determinant alone. With dimension n = 3h + 1, the lattice's determinant is N3h(h+1)/2 Xn(n−1)/2. The attack works roughly when its n-th root falls below Nh, and solving for X gives the bound. For h = 1 that is X < N1/6, 42.7 bits, and the attack recovered 40. Larger lattices close in on N1/3 = 85 bits slowly, and at growing cost. The dimension-10 run at 68 unknown bits took 1,582 LLL swaps on entries over a thousand bits long, and the reduced basis was checked against both LLL conditions.
What follows from it
- Small public exponents. e = 3 with deterministic or low-entropy padding falls to the attack above, and Håstad's broadcast attack, which recovers a message sent to several recipients, is sharpened by it. Randomised padding such as OAEP removes the structure the attack needs.
- Factoring with partial knowledge. Coppersmith also showed that N = pq can be factored in polynomial time once half of the bits of p are known, the top half or the bottom half. Side channels and weak key generators that leak those bits break the key outright.
- ROCA. In 2017 Nemec, Sys, Švenda, Klinec and Matyáš found that RSA keys from a widely deployed Infineon library had primes of a special form, and applied a Coppersmith-style attack over the few unknown parameters. The affected smartcards, TPMs and identity cards had to be reissued.
- Small private exponents. Boneh and Durfee used a bivariate version to break RSA whenever d < N0.292, improving on Wiener's continued-fraction bound of N1/4. The bivariate method rests on a heuristic that the reduced polynomials are algebraically independent, which holds in practice.
- Partial key exposure. Knowing a fraction of the bits of d, together with a small e, is also often enough to recover the rest.
The boundary
Coppersmith's method is not an attack on the RSA problem. Properly generated RSA keys with standard exponents and randomised padding leave it nothing to use. It needs structure the designer did not intend: a small root, known bits, a special form of prime. Its reach is predictable, so for each of those structures there is a precise answer to how much leakage is too much, and that is its lasting value to an assessor.
The same lattice machinery, applied to a different equation, gives the hidden number problem attack on ECDSA nonces with a few leaked bits.
Primary sources
- D. Coppersmith, "Small solutions to polynomial equations, and low exponent RSA vulnerabilities", Journal of Cryptology 10 (1997)
- N. Howgrave-Graham, "Finding small roots of univariate modular equations revisited", Cryptography and Coding 1997
- D. Boneh and G. Durfee, "Cryptanalysis of RSA with private key d less than N0.292", IEEE Transactions on Information Theory 46 (2000)
- M. Nemec, M. Sys, P. Švenda, D. Klinec and V. Matyáš, "The return of Coppersmith's attack: practical factorization of widely used RSA moduli", ACM CCS 2017
- A. May, "Using LLL-reduction for solving RSA and factorization problems", in The LLL Algorithm, Springer (2010)