Cryptography Flashback
Revisiting factoring challenges and Martin Gardner's RSA article
The world became aware of public key cryptography after the publication of Martin Gardner’s Scientific American article about RSA encryption. It’s fun to look back at Gardner’s article almost 50 years later. Aspects of the article now seem quaint, but it accurately conveyed the potential of public key cryptography.
The security of RSA encryption depends on the difficulty of factoring the product of large prime numbers. Prime factoring algorithms have gotten much better over the last 50 years, and of course so has computing hardware. Prime numbers need to have 5 to 10 times as many digits as was considered adequate in 1977, and there are other caveats, but RSA remains secure given some modifications.
RSA Laboratories issued several factoring challenges to demonstrate/test the difficulty of factoring large numbers. The smallest of these, RSA-100, contained 100 digits. I factored that number in 23 minutes yesterday on a $600 computer. The original factorization took a couple days on a $500,000 computer.
Many of the RSA factoring challenges have been computed using a library called CADO-NFS. That’s the software I used in the example above. The number field sieve algorithm used in CADO-NFS is the most efficient known algorithm for factoring numbers with over 100 digits, but not for smaller numbers.
Factoring RSA-100 with CADO-NFS took 23 minutes. I tried the same task in Mathematica, and killed the process after it ran for two hours.
However, when factoring the 76-digit numbers mentioned previously, Mathematica was about six times faster than CADO-NFS.
Martin Gardner’s article contained a decryption challenge that supposedly take forever to break. It was broken 16 years later. And in 2015 someone redid the same factorization using six CPU-hours. Despite these unforseen speedups, RSA encryption remains secure if you use longer keys.
RSA with 3072-bit keys, about seven times longer than the key in Martin Gardner’s office, is believed to be secure for the next 15 years or longer, provided large-scale quantum computing doesn’t become practical in the mean time.
Thanks for reading. If you’d like my company’s help with a project, let’s talk.