# Breaking RSA may not be equivalent to factoring

**Authors:**

*D. Boneh and R. Venkatesan*

** 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 weakness in the RSA
system.

** Reference:**

In Proceedings *Eurocrypt '98*, Lecture Notes in Computer Science,
Vol. 1233, Springer-Verlag, pp. 59--71, 1998

**Full paper:**
gzipped-PostScript,
PDF
[first posted
3/1998 ]