RSA Encryption: Secrets in Plain Sight

#TL;DR

Before 1976, every encryption system had the same fatal flaw: you needed a secret key, and both sides had to have it before they could talk securely. That meant couriers, sealed envelopes, pre-shared codebooks — none of which worked for a world where strangers needed to exchange credit card numbers over a public network. Diffie and Hellman proved a radical idea was possible: two people could agree on a shared secret without ever exchanging one. A year later, three MIT researchers — Rivest, Shamir, and Adleman — built the first practical system: RSA. The trick was a mathematical trapdoor. Multiplying two huge primes is trivial. Factoring the result back into those primes is, for all practical purposes, impossible. Every HTTPS connection you’ve ever made depends on this asymmetry.

#The Key Distribution Problem

Cryptography is ancient. Caesar shifted letters. The Enigma machine nearly won a war. But every system before the 1970s shared a crippling assumption: the sender and receiver already have the same key.

This is fine for generals with couriers. It’s a disaster for a network.

Imagine ARPANET in 1975. You want to send a classified message from UCLA to MIT. You encrypt it with a secret key. But how does MIT get that key? You can’t send it over the network — anyone listening would intercept it and read your message. You could mail it, or fly it out, but that defeats the point of having a network. And you’d need a different key for every pair of communicators. A network of 100 nodes would need 4,950 unique keys, each exchanged in advance.

This was called the key distribution problem, and cryptographers had been stuck on it for centuries. Every clever encryption scheme just moved the problem around — you still needed a secure channel to share the key, and if you already had a secure channel, why did you need encryption?

#A Paper That Changed Everything

In November 1976, Whitfield Diffie and Martin Hellman at Stanford published “New Directions in Cryptography” — one of the most important papers in the history of computer science.

Their insight was radical: what if encryption and decryption used different keys? One key locks the box. A completely different key opens it. You can publish the locking key to the world — nail it to a bulletin board, broadcast it on the radio — and only the person with the unlocking key can read the message.

They called this public-key cryptography. The concept was elegant and provably possible. But they didn’t have a working implementation. They’d proven the lock could exist. They hadn’t built one yet.

That challenge — find a mathematical function that’s easy to compute in one direction and practically impossible to reverse — was an open dare to every mathematician and computer scientist alive.

#A Passover at MIT

At MIT, three young researchers took the bait.

Ron Rivest was a computer scientist. Adi Shamir was a mathematician. Leonard Adleman was the skeptic — a theoretical computer scientist whose self-described role was to break whatever Rivest and Shamir came up with. The pattern was always the same: Rivest would propose a scheme, Shamir would help refine it, and Adleman would find the flaw. They went through dozens of attempts.

Then, in April 1977, Rivest stayed up late after a Passover seder, drinking wine and thinking about number theory. By 4 AM, he had a complete system — the math, the proof, the algorithm. He wrote it up and handed it to Adleman the next morning.

Adleman couldn’t break it. Nobody could.

The system was named RSA, after all three authors. Rivest and Shamir’s initials came first alphabetically, but Adleman initially declined to have his name on it — he thought it was “just a computer science paper.” Rivest insisted. It became one of the most cited papers in the field.

#The Trapdoor

RSA rests on a single asymmetry: multiplying is easy, factoring is hard.

Take two large prime numbers — call them p and q. Multiplying them is trivial, even for a 1977 computer:

p = 61
q = 53
n = p × q = 3233

Now forget p and q. Given only n = 3233, can you find the original primes? With small numbers, sure. But when p and q are each 300 digits long, the resulting n is 600 digits — and no known algorithm can factor it in any reasonable time. Not in a year. Not in the lifetime of the universe.

This is a trapdoor function: easy to fall through in one direction, practically impossible to climb back up.

Here’s how RSA turns that into encryption:

Key generation — the part you do once:

from math import gcd

# 1. Pick two primes (tiny ones here — real RSA uses 1024+ bit primes)
p, q = 61, 53
n = p * q          # 3233 — the modulus, part of both keys

# 2. Compute Euler's totient: how many numbers < n are coprime to n
phi = (p - 1) * (q - 1)  # 3120

# 3. Pick a public exponent e, coprime to phi
e = 17  # common choice; real implementations often use 65537

# 4. Compute the private exponent d: the modular inverse of e mod phi
#    i.e., find d such that (e * d) % phi == 1
d = pow(e, -1, phi)  # 2753

# Public key:  (e=17, n=3233)   — publish this to the world
# Private key: (d=2753, n=3233) — guard this with your life

Encryption — anyone can do this with your public key:

message = 65  # the number we want to encrypt (e.g., ASCII 'A')
ciphertext = pow(message, e, n)  # 65^17 mod 3233 = 2790

Decryption — only you can do this with your private key:

plaintext = pow(ciphertext, d, n)  # 2790^2753 mod 3233 = 65

The magic: 65 → 2790 → 65. The public key scrambled the message. The private key — which was never transmitted, never shared, never left your machine — unscrambled it.

An attacker who intercepts 2790 and knows the public key (17, 3233) would need to factor 3233 to recover d. For toy numbers, that’s trivial. For the 2048-bit keys used today, it’s computationally impossible.

#Digital Signatures: Proof You Wrote It

RSA has a second trick. If encryption goes public key → private key (anyone can lock, only you can unlock), then reversing the direction gives you digital signatures: private key → public key (only you can sign, anyone can verify).

# Signing: encrypt with YOUR private key
document_hash = 42
signature = pow(document_hash, d, n)  # only you can produce this

# Verification: decrypt with YOUR public key
verified = pow(signature, e, n)       # anyone can check this
assert verified == document_hash      # if it matches, you signed it

This solves a problem as old as writing: how do you prove a message wasn’t tampered with, and that it actually came from who it claims? Digital signatures underpin software updates, legal documents, cryptocurrency transactions, and every git commit you’ve ever signed.

#The NSA, the Patent, and the Fight Over Who Owns Math

RSA didn’t arrive quietly. The NSA — America’s signals intelligence agency — was deeply uncomfortable. They had built their power on the assumption that strong cryptography was a government monopoly. Civilians weren’t supposed to have it.

In 1977, an NSA employee wrote a letter to the IEEE warning that publishing cryptography research might violate the Arms Export Control Act — the same law that regulated missile technology. The implication: Rivest, Shamir, and Adleman could face prosecution for publishing a math paper.

The threat didn’t stick — the academic community pushed back hard — but it foreshadowed decades of conflict. In the 1990s, the Crypto Wars erupted when the US government tried to limit the key sizes civilians could use, mandate backdoors (the Clipper Chip), and classify encryption software as a munition. Phil Zimmermann was investigated for three years after releasing PGP (Pretty Good Privacy), which used RSA, as free software.

The cryptographers won. The government backed down. Strong encryption became legal for everyone. But the debate — should citizens have access to encryption the government can’t break? — never really ended. It echoes in every argument about encrypted messaging apps today.

#What RSA Got Right

RSA was published 49 years ago. Computers are billions of times faster. And RSA still works — not because attackers haven’t tried, but because the mathematical asymmetry at its core is genuinely hard:

• The key distribution problem is solved — you can publish your public key on a billboard, and the system remains secure. Two strangers can communicate privately without ever meeting. This is the foundation of internet commerce.
• Authentication, not just secrecy — digital signatures proved that public-key cryptography wasn’t just about hiding messages. It was about proving identity, verifying integrity, and building trust between machines that have never met.
• Defense in depth — RSA doesn’t work alone in practice. Modern TLS uses RSA (or its elliptic-curve successors) to exchange a session key, then switches to faster symmetric encryption like AES for the actual data. This layered approach means the system degrades gracefully if any single component weakens.
• Math as infrastructure — before RSA, cryptography was spycraft. After RSA, it was computer science. The algorithm turned a branch of classified military research into a public discipline that anyone could study, improve, and build on.

There’s a caveat on the horizon. RSA’s security rests on the assumption that factoring large numbers is computationally infeasible. Quantum computers, running Shor’s algorithm, could change that — factoring a 2048-bit number in hours instead of millennia. That hasn’t happened yet, but the cryptography community is already preparing, designing post-quantum algorithms that don’t depend on factoring. The trapdoor that’s held for fifty years may need to be replaced — but the idea of public-key cryptography, the revolution Diffie, Hellman, Rivest, Shamir, and Adleman started, is permanent.