### 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.

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

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

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.