Cryptology ePrint Archive: Report 2015/1000
Factoring as a Service
Luke Valenta and Shaanan Cohney and Alex Liao and Joshua Fried and Satya Bodduluri and Nadia Heninger
Abstract: The difficulty of integer factorization is fundamental to modern cryptographic security using RSA encryption and signatures. Although a 512-bit RSA modulus was first factored in 1999, 512-bit RSA remains surprisingly common in practice across many cryptographic protocols. Popular understanding of the difficulty of 512-bit factorization does not seem to have kept pace with developments in computing power. In this paper, we optimize the CADO-NFS and Msieve implementations of the number field sieve for use on the Amazon Elastic Compute Cloud platform, allowing a non-expert to factor 512-bit RSA public keys in under four hours for \$75. We go on to survey the RSA key sizes used in popular protocols, finding hundreds or thousands of deployed 512-bit RSA keys in DNSSEC, HTTPS, IMAP, POP3, SMTP, DKIM, SSH, and PGP.
Category / Keywords: public-key cryptography / RSA, factoring, cloud computing
Original Publication (with minor differences): Financial Cryptography and Data Security 2016
Date: received 14 Oct 2015, last revised 16 Jan 2016
Contact author: nadiah at cis upenn edu
Available format(s): PDF | BibTeX Citation
Note: Corrected a reference.
Version: 20160116:222454 (All versions of this report)
Short URL: ia.cr/2015/1000
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]