RSA

In 1976, no one could have imagined that a research paper published by Whitfield Diffie and Martin Hellman would revolutionize the world of cryptography. Their publication, “New Directions in Cryptography,” introduced an idea that seemed purely theoretical: asymmetric cryptography. Until that date, all cryptographic systems operated on a single principle: two people wishing to communicate securely first had to meet to exchange a secret key. This constraint paralyzed the development of digital communications.

The trio of researchers—Diffie, Hellman, and Ralph Merkle—proposed three concepts that would revolutionize the field: public-key encryption, digital signatures, and key exchange. Their paper, however, contained only one concrete implementation: the key exchange method that would bear their names. This Diffie-Hellman protocol constituted the first practical method for establishing a shared secret without prior meeting.

The following year, three researchers from MIT would take the decisive step. Ron Rivest, Adi Shamir, and Len Adleman formed a team with complementary talents. Rivest excelled at applying theoretical concepts to concrete problems. He devoured scientific literature and generated a constant stream of new ideas. Shamir possessed that rare ability to pierce through to the essence of a problem beyond its apparent complexity. Adleman, a rigorous mathematician, evaluated each proposition with the precision of a Swiss watchmaker.

For months, the trio explored various avenues without success. Then came that April evening in 1977. Rivest had spent the Passover evening at a student’s home, where they had shared Manischewitz wine. Back home, unable to sleep, he settled on his couch with a mathematics textbook. The question that had obsessed him for a year turned over in his mind: does there exist a mathematical function that is easy to compute in one direction but impossible to reverse without particular information? By sunrise, Rivest had drafted the entire paper describing the RSA system.

The genius of this discovery lies in its conceptual simplicity. The RSA system relies on a fundamental arithmetic property: multiplying two prime numbers is child’s play, but finding those numbers from their product is a nightmare when they reach a respectable size. The system generates two mathematically linked keys: a public key that anyone can know, and a private key that only its owner possesses. What is encrypted with the first can only be decrypted with the second.

To demonstrate their confidence in this new system, the three inventors launched a bold challenge in the pages of Scientific American. They published a 129-digit number, the product of two secret prime numbers, accompanied by an encrypted message. One hundred dollars awaited whoever could decipher it before April 1, 1982. This wager testified to their conviction in the mathematical robustness of their creation.

RSA-129 would resist well beyond the fixed deadline. It would take until 1994 to see this numerical giant collapse under the coordinated assault of 600 people spread across 24 countries. Arjen Lenstra, Paul Leyland, Michael Graff, and Derek Atkins orchestrated this collaborative enterprise that mobilized 1,600 computers for seven months. The secret message revealed—“THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE”—rewarded this technical feat with poetry of rather relative quality.

This collective victory did not signal the death of RSA but illustrated the permanent evolution of the balance of power between cryptographers and cryptanalysts. Over the decades, numerous attacks emerged, often targeting implementation weaknesses rather than the mathematical foundations of the system. Michael Wiener demonstrated in 1990 that an excessively small private exponent compromises security. Paul Kocher revealed in 1996 that a smart card could betray its secret key through the simple time it takes to compute. Daniel Bleichenbacher discovered in 1998 that certain error messages divulge valuable information to a patient attacker.

These discoveries did not undermine the confidence placed in RSA, which became one of the pillars of the modern internet. Every time you connect to your online bank, make a purchase, or check your email, RSA works silently to protect your data. Its discreet yet omnipresent presence has made possible the explosion of e-commerce and the digitalization of financial services.

Yet, a sword of Damocles hangs over this cryptographic giant. In 1994, Peter Shor published an algorithm that could, on a sufficiently powerful quantum computer, efficiently factor very large numbers. This theoretical threat stimulates research in post-quantum cryptography, a race against time to develop new systems before quantum computers become reality.

Forty-five years after its birth, RSA retains its relevance and reliability. Its journey demonstrates that an innovation can transform society far beyond its creators’ initial intentions, as new cryptographic challenges emerge with the advent of the quantum era.