Public-Key Cryptography and RSA

A trick of one-way arithmetic — multiplying two primes is easy, factoring their product is fiendishly hard — quietly underwrites every padlock on the internet.

For most of recorded history, every form of secret writing rested on one tacit assumption: that the sender and the receiver had already, at some earlier moment, agreed on a shared key. The Caesar cipher needed a shift. The Enigma machine needed a daily key sheet. A wartime spy needed a one-time pad printed on silk and smuggled across a border before transmission could begin. The trouble is obvious. To send a secret, you first had to deliver a secret. The chain of trust was only as strong as the weakest courier.

In the mid-1970s, with the faint outline of a global network starting to take shape, the problem turned existential. How could two computers that had never met agree on a key, over a wire that anyone could tap?

The locked-box problem

It helps to start with a parable. Suppose you want to send a friend a box, securely, through a postal service you do not trust. You have a strong padlock. You put your message in the box, snap the lock shut, and ship it. Your friend receives the box — and cannot open it, because you have the only key.

So try a different protocol. Your friend snaps their padlock onto the box and sends it back. You add your own padlock and return it. Your friend removes their padlock — the box still has yours, so it stays sealed — and ships it back one more time. You remove yours. The message has crossed the postal service three times, padlocked at every moment, and no key has ever been shared.

The chain of trust was only as strong as the weakest courier.

This is the conceptual trick. The mathematical version is more elaborate, but the spirit is the same: secrecy without prior agreement. The question after 1976 was no longer whether such schemes could exist. It was which piece of arithmetic could play the part of the padlock.

The Diffie–Hellman leap

In 1976, Whitfield Diffie and Martin Hellman published a paper called “New Directions in Cryptography.” They did not fully solve the problem. They reframed it. Split the key, they said, into two pieces. A public part that anyone can see, and a private part you keep to yourself. The public part is for locking. The private part is for unlocking. Like a mail slot — the world can drop letters in; only you can take them out.

The clever bit is that the two halves are bound together by a one-way function: a piece of arithmetic that is cheap to perform in one direction and brutally expensive to invert. Computing 17 × 19 = 323 is a few seconds with pencil and paper. Recovering “17 and 19” from 323 alone is harder, and as the numbers grow, harder at a punishing rate. Diffie and Hellman believed such functions existed in forms strong enough to build a cryptosystem on; they could not, at the time, produce one with quite the right algebraic shape. They had built the airframe and were waiting on the engine.

RSA — the math made concrete

A year later, three researchers at MIT — Ron Rivest, Adi Shamir, and Leonard Adleman — delivered the engine. RSA, named for the order their initials happened to fall in, is a concrete instance of Diffie and Hellman’s vision.

The recipe, as simply as it can be told. Pick two large prime numbers, p and q — hundreds of digits each, in practice. Multiply them: n = p · q. Pick a public exponent e; the value 65537 is the standard choice. Then use p and q to compute a matching private exponent d, such that for any number m less than n, the round trip (m^e)^d mod n returns m. The number d exists because of a piece of number theory from Euler; computing it requires knowing the factorization of n, which is to say, knowing p and q.

Publish the pair (n, e) as your public key. Keep d secret. To send you a message m, anyone in the world can compute c = m^e mod n and shout the result across the internet. To read it, you compute c^d mod n and recover m.

An eavesdropper sees c, n, and e. To decrypt, they need d. To compute d, they need p and q. To get p and q, they need to factor n. And factoring a number that is the product of two enormous primes is, as far as anyone publicly knows, computationally infeasible on a classical computer. For a 2048-bit n, the best known algorithms would take an age of the universe to grind through. The trapdoor exists, mathematically, but only the holder of p and q knows where it is. From the outside, the lock looks impenetrable.

What holds it up — and what threatens it

RSA’s security does not come from a proof. It comes from a conjecture: that factoring is hard. This is a special case of a deeper open problem — nobody has shown, or shown impossible, an efficient algorithm for integer factorization on a classical machine. Decades of attack have only chipped at the edges, finding faster sieves but never a method whose running time is polynomial in the number of digits. Every padlock on the internet, every banking session, every signed software update is a standing bet on the proposition that none ever will be.

There is one cloud on the horizon, and it has a name. In 1994, Peter Shor showed that a sufficiently large quantum computer could factor integers in polynomial time. The day that machine is built — and serious people now estimate it in decades rather than centuries — RSA breaks. So, with it, do the related schemes built on the discrete logarithm: Diffie–Hellman key exchange, elliptic-curve cryptography. The current scramble for “post-quantum” algorithms is a quiet, urgent attempt to replace the engine of internet trust before the day arrives.

The deeper idea, though, does not die with RSA. The proposition that two strangers can agree on a key without ever meeting — that secrecy in plain view is possible at all — survives in lattice-based schemes, in code-based schemes, in any system that finds a new one-way function and points it the right direction. The trick is no longer the surprise it was in 1976. It is now the floor on which the digital world stands.