Breaking RSA Generically is Equivalent to Factoring (original) (raw)

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 mathbbZN\mathbb{Z}_NmathbbZN can be converted into an algorithm for factoring the corresponding RSA-modulus NNN. Our results imply that any attempt at breaking RSA without factoring NNN will be non-generic and hence will have to manipulate the particular bit-representation of the input in mathbbZN\mathbb{Z}_NmathbbZN. This provides new evidence that breaking RSA may be equivalent to factoring the modulus.

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} }