Cryptology ePrint Archive: Report 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.

Category / Keywords: Factoring, RSA, Generic Algorithms

Publication Info: To appear in Eurocrypt, 2009

Date: received 8 Jun 2008, last revised 23 Jan 2009

Contact author: divesha at inf ethz ch

Available format(s): PDF | BibTeX Citation

Version: 20090123:174708 (All versions of this report)

Short URL: ia.cr/2008/260

Discussion forum: Show discussion | Start new discussion