Abstract
We provide evidence that breaking low-exponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking low-exponent RSA can be converted into an efficient factoring algorithm. Thus, in effect an oracle for breaking RSA does not help in factoring integers. Our result suggests an explanation for the lack of progress in proving that breaking rsa is equivalent to factoring. We emphasize that our results do not expose any specific weakness in the rsa system.
Chapter PDF
References
D. Boneh, R. Lipton, “Black box fields and their application to cryptography”, Proc. of Crypto '96, pp. 283–297.
D. Coppersmith, “Finding a small root of a univariate modular equation”, Proc. of Eurocrypt '96, pp. 155–165.
W. Diffie, M. Hellman, “New directions in cryptography”, IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.
J. Hastad, “Solving simultaneous modular equations of low degree”, SIAM Journal of Computing, vol. 17, pp 336–341, 1988.
S. Lang, “Algebra”, Addison-Wesley, 1993.
A. Lenstra, H.W. Lenstra, “Algorithms in Number Theory”, Handbook of Theoretical Computer Science (Volume A: Algorithms and Complexity), Elsevier and MIT Press, Ch. 12, pp. 673–715, 1990.
H. W. Lenstra, “Factoring integers with elliptic curves”, Annals of Math., Vol. 126, pp. 649–673, 1987.
U. Maurer, “Towards proving the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms”, Proc. of Crypto '94, pp. 271–281.
U. Maurer, S. Wolf, “Diffie-Hellman oracles”, Proc. of Crypto '96, pp. 268–282.
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.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boneh, D., Venkatesan, R. (1998). Breaking RSA may not be equivalent to factoring. In: Nyberg, K. (eds) Advances in Cryptology — EUROCRYPT'98. EUROCRYPT 1998. Lecture Notes in Computer Science, vol 1403. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054117
Download citation
DOI: https://doi.org/10.1007/BFb0054117
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64518-4
Online ISBN: 978-3-540-69795-4
eBook Packages: Springer Book Archive