Coppersmith method

The Coppersmith method, proposed by Don Coppersmith, is a method to find small integer zeroes of univariate or bivariate polynomials modulo a given integer.

The method uses the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) to find a polynomial that has the same zeroes as the target polynomial but smaller coefficients.[1]

In cryptography, the Coppersmith method is mainly used in attacks on RSA when parts of the secret key are known and forms a base for Coppersmith's Attack.

Approach

Coppersmith’s approach is a reduction of solving modular polynomial equations to solving polynomials over the integers.

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

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_2 related to F that has the same x_0 as a solution and has only small coefficients. If the coefficients and x_0 are so small that F_2(x_0) < M over the integers, then x_0 is a root of F over Q and can easily be found.

Coppersmith's algorithm uses LLL to construct the polynomial F_2 with small coefficients. Given F, the algorithm constructs polynomials p_1(x), p_2(x), \dots, p_n(x) that have the same zero x_0 modulo M^a, where a is some integer chosen dependent on the degree of F and the size of x_0. Any linear combination of these polynomials has zero x_0 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_2(x)| < M^a holds. Now standard factorization methods can calculate the zeroes of F_2(x) over the integers.

See also

References

  1. ↑ "Lattice Basis Reduction Algorithms".
This article is issued from Wikipedia - version of the Friday, November 20, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.