International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

FACTORING IS EQUIVALENT TO GENERIC RSA

Authors:
Divesh Aggarwal
Ueli Maurer
Download:
URL: http://eprint.iacr.org/2008/260
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-17937,
  title={FACTORING IS EQUIVALENT TO GENERIC RSA},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / RSA, factoring, generic algorithms},
  url={http://eprint.iacr.org/2008/260},
  note={Submitted to FOCS, 08 divesha@inf.ethz.ch 14038 received 8 Jun 2008},
  author={Divesh Aggarwal and Ueli Maurer},
  year=2008
}