Breaking RSA Generically is Equivalent to Factoring

Divesh Aggarwal and Ueli Maurer

Advances in Cryptology - EUROCRYPT 2009, Lecture Notes in Computer Science, Springer-Verlag, vol. 5479, pp. 36-53, Apr 2009.

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 Citation

@inproceedings{AggMau09,
    author       = {Divesh Aggarwal and Ueli Maurer},
    title        = {Breaking RSA Generically is Equivalent to Factoring},
    editor       = {A. Joux},
    booktitle    = {Advances in Cryptology - EUROCRYPT 2009},
    pages        = 36-53,
    series       = {Lecture Notes in Computer Science},
    volume       = 5479,
    year         = 2009,
    month        = 4,
    publisher    = {Springer-Verlag},
}