Coppersmith method

The Coppersmith method, proposed by Don Coppersmith, is a method to find small integer roots of polynomial equations. These polynomials can be univariate or bivariate. In cryptography the algorithm is mainly used in attacks on RSA when parts of the secret key are known.

The method uses the LLL algorithm ^[1] to find a polynomial that has the roots of the target polynomial as roots and has small coefficients.

Coppersmith’s method is based on lattice reduction. A lattice L is a subgroup of $\mathbf{R}^n$. Also there exists a k such that $L = \mathbf{Z}b_1\oplus \ldots \oplus \mathbf{Z}b_k$, where $B=(b_1,b_2,\ldots ,b_k)$ is a basis of L. The LLL algorithm computes a basis $(b_1^*,b_2^*,\dots ,b_k^*)$ of short vectors. If k=n, the determinant of the lattice is given by det(L)=det(B); in general $\mathrm{det}(L)\le \prod||b_i^*||$.

For any LLL reduced basis $(b_1^*,b_2^*,\dots ,b_k^*)$ it holds that $||b_k^*||\ge (\mathrm{det}(L))^{1/k}\cdot 2^{(1-k)/4}$, see ^[2].

Let $F(x) = x^n+a_{n-1}x^{n-1}+\ldots +a_1x+a_0$ and assume that $F(x_0)\equiv 0 \mod M$ for some integer | x₀ | < M^{1 / n}. Coppersmith’s algorithm can be used to find this integer solution x₀.

Finding roots over Q is easy using e.g. Newton's method but these algorithms do not work modulo a composite number M. The idea behind Coppersmith’s method is to find a different polynomial F₂ related to F that has the same x₀ as a solution and has only small coefficients. If the coefficients and x₀ are so small that F₂(x₀) < M over the integers, then x₀ is a root of F over Q and can easily be found.

How to find small roots using Coppersmith's method

Coppersmith’s approach is a reduction of solving modular polynomial equations to solving polynomials over the integers. Coppersmith's algorithm uses LLL to construct the polynomial F₂ with small coefficients.

Given F, the algorithm constructs polynomials $p_1(x),p_2(x),\dots ,p_n(x)$ that have the same x₀ as root modulo M^a, where a is some integer chosen dependent on the degree of F and the size of x₀. Any linear combination of these polynomials has x₀ as root modulo M^a.

The next step is to use the LLL algorithm to construct a linear combination $F_2(x)=\sum c_ip_i(x)$ of the p_i so that the inequality | F₂(x) | < M^a holds. Now standard factorization methods can calculate the roots of F₂(x) over the integers.

References

1. ^ Lattice Basis Reduction Algorithms (http://www.farcaster.com/papers/sm-thesis/node7.html)
2. ^ A. Bauer and A. Joux, Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables, Springer, LNCS 4515, 2007