eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2016/515

RSA Weak Public Keys available on the Internet

Mihai Barbulescu, Adrian Stratulat, Vlad Traista-Popescu, and Emil Simion


It is common knowledge that RSA can fail when used with weak random number generators. In this paper we present two algorithms that we used to find vulnerable public keys together with a simple procedure for recovering the private key from a broken public key. Our study focused on finding RSA keys with 512 and 1024 bit length, which are not considered safe, and finding a GCD is relatively fast. One database that we used in our study is made from 42 million public keys discovered when scanning TCP port 443 for raw X.509 certificates, between June 6, 2012 and August 4, 2013. Another database used in the study was made by crawling Github and retrieving the keys used by users to authenticate themselves when pushing to repositories they contribute to. We show that the percentage of broken keys with 512 bits is 3.7%, while the percentage of broken keys with 1024 bits is 0.05%. The smaller value is due to the fact that factorization of large numbers includes new prime numbers, unused in the small keys.

Available format(s)
Publication info
Published elsewhere. Minor revision. The post-proceedings of SECITC 2016 will be published by Springer: “Innovative Security Solutions for Information Technology and Communications” Date: received 23 May 2016
RSApublic keysweaknessvulnerabilitiesGCDinternet
Contact author(s)
esimion @ fmi unibuc ro
2016-05-29: received
Short URL
Creative Commons Attribution


      author = {Mihai Barbulescu and Adrian Stratulat and Vlad Traista-Popescu and Emil Simion},
      title = {RSA Weak Public Keys available on the Internet},
      howpublished = {Cryptology ePrint Archive, Paper 2016/515},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/515}},
      url = {https://eprint.iacr.org/2016/515}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.