Cryptology ePrint Archive: Report 2016/515

RSA Weak Public Keys available on the Internet

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

Abstract: 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.

Category / Keywords: RSA, public keys, weakness, vulnerabilities, GCD, internet

Original Publication (with minor differences): The post-proceedings of SECITC 2016 will be published by Springer: “Innovative Security Solutions for Information Technology and Communications” Date: received 23 May 2016

Date: received 25 May 2016

Contact author: esimion at fmi unibuc ro

Available format(s): PDF | BibTeX Citation

Version: 20160529:210037 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]