Coppersmith method

The Coppersmith method, proposed by Don Coppersmith, is a method to find small integer zeroes of univariate or bivariate polynomials, or their small zeroes 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.

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 {{mvar|Q}} is easy using, e.g., Newton's method, but such an algorithm does not work modulo a composite number {{mvar|M}}. The idea behind Coppersmith’s method is to find a different polynomial {{mvar|f}} related to {{mvar|F}} that has the same root $x_0$ modulo {{mvar|M}}, but has only small coefficients. If the coefficients and $x_0$ are small enough that $|f(x_0)| < M$ over the integers, then we have $f(x_0) = 0$ , so that $x_0$ is a root of {{mvar|f}} over {{mvar|Q}} and can be found easily. More generally, we can find a polynomial $f(x)$ with the same root $x_0$ modulo some power $M^a$ of {{mvar|M}}, satisfying $|f(x_0)| < M^a$ , and solve for $x_0$ as above.

Coppersmith's algorithm uses the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) to construct the polynomial {{mvar|f}} with small coefficients.

Given {{mvar|F}}, the algorithm constructs polynomials $p_1(x), p_2(x), \dots, p_n(x)$ that all have the same root $x_0$ modulo $M^a$ , where {{mvar|a}} is some integer chosen based on the degree of {{mvar|F}} and the size of $x_0$ .

Any linear combination of these polynomials also has $x_0$ as a root modulo $M^a$ .

The next step is to use the LLL algorithm to construct a linear combination $f(x)=\sum c_ip_i(x)$

of the $p_i(x)$ so that the inequality $|f(x_0)| < M^a$ holds.

Now standard factorization methods can calculate the zeroes of $f(x)$ over the integers.

Implementations

Coppersmith's method for univariate polynomials is implemented in

Magma as the function SmallRoots;
PARI/GP as the function zncoppersmith;
SageMath as the method small_roots.

References

{{cite book |author=Coppersmith, D.|title=Advances in Cryptology — EUROCRYPT '96 |chapter=Finding a Small Root of a Univariate Modular Equation |series=Lecture Notes in Computer Science |volume=1070 |pages=155–165 |year=1996 |doi=10.1007/3-540-68339-9_14|isbn=978-3-540-61186-8 |doi-access=free }}
{{cite book |author=Coppersmith, D. |title=Advances in Cryptology — EUROCRYPT '96 |chapter=Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known |series=Lecture Notes in Computer Science |volume=1070 |pages=178–189 |year=1996 |doi=10.1007/3-540-68339-9_16|isbn=978-3-540-61186-8 |doi-access=free }}
{{cite book | author=Coron, J. S. |title=Advances in Cryptology - EUROCRYPT 2004 |chapter=Finding Small Roots of Bivariate Integer Polynomial Equations Revisited |series=Lecture Notes in Computer Science |year=2004 |volume=3027

|pages=492–505 |doi=10.1007/978-3-540-24676-3_29 |isbn=978-3-540-21935-4 |chapter-url=https://iacr.org/archive/eurocrypt2004/30270487/bivariate.pdf}}

{{cite book |first1=A. |last1=Bauer |first2=A. |last2=Joux |title=Advances in Cryptology - EUROCRYPT 2007 |chapter=Toward a Rigorous Variation of Coppersmith's Algorithm on Three Variables |series=Lecture Notes in Computer Science |authorlink2=Antoine Joux |volume=4515 |year=2007 |pages=361–378 |doi=10.1007/978-3-540-72540-4_21 |isbn=978-3-540-72539-8 |doi-access=free }}
{{cite book |author=Coron, J. S. |title=Advances in Cryptology - CRYPTO 2007 |chapter=Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach |series=Lecture Notes in Computer Science |year=2007 |volume=4622 |pages=379–394 |doi=10.1007/978-3-540-74143-5_21 |isbn=978-3-540-74142-8 |chapter-url=https://iacr.org/archive/crypto2007/46220372/46220372.pdf}}

Category:Asymmetric-key algorithms

Category:1996 introductions