Abstract
We present an elementary method to construct optimized lattices that are used for finding small roots of polynomial equations. Former methods first construct some large lattice in a generic way from a polynomial f and then optimize via finding suitable smaller dimensional sublattices. In contrast, our method focuses on optimizing f first which then directly leads to an optimized small dimensional lattice.
Using our method, we construct the first elementary proof of the Boneh-Durfee attack for small RSA secret exponents with d ≤ N 0.292. Moreover, we identify a sublattice structure behind the Jochemsz-May attack for small CRT-RSA exponents \(d_p, d_q \leq N^{0.073}\). Unfortunately, in contrast to the Boneh-Durfee attack, for the Jochemsz-May attack the sublattice does not help to improve the bound asymptotically. Instead, we are able to attack much larger values of d p ,d q in practice by LLL reducing smaller dimensional lattices.
Chapter PDF
Similar content being viewed by others
References
Boneh, D., Durfee, G.: Cryptanalysis of RSA with Private Key d Less than N \(^{\mbox{0.292}}\). In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 1–11. Springer, Heidelberg (1999)
Blömer, J., May, A.: Low Secret Exponent RSA Revisited. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 4–19. Springer, Heidelberg (2001)
Bleichenbacher, D., May, A.: New Attacks on RSA with Small Secret CRT-Exponents. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 1–13. Springer, Heidelberg (2006)
Coppersmith, D.: Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known. In: Maurer [Mau96], pp. 178–189 (1996)
Coppersmith, D.: Finding a Small Root of a Univariate Modular Equation. In: Maurer [Mau96], pp. 155–165 (1996)
Coppersmith, D.: Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. J. Cryptology 10(4), 233–260 (1997)
Howgrave-Graham, N.: Finding Small Roots of Univariate Modular Equations Revisited. In: Darnell, M.J. (ed.) Cryptography and Coding 1997. LNCS, vol. 1355, pp. 131–142. Springer, Heidelberg (1997)
Herrmann, M., May, A.: Attacking Power Generators Using Unravelled Linearization: When Do We Output Too Much? In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 487–504. Springer, Heidelberg (2009)
Jochemsz, E., May, A.: A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 267–282. Springer, Heidelberg (2006)
Jochemsz, E., May, A.: A Polynomial Time Attack on RSA with Private CRT-Exponents Smaller Than N \(^{\mbox{0.073}}\). In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 395–411. Springer, Heidelberg (2007)
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring Polynomials with Rational Coefficients. Mathematische Annalen 261(4), 515–534 (1982)
Maurer, U.M. (ed.): EUROCRYPT 1996. LNCS, vol. 1070. Springer, Heidelberg (1996)
Nguyen, P.Q., Stehlé, D.: An LLL Algorithm with Quadratic Complexity. SIAM J. Comput. 39(3), 874–903 (2009)
Quisquater, J.J., Couvreur, C.: Fast Decipherment Algorithm for RSA Public-key Cryptosystem. Electronics Letters 18, 905 (1982)
Wiener, M.J.: Cryptanalysis of Short RSA Secret Exponents. IEEE Transactions on Information Theory 36(3), 553–558 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Herrmann, M., May, A. (2010). Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA. In: Nguyen, P.Q., Pointcheval, D. (eds) Public Key Cryptography – PKC 2010. PKC 2010. Lecture Notes in Computer Science, vol 6056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13013-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-13013-7_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13012-0
Online ISBN: 978-3-642-13013-7
eBook Packages: Computer ScienceComputer Science (R0)