Coppersmith method

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 | x0 | < M1 / n. Coppersmith’s algorithm can be used to find this integer solution x0.

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 F2 related to F that has the same x0 as a solution and has only small coefficients. If the coefficients and x0 are so small that F2(x0) < M over the integers, then x0 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 F2 with small coefficients.

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

The next step is to use the LLL algorithm to construct a linear combination F_2(x)=\sum c_ip_i(x) of the pi so that the inequality | F2(x) | < Ma holds. Now standard factorization methods can calculate the roots of F2(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

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Coppersmith's Attack — describes a class of attacks on the public key cryptosystem RSA based on Coppersmith s theorem (see below). The public key in the RSA system is a tuple of integers (N,e), where N is the product of two primes p and q. The secret key is given by an …   Wikipedia

  • Matrix multiplication — In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n by m matrix and B is an m by p matrix, the result AB of their multiplication is an n by p matrix defined only if… …   Wikipedia

  • Data Encryption Standard — The Feistel function (F function) of DES General Designers IBM First publis …   Wikipedia

  • Computational complexity of mathematical operations — The following tables list the running time of various algorithms for common mathematical operations. Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.[1] See big O notation for an explanation …   Wikipedia

  • Differential cryptanalysis — is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at… …   Wikipedia

  • RSA — In cryptography, RSA is an algorithm for public key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is widely used in electronic… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • RSA-Kryptosystem — RSA ist ein asymmetrisches kryptographisches Verfahren, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann.[1] Es verwendet ein Schlüsselpaar, bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder… …   Deutsch Wikipedia

  • METALS AND MINING — In the Bible Six metals are mentioned in the Bible and in many passages they are listed in the same order: gold, silver, copper, iron, tin, and lead. Antimony is also mentioned. The metals are referred to in various contexts, including methods of …   Encyclopedia of Judaism

  • Color-coding — For other uses, see Color code. In computer science and graph theory, the method of color coding[1][2] efficiently finds k vertex simple paths, k vertex cycles, and other small subgraphs within a given graph using probabilistic algorithms, which… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”