Paper 2016/515
RSA Weak Public Keys available on the Internet
Mihai Barbulescu, Adrian Stratulat, 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.
Metadata
- Available format(s)
-
PDF
- 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
- Keywords
- RSApublic keysweaknessvulnerabilitiesGCDinternet
- Contact author(s)
- esimion @ fmi unibuc ro
- History
- 2016-05-29: received
- Short URL
- https://ia.cr/2016/515
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/515,
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},
url = {https://eprint.iacr.org/2016/515}
}
