Abstract
We show that if the private exponent d used in the RSA public-key cryptosystem is less than N 0.292 then the system is insecure. This is the first improvement over an old result of Wiener showing that when d < N 0.25 the RSA system is insecure. We hope our approach can be used to eventually improve the bound to d < N 0.5.
Supported by DARPA.
Supported by Certicom and an NSF Graduate Research Fellowship.
Chapter PDF
References
D. Bleichenbacher, “On the security of the KMOV public key cryptosystem”, Proc. of Crypto’ 97, pp. 235–248.
D. Coppersmith, “Small solutions to polynomial equations, and low exponent RSA vulnerabilities”, J. of Cryptology, Vol. 10, pp. 233–260, 1997.
J. Hastad, “Solving simultaneous modular equations of low degree”, SIAM Journal of Computing, vol. 17, pp. 336–341, 1988.
N. Howgrave-Graham, “Finding small roots of univariate modular equations revisited”, Proc. Of Cryptography and Coding, LNCS 1355, Springer-Verlag, 1997, pp. 131–142.
C. Jutla, “On finding small solutions of modular multivariate polynomial equations”, Proc. of Eurocrypt’ 98, pp. 158–170.
A. Lenstra, H. Lenstra, and L. Lovasz. Factoring polynomial with rational coefficients. Mathematiche Annalen, 261:515–534, 1982.
L. Lovasz, “An algorithmic theory of numbers, graphs and convexity”, SIAM lecture series, Vol. 50, 1986.
R. Rivest, A. Shamir, L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems”, Communications of the ACM, vol. 21, pp. 120–126, 1978.
E. Verheul, H. van Tilborg, “Cryptanalysis of less short RSA secret exponents”, Applicable Algebra in Engineering, Communication and Computing, Springer-Verlag, vol. 8, pp. 425–435, 1997.
M. Wiener, “Cryptanalysis of short RSA secret exponents”, IEEE Transactions on Info. Th., Vol. 36, No. 3, 1990, pp. 553–558.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boneh, D., Durfee, G. (1999). Cryptanalysis of RSA with Private Key d Less than N 0.292 . In: Stern, J. (eds) Advances in Cryptology — EUROCRYPT ’99. EUROCRYPT 1999. Lecture Notes in Computer Science, vol 1592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48910-X_1
Download citation
DOI: https://doi.org/10.1007/3-540-48910-X_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65889-4
Online ISBN: 978-3-540-48910-8
eBook Packages: Springer Book Archive