Breaking RSA May Be As Difficult As Factoring

Daniel R.  L.  Brown

Paper 2005/380

Breaking RSA May Be As Difficult As Factoring

Daniel R. L. Brown

Abstract

If factoring is hard, this paper shows that straight line programs cannot efficiently solve the low public exponent RSA problem. More precisely, no efficient algorithm can take an RSA public key as input and then output a straight line program that efficiently solves the low public exponent RSA problem for the given public key --- unless factoring is easy.

Note: Slight correction: alternative strategy if g(X) not square-free.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: RSA Problem Factoring Straight Line Programs
Contact author(s): dbrown @ certicom com
History: 2008-01-07: last of 6 revisions; 2005-10-23: received; See all versions
Short URL: https://ia.cr/2005/380
License: CC BY

BibTeX

@misc{cryptoeprint:2005/380,
      author = {Daniel R.  L.  Brown},
      title = {Breaking RSA May Be As Difficult As Factoring},
      howpublished = {Cryptology ePrint Archive, Paper 2005/380},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/380}},
      url = {https://eprint.iacr.org/2005/380}
}