Paper 2008/260

Breaking RSA Generically is Equivalent to Factoring

Divesh Aggarwal and Ueli Maurer

Abstract

We show that a generic ring algorithm for breaking RSA in $\mathbb{Z}_N$ can be converted into an algorithm for factoring the corresponding RSA-modulus $N$. Our results imply that any attempt at breaking RSA without factoring $N$ will be non-generic and hence will have to manipulate the particular bit-representation of the input in $\mathbb{Z}_N$. This provides new evidence that breaking RSA may be equivalent to factoring the modulus.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. To appear in Eurocrypt, 2009
Keywords
FactoringRSAGeneric Algorithms
Contact author(s)
divesha @ inf ethz ch
History
2014-10-17: last of 3 revisions
2008-06-10: received
See all versions
Short URL
https://ia.cr/2008/260
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/260,
      author = {Divesh Aggarwal and Ueli Maurer},
      title = {Breaking RSA Generically is Equivalent to Factoring},
      howpublished = {Cryptology ePrint Archive, Paper 2008/260},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/260}},
      url = {https://eprint.iacr.org/2008/260}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.