Public key cryptography came to the world’s attention via Martin Gardner’s Scientific American article from September 1977 on RSA encryption.
The article’s opening paragraph illustrates what a different world 1977 was in regard to computation and communication.
… in a few decades … the transfer of information will probably be much faster and much cheaper by “electronic mail” than by conventional postal systems.
Gardner quotes Ron Rivest [1] saying that breaking RSA encryption by factoring the product of two 63-digit primes would take about 40 quadrillion years. The article included a challenge, a message encrypted using a 129-digit key, the product of a 64-digit prime and a 65-digit prime. Rivest offered a $100 prize for decrypting the message.
Note the tension between Rivest’s estimate and his bet. It’s as if he were saying “Based on the factoring algorithms and computational hardware now available, it would take forever to decrypt this message. But I’m only willing to bet $100 that that estimate remains valid for long.”
The message was decrypted 16 years later. Unbeknownst to Gardner’s readers in 1977, the challenge message was
THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
encoded using 00 for space, 01 for A, 02 for B, etc. It was decrypted in 1993 by a group of around 600 people using around 1600 computers. Here is a paper describing the effort. In 2015 Nat McHugh factored the key in 47 minutes using 8 CPUs on Google Cloud.
The RSA algorithm presented in Gardner’s article is much simpler than it’s current implementaiton, though the core idea remains unchanged. Now we use much larger public keys, the product of two 1024 bit (308 digit) primes or larger. Also, RSA isn’t used to encrypt messages per se; RSA is used to exchange symmetric encryption keys, such as AES keys, which are then used to encrypt messages.
RSA is still widely used, though elliptic curve cryptography (ECC) is taking its place, and eventually both RSA and ECC will presumably be replaced with post-quantum methods.
More RSA posts
[1] I met Ron Rivest at the Heidelberg Laureate Forum in 2013. When he introduced himself I said something like “So you’re the ‘R’ in RSA?” He’s probably tired of hearing that, but if so he was too gracious to show it.