Secrets Between Strangers: How Public-Key Cryptography Works

Every time you buy something online, your computer and a server you have never met agree on a secret in full view of anyone watching the wire, and use it to scramble your card number beyond recovery. This should not be possible. For thousands of years, secret communication ran on a shared key: a code, a cipher wheel, a password that both sides knew in advance and kept hidden from everyone else. The catch was always the same. Before you could send a secret message, you first had to deliver the key, and delivering the key was itself a secret you had to protect. Spies met in person, diplomats used locked pouches, banks shipped codebooks under guard. If an enemy intercepted the key, the whole system fell. This is the key distribution problem, and until the 1970s it looked like an unavoidable cost of secrecy.

The breakthrough was an idea so counterintuitive that it took a while to be believed: that two people could establish a shared secret over a channel an eavesdropper was listening to the entire time, without ever having met. In 1976 Whitfield Diffie and Martin Hellman published a paper, plainly titled New Directions in Cryptography, that laid out the concept of public-key cryptography. The following year, three researchers at MIT, Ron Rivest, Adi Shamir, and Leonard Adleman, turned the concept into a concrete, workable system. Their initials gave it its name: RSA.

The trick rests on splitting the key in two. Instead of a single secret shared by both parties, each person has a pair of keys that belong together. One is public, and you can hand it to anyone, print it on a business card, post it on a website. The other is private, and you tell it to no one. The two keys are mathematically linked so that a message scrambled with the public key can only be unscrambled with the matching private key, and not even with the public key that locked it. Anyone can send you a secret by encrypting it with your public key. Only you, holding the private key, can read it. The lock and the key to open it are different objects, which is the whole point. You can give away as many copies of the open padlock as you like, and none of them helps anyone pick it.

What makes this possible is a special kind of mathematical operation, sometimes called a trapdoor one-way function. A one-way function is easy to compute in one direction and very hard to reverse, like mixing two colors of paint: simple to combine, painful to separate. A trapdoor function adds a secret shortcut that makes the reverse easy if and only if you know it. For RSA, the one-way operation is multiplication of large prime numbers. Multiplying two big primes together to get their product is quick, the kind of thing a computer does instantly. Going the other way, taking a large number and finding which two primes were multiplied to make it, is brutally hard. There is no known fast method to factor a number with hundreds of digits, and people have tried for a long time. The product of the two primes is, in effect, public. The two primes themselves are the trapdoor, the private secret.

The actual mechanism is short to state, if not to fully prove. You pick two enormous prime numbers and multiply them to get a number used in the public key. You then choose the keys so that encrypting a message amounts to raising its numeric form to a public power and taking the remainder when divided by that large product, an operation called modular exponentiation that computers handle easily. Decrypting reverses it using a private power that is derived from the two original primes. Anyone who could factor the public product back into its two primes could compute that private power and read everything. No one can, at least not in any practical amount of time, and so the system holds. The security of your bank session rests, quite literally, on the fact that factoring large numbers is slow.

There is a historical footnote that complicates the usual credit. It later emerged that mathematicians at the British signals intelligence agency, GCHQ, had worked out an equivalent system a few years earlier. Clifford Cocks devised essentially the RSA algorithm in 1973, but the work was classified and stayed secret until 1997. So the public invention by Rivest, Shamir, and Adleman was, unknown to them, a rediscovery. Because their version was published and free to build on, it is the one that changed the world, which says something about the difference between knowing a thing and being able to use it.

Public-key cryptography does more than hide messages. The same machinery, run in reverse, produces digital signatures. If you scramble something with your private key, anyone can use your public key to check that it unscrambles correctly, which proves it could only have come from you. That is how your browser confirms that the website claiming to be your bank really holds the matching private key, and how software updates prove they came from their actual maker rather than an impostor. Encryption protects secrecy. Signatures protect authenticity, and the modern internet needs both.

In practice the systems you use combine ideas. Public-key methods are relatively slow, so a typical secure connection uses RSA or a related scheme only to agree on a fresh shared key at the start, then switches to a fast traditional cipher for the bulk of the conversation. The public-key step solves the old key distribution problem once, at the beginning, and the rest is ordinary scrambling with a key that no eavesdropper ever saw. The little padlock icon in your browser is shorthand for this whole dance having completed successfully.

There is a cloud on the horizon worth naming. RSA is safe only because factoring is hard for ordinary computers. A sufficiently large quantum computer running an algorithm devised by Peter Shor in 1994 could factor those numbers efficiently, which would break RSA outright. Such machines do not yet exist at the needed scale, but the threat is taken seriously enough that cryptographers are now designing and standardizing post-quantum schemes built on harder problems, so that the secrets of the next era do not depend on a wall that a future computer could walk through. For now, though, the ordinary miracle holds: every day, billions of strangers share secrets across an open network, and the eavesdroppers, listening to every bit, learn nothing.