Paper 2015/1000

Factoring as a Service

Luke Valenta, Shaanan Cohney, Alex Liao, Joshua Fried, 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.

Note: Corrected a reference.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Financial Cryptography and Data Security 2016
Keywords
RSAfactoringcloud computing
Contact author(s)
nadiah @ cis upenn edu
History
2016-01-16: last of 3 revisions
2015-10-15: received
See all versions
Short URL
https://ia.cr/2015/1000
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1000,
      author = {Luke Valenta and Shaanan Cohney and Alex Liao and Joshua Fried and Satya Bodduluri and Nadia Heninger},
      title = {Factoring as a Service},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1000},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1000}},
      url = {https://eprint.iacr.org/2015/1000}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.