Abstract
Twenty five years ago, Lenstra, Lenstra and Lovász presented their celebrated LLL lattice reduction algorithm. Among the various applications of the LLL algorithm is a method due to Coppersmith for finding small roots of polynomial equations. We give a survey of the applications of this root finding method to the problem of inverting the RSA function and the factorization problem. As we will see, most of the results are of a dual nature, they can either be interpreted as cryptanalytic results or as hardness/security results.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
R. Rivest, A. Shamir and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, Vol. 21(2), pp.120–126, 1978
D. Boneh, Venkatesan, Breaking RSA may not be equivalent to factoring, Advances in Cryptology – Eurocrypt ’98, Lecture Notes in Computer Science Vol. 1233, Springer, pp. 59–71, 1998
D. Brown, Breaking RSA May Be As Difficult As Factoring, Cryptology ePrint Archive Report 2005/380, 2005
G. Leander, A. Rupp, On the Equivalence of RSA and Factoring Regarding Generic Ring Algorithms, Advances in Cryptology – Asiacrypt 2006, Lecture Notes in Computer Science Vol. 4284, pp. 241–251, Springer, 2006
D. Boneh, Twenty years of attacks on the RSA cryptosystem, Notices of the AMS, 1999
S. Katzenbeisser, Recent Advances in RSA Cryptography, Advances in Information Security, Kluwer Academic Publishers, 2001
C. Pomerance, The Quadratic Sieve Factoring Algorithm, Advances in Cryptology – Eurocrypt 84, Lecture Notes in Computer Science, pp. 169–182, 1985
H. W. Lenstra, Factoring Integers with Elliptic Curves, Mathematische Annalen, Vol. 126, pp. 649–673, 1987
A.K. Lenstra, H.W. Lenstra, The Development of the Number Field Sieve, Springer, 1993
P.W. Shor, Algorithms for quantum computation: Discrete log and factoring, In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994
D. Coppersmith, Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known, Advances in Cryptology – Eurocrypt ’96, Lecture Notes in Computer Science Vol. 1070, Springer, pp. 178–189, 1996
J. Håstad, Solving Simultaneous Modular Equations of Low Degree, Siam J. Computing, 1988
M. Girault, P. Toffin, B. Vallée, Computation of Approximate L-th Roots Modulo n and Application to Cryptography, Advances in Cryptology – Crypto 1988, Lecture Notes in Computer Science Vol. 403, pp. 100-117, 1988
D. Coppersmith, Finding a Small Root of a Univariate Modular Equation, Advances in Cryptology – Eurocrypt ’96, Lecture Notes in Computer Science Vol. 1070, Springer, pp. 155–165, 1996
D. Coppersmith, Small solutions to polynomial equations and low exponent vulnerabilities, Journal of Cryptology, Vol. 10(4), pp. 223–260, 1997.
D. Coppersmith, Finding Small Solutions to Small Degree Polynomials, Cryptography and Lattice Conference (CaLC 2001), Lecture Notes in Computer Science Volume 2146, Springer, pp. 20–31, 2001.
A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients,” Mathematische Annalen, Vol. 261, pp. 513–534, 1982
V. Shoup, OAEP Reconsidered, Advances in Cryptology – Crypto 2001, Lecture Notes in Computer Science Vol. 2139, Springer, pp. 239–259, 2001
R. Steinfeld, J. Pieprzyk, H. Wang, On the Provable Security of an Efficient RSA-Based Pseudorandom Generator, Advances in Cryptology – Asiacrypt 2006, Lecture Notes in Computer Science Vol. 4284, pp. 194–209, Springer, 2006
D. Boneh, G. Durfee, and N. Howgrave-Graham, Factoring N = p r q for large r, Advances in Cryptology – Crypto ’99, Lecture Notes in Computer Science Vol. 1666, Springer, pp. 326–337, 1999
A. May, Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring, Advances in Cryptology (Crypto 2004), Lecture Notes in Computer Science Volume 3152, pages 213–219, Springer, 2004
J.-S. Coron, A. May, Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring, Journal of Cryptology, 2007
D. Boneh, Finding smooth integers in short intervals using CRT decoding, STOC, pp. 265–272, 2000
M. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Transactions on Information Theory, Vol. 36, pp. 553–558, 1990
D. Boneh, G. Durfee, Cryptanalysis of RSA with private key d less than N 0. 292, Advances in Cryptology – Eurocrypt’99, Lecture Notes in Computer Science Vol. 1592, Springer, pp. 1–11, 1999.
D. Boneh, G. Durfee, Cryptanalysis of RSA with private key d less than N 0. 292, IEEE Trans. on Information Theory, Vol. 46(4), pp. 1339–1349, 2000
E. Jochemsz, A. May, A Polynomial Time Attack on Standard RSA with Private CRT-Exponents Smaller than N 0. 073, Advances in Cryptology – Crypto 2007, Lecture Notes in Computer Science Vol. 4622, pp. 395–411, Springer, 2007
D. Boneh, G. Durfee, Y. Frankel, An attack on RSA given a small fraction of the private key bits, Advances in Cryptology – Asiacrypt ’98, Lecture Notes in Computer Science Vol. 1514, Springer, pp. 25–34, 1998
R. Steinfeld, Y. Zheng, On the Security of RSA with Primes Sharing Least-Significant Bits, Applicable Algebra in Engineering, Communication and Computing Vol. 15(3-4),pp. 179–200, 2004
N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, Proceedings of Cryptography and Coding, Lecture Notes in Computer Science Vol. 1355, Springer, pp. 131–142, 1997
M. van Hoeij, Factoring Polynomials and 0-1 Vectors, Cryptography and Lattice Conference (CaLC 2001), Lecture Notes in Computer Science Vol. 2146, Springer, pp. 45–50, 2001
M. van Hoeij, Factoring polynomials and the knapsack problem, J. Number Theory Vol. 95, pp. 167–189, 2002
J. Klüners, The van Hoeij algorithm for factoring polynomials, LLL+25 Conference in honour of the 25th birthday of the LLL algorithm, 2007
N. Howgrave-Graham, Approximate Integer Common Divisors, Cryptography and Lattice Conference (CaLC 2001), Lecture Notes in Computer Science Vol. 2146, Springer, pp. 51–66, 2001
A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, PhD thesis, University of Paderborn, 2003
J.-S. Coron, Finding Small Roots of Bivariate Integer Polynomial Equations Revisited, Advances in Cryptology – Eurocrypt 2005, Lecture Notes in Computer Science Vol. 3027, Springer, 2005
J.-S. Coron, Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach, Advances in Cryptology – Crypto 2007, Lecture Notes in Computer Science, Springer, 2007
P. Nguyen, D. Stehlé, Floating-Point LLL Revisited, Advances in Cryptology – Eurocrypt 2005, Lecture Notes in Computer Science Vol. 3494, pp. 215–233, Springer, 2005
D. Stehlé, Floating-Point LLL: Theoretical and Practical Aspects, LLL+25 Conference in honour of the 25th birthday of the LLL algorithm, 2007
J. Håstad, M. Näslund, The security of all RSA and discrete log bits, Journal of the ACM Vol. 51(2), pp. 187–230, 2004
M. Bellare, P. Rogaway, Optimal Asymmetric Encryption, Advances in Cryptology – Eurocrypt ’94, Lecture Notes in Computer Science Vol. 950, Springer, pp. 92–111, 1994
G. Gentry, The Geometry of Provable Security: Some Proofs of Security in which Lattices Make a Surprise Appearance, LLL+25 Conference in honour of the 25th birthday of the LLL algorithm, 2007
E. Fujisaki, T. Okamoto, D. Pointcheval, J. Stern, RSA-OAEP Is Secure under the RSA Assumption, Advances in Cryptology – Crypto 2001, Lecture Notes in Computer Science Vol. 2139, Springer, pp. 260–274, 2001
R. Fischlin, C.-P. Schnorr, Stronger Security Proofs for RSA and Rabin Bits, Journal of Cryptology Vol. 13(2), pp. 221–244, 2000
S. Micali, C.P. Schnorr, Efficient, Perfect Random Number Generators, Advances in Cryptology – Crypto 1988, Lecture Notes in Computer Science Vol. 403, pp. 173–198, Springer, 1988
D. Boneh, S. Halevi, N. Howgrave-Graham, The Modular Inversion Hidden Number Problem, Advances in Cryptology – Asiacrypt 2001, Lecture Notes in Computer Science Vol. 2248, Springer, pp. 36–51, 2001
M.K. Franklin, M. K. Reiter, A linear protocol failure for RSA with exponent three, Rump Session Crypto ’95, 1995
D. Coppersmith, M. K. Franklin, J. Patarin, and M. K. Reiter, Low-Exponent RSA with Related Messages, Advances in Cryptology – Eurocrypt ’96, Lecture Notes in Computer Science Vol. 1070, Springer, pp. 1–9, 1996
A. May, M. Ritzenhofen, Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know?, Practice and Theory in Public Key Cryptography – PKC 2008, Lecture Notes in Computer Science Vol. 4939, Springer, pp. 37–46, 2008
R. Rivest, A. Shamir, Efficient factoring based on partial information, Advances in Cryptology (Eurocrypt ’85), Lecture Notes in Computer Science Volume 219, pp. 81–95, Springer, 1985
D. Coppersmith, Factoring with a hint, IBM Research Report RC 19905, 1995
G.L. Miller, Riemann’s hypothesis and test for primality, STOC, pp. 234–239, 1975
J.-J. Quisquater, C. Couvreur, Fast decipherment algorithm for RSA public-key cryptosystem, Electronic Letters 18 (21), pp. 905–907, 1982
D. Bleichenbacher, A. May, New Attacks on RSA with Small Secret CRT-Exponents, Practice and Theory in Public Key Cryptography – PKC 2006, Lecture Notes in Computer Science Vol. 3958, pp. 1–13, Springer, 2006
J. Blömer, A. May, New Partial Key Exposure Attacks on RSA, Advances in Cryptology – Crypto 2003, Lecture Notes in Computer Science Vol. 2729, pp. 27–43, Springer, 2003
M. Ernst, E. Jochemsz, A. May, B. de Weger, Partial Key Exposure Attacks on RSA up to Full Size Exponents, Advances in Cryptology – Eurocrypt 2005, Lecture Notes in Computer Science Vol. 3494, pp. 371–386, Springer, 2005
N. Howgrave-Graham, Computational Mathematics Inspired by RSA, PhD thesis, University of Bath, 1998
C. Jutla, On finding small solutions of modular multivariate polynomial equations, Advances in Cryptology – Eurocrypt ’98, Lecture Notes in Computer Science Vol. 1403, Springer, pp. 158–170, 1998
D. Bernstein, Reducing lattice bases to find small-height values of univariate polynomials. Algorithmic number theory, 2004
A. Bauer, A. Joux, Toward a rigorous variation of Coppersmith’s algorithm on three variables, Advances in Cryptology – Eurocrypt 2007, Lecture Notes in Computer Science, Springer, 2007
J. Blömer, A. May, A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers, Advances in Cryptology – Eurocrypt 2005, Lecture Notes in Computer Science Vol. 3494, pp. 251–267, Springer, 2005
G. Durfee, P. Nguyen, Cryptanalysis of the RSA Schemes with Short Secret Exponent from Asiacrypt ’99, Advances in Cryptology – Asiacrypt 2000, Lecture Notes in Computer Science Vol. 1976, Springer, pp. 14–29, 2000
J. Blömer, A. May, Low Secret Exponent RSA Revisited, Cryptography and Lattice Conference (CaLC 2001), Lecture Notes in Computer Science Volume 2146, Springer, pp. 4–19, 2001.
B. de Weger, Cryptanalysis of RSA with small prime difference, Applicable Algebra in Engineering, Communication and Computing ,Vol. 13(1), Springer, pp. 17–28, 2002
M.J. Hinek, Another Look at Small RSA Exponents, Topics in Cryptology – CT-RSA 2006, Lecture Notes in Computer Science Vol. 3860, pp. 82–98, 2006
A. May, Secret Exponent Attacks on RSA-type Schemes with Moduli N = p r q, Practice and Theory in Public Key Cryptography – PKC 2004, Lecture Notes in Computer Science Vol. 2947, Springer, pp. 218–230, 2004
N. Kunihiro, K. Kurosawa, Deterministic Polynomial Time Equivalence between Factoring and Key-Recovery Attack on Takagi’s RSA, Practice and Theory in Public Key Cryptography – PKC 2007, Lecture Notes in Computer Science, Springer, 2007
A. May, Cryptanalysis of Unbalanced RSA with Small CRT-Exponent, Advances in Cryptology – Crypto 2002, Lecture Notes in Computer Science Vol. 2442, Springer, pp. 242–256, 2002
H.-M. Sun, M.J. Hinek, and M.-E. Wu, An Approach Towards Rebalanced RSA-CRT with Short Public Exponent, revised version of [70], online available at http://www.cacr.math.uwaterloo.ca/techreports/2005/cacr2005-35.pdf
H.-M. Sun, M.-E. Wu, An Approach Towards Rebalanced RSA-CRT with Short Public Exponent, Cryptology ePrint Archive: Report 2005/053, online available at http://eprint.iacr.org/2005/053
S.D. Galbraith, C. Heneghan, and J.F. McKee, Tunable Balancing of RSA, Proceedings of ACISP 2005, Lecture Notes in Computer Science Vol. 3574, pp. 280–292, 2005
S.D. Galbraith, C. Heneghan, and J.F. McKee, Tunable Balancing of RSA, full version of [71], online available at http://www.isg.rhul.ac.uk/∼sdg/full-tunable-rsa.pdf
E. Jochemsz, A. May, A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants, Advances in Cryptology – Asiacrypt 2006, Lecture Notes in Computer Science Vol. 4284, pp. 267–282, Springer, 2006
D. Boneh, Simplified OAEP for the RSA and Rabin Functions, Advances in Cryptology – Crypto 2001, Lecture Notes in Computer Science Vol. 2139, pp. 275–291, Springer, 2001
C. Crépeau, A. Slakmon, Simple Backdoors for RSA Key Generation, Topics in Cryptology – CT-RSA 2003, Lecture Notes in Computer Science Vol. 2612, pp. 403–416, Springer, 2003
B. Santoso, N. Kunihiro, N. Kanayama, K. Ohta, Factorization of Square-Free Integers with High Bits Known, Progress in Cryptology, VIETCRYPT 2006, Lecture Notes in Computer Science Vol. 4341, pp. 115–130, 2006
M. Herrmann, A. May, Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits, Advances in Cryptology – Asiacrypt 2008, Lecture Notes in Computer Science, Springer, 2008
C.P. Schnorr, Factoring Integers and Computing Discrete Logarithms via Diophantine Approximations, Advances in Cryptology – Eurocrypt 1991, Lecture Notes in Computer Science, pp. 281–293, Springer, 1991
S.V. Konyagin, T. Steger, On polynomial congruences, Mathematical Notes Vol. 55(6), pp. 596–600, 1994
D. Bleichenbacher, P.G. Nguyen, Noisy Polynomial Interpolation and Noisy Chinese Remaindering, Advances in Cryptology – Eurocrypt 2000, Lecture Notes in Computer Science, pp. 53–69, Springer, 2000
J. Blömer, A. May, A Generalized Wiener Attack on RSA, Practice and Theory in Public Key Cryptography – PKC 2004, Lecture Notes in Computer Science Vol. 2947, pp. 1–13, Springer, 2004
D. Boneh, G. Durfee, Y. Frankel, Exposing an RSA Private Key Given a Small Fraction of its Bits, Full version of the work from Asiacrypt’98, available at http://crypto.stanford.edu/∼dabo/abstracts/bits{ _}of{ _}d.html, 1998
A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The number field sieve, In Proceedings of the 22nd Annual ACM Symposium on the Theory of Computation, pages 564–572, 1990
Acknowledgements
The author thanks Mathias Herrmann, Ellen Jochemsz, Phong Nguyen, Maike Ritzenhofen, and Damien Stehlé for comments and discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
May, A. (2009). Using LLL-Reduction for Solving RSA and Factorization Problems. In: Nguyen, P., Vallée, B. (eds) The LLL Algorithm. Information Security and Cryptography. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02295-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-02295-1_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02294-4
Online ISBN: 978-3-642-02295-1
eBook Packages: Computer ScienceComputer Science (R0)