Cryptology ePrint Archive: Report 2012/064
Ron was wrong, Whit is right
Arjen K. Lenstra and James P. Hughes and Maxime Augier and Joppe W. Bos and Thorsten Kleinjung and Christophe Wachter
Abstract: We performed a sanity check of public keys collected on the web.
Our main goal was to test the validity of the assumption that different
random choices are made each time keys are generated.
We found that the vast majority of public keys
work as intended. A more disconcerting finding
is that two out of every one thousand RSA moduli that we collected
offer no security. Our conclusion is that the validity of the
assumption is questionable and that generating keys in the real world
for ``multiple-secrets'' cryptosystems such as RSA is significantly
riskier than for ``single-secret'' ones such as ElGamal or (EC)DSA
which are based on Diffie-Hellman.
Category / Keywords: public-key cryptography / Sanity check, RSA, 99.8\% security, ElGamal, DSA, ECDSA, (batch) factoring, discrete logarithm, Euclidean algorithm, seeding random number generators, $K_9$.
Date: received 14 Feb 2012, last revised 17 Feb 2012
Contact author: akl at epfl ch
Available format(s): PDF | BibTeX Citation
Version: 20120217:134904 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]