Breaking RSA Generically is Equivalent to Factoring

Divesh Aggarwal; Ueli Maurer

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: Factoring RSA Generic 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: 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},
      url = {https://eprint.iacr.org/2008/260}
}