Cryptology ePrint Archive: Report 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.
Category / Keywords: public-key cryptography / RSA Problem, Factoring, Straight Line Programs
Date: received 20 Oct 2005, last revised 7 Jan 2008
Contact author: dbrown at certicom com
Available format(s): PDF | BibTeX Citation
Note: Slight correction: alternative strategy if g(X) not square-free.
Version: 20080107:205109 (All versions of this report)
Short URL: ia.cr/2005/380
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]