Simple backdoors to RSA key generation

Claude Crépeau; Alain Slakmon

Paper 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 = p q$ . 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 given only the public information . Our last scheme, similar to the PAP method of Young and Yung, but more secure, works for any public exponent such as by revealing the factorization of in its own representation. This suggests that nobody should rely on RSA key generation schemes provided by a third party.

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

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): crepeau @ cs mcgill ca
History: 2002-12-01: received
Short URL: https://ia.cr/2002/183
License: CC BY

BibTeX

@misc{cryptoeprint:2002/183,
      author = {Claude Crépeau and Alain Slakmon},
      title = {Simple backdoors to {RSA} key generation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2002/183},
      year = {2002},
      url = {https://eprint.iacr.org/2002/183}
}