2008 · 16 citations · 13 references
Natural SciencesComputer ScienceMathematicsCryptographyFault ToleranceNumber TheoryApproximation MethodsContinued FractionsContinued Fraction AlgorithmsContinued Fraction ExpansionsContinued Fraction TransformationsContinued-fraction ExpansionGeneralized Continued FractionsPublic-key EncryptionRsa Cryptosystem
Let (n = pq, e) be an RSA public key with private exponent d = n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">delta</sup> , where p and q are large primes of the same bit size. Suppose that p <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> ges radicn be an approximation of p with |p - po| les 1/8n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">alpha</sup> , alpha les 1/2. Using continued fractions, we show that the system is insecure if delta < 1-alpha/2. Our result is deterministic polynomial time and an extension of Coppersmith's result on a factorization.
13
Factoring polynomials with rational coefficients
A. K. Lenstra, H. W. Lenstra, László Lovász · Mathematische Annalen · 1982 · 4K citations · Full text
Henry J. Ricardo, David Burton · The Two-Year College Mathematics Journal · 1979 · 975 citations