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