Cryptology ePrint Archive: Report 2002/183

Simple backdoors to RSA key generation

Claude Crépeau and Alain Slakmon

Abstract: We present extremely simple ways of embedding a backdoor in the key generation scheme of RSA. Three of our schemes generate two genuinely random primes $p$ and $q$ of a given size, to obtain their public product $n=pq$. However they generate private/public exponents pairs $(d,e)$ in such a way that appears very random while allowing the author of the scheme to easily factor $n$ given only the public information $(n,e)$. Our last scheme, similar to the PAP method of Young and Yung, but more secure, works for any public exponent $e$ such as $3,17,65537$ by revealing the factorization of $n$ in its own representation. This suggests that nobody should rely on RSA key generation schemes provided by a third party.

Category / Keywords: public-key cryptography /

Date: received 26 Nov 2002

Contact author: crepeau at cs mcgill ca

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: To appear in proceedings of "Topics in Cryptology -- CT-RSA 2003", Marc Joye Editor, Springer-Verlag, 2003.

Version: 20021201:215042 (All versions of this report)

Short URL: ia.cr/2002/183

Discussion forum: Show discussion | Start new discussion