International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Breaking RSA May Be As Difficult As Factoring

Authors:
Daniel R. L. Brown
Download:
URL: http://eprint.iacr.org/2005/380
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12714,
  title={Breaking RSA May Be As Difficult As Factoring},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / RSA Problem, Factoring, Straight Line Programs},
  url={http://eprint.iacr.org/2005/380},
  note={ dbrown@certicom.com 13250 received 20 Oct 2005, last revised 12 Apr 2006},
  author={Daniel R. L. Brown},
  year=2005
}