Paper 2012/064

Ron was wrong, Whit is right

Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Sanity checkRSA99.8\% securityElGamalDSAECDSA(batch) factoringdiscrete logarithmEuclidean algorithmseeding random number generators$K_9$.
Contact author(s)
akl @ epfl ch
History
2012-02-17: last of 2 revisions
2012-02-14: received
See all versions
Short URL
https://ia.cr/2012/064
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/064,
      author = {Arjen K.  Lenstra and James P.  Hughes and Maxime Augier and Joppe W.  Bos and Thorsten Kleinjung and Christophe Wachter},
      title = {Ron was wrong, Whit is right},
      howpublished = {Cryptology ePrint Archive, Paper 2012/064},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/064}},
      url = {https://eprint.iacr.org/2012/064}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.