Public-key cryptography

For thousands of years, sending a secret meant first sharing a key in private. In the 1970s, cryptographers found a way around that, and it's the reason you can shop, bank and message securely with people and companies you've never met.

The key problem

Classic encryption is symmetric: the same key locks and unlocks. It's fast and strong. AES, which protects almost all data today, works this way. But both sides need the same key before they start, and handing it over is exactly the hard part. If you could pass a key secretly, you could probably pass the message secretly too.

It also scales badly. Every pair of people who want to talk privately needs their own key.

In 1976, Whitfield Diffie and Martin Hellman published the idea that changes this: give each person a pair of keys. One half is public and can be shown to the world. The other is private and never leaves its owner. A year later, Ron Rivest, Adi Shamir and Leonard Adleman published RSA, the first practical way to do it. (Researchers at GCHQ had found the same ideas a few years earlier, but kept them secret until 1997.)

Open padlocks

Here's the classic picture. Bob buys a big bag of identical padlocks. He keeps the only key, and leaves open padlocks in a public pile where anyone can take one. Snapping a padlock shut doesn't need the key; opening it does.

That last question is the one people forget. Public-key cryptography moves the problem from “how do I share a secret key?” to “how do I know this public key really belongs to Bob?” That second problem is much easier, but it still has to be solved. We'll come back to it at the end.

Two keys, two jobs

Real key pairs aren't padlocks. They're numbers with a mathematical link: it's easy to compute the public key from the private one, and practically impossible to go the other way. That one-way link gives two different abilities:

A useful way to remember it: the private key is for the things only you should be able to do, reading your post and signing your name. Everything anyone may do, sending you secrets and checking your signature, uses your public key.

RSA by hand

RSA's one-way link comes from multiplication. Multiplying two large primes is instant. Splitting the result back into those two primes, called factoring, is extraordinarily slow. RSA builds a key pair so that knowing the primes lets you undo encryption, and not knowing them doesn't.

1. Pick two secret primes, p and q Multiply them to get n. This n is public.
2. Pick the public exponent e Usually 65537 in real life. The public key is the pair (n, e).
3. Work out the private exponent d d is chosen so that raising to the power e and then to the power d brings you back where you started. Computing d needs p and q. The private key is (n, d).
4. Encrypt and decrypt To encrypt a number m: c = m^e mod n. To decrypt: m = c^d mod n.

Two lessons from this toy. First, with small primes, factoring is instant, so the private key falls out immediately. Real RSA uses primes over 300 digits long. The largest RSA number ever publicly factored, RSA-250 in 2020, has 250 digits and took about 2,700 years of computer time. A standard 2048-bit key has 617.

Second, look at the repeated letters. Textbook RSA always encrypts the same input to the same output, so an eavesdropper can spot patterns. Real RSA adds random padding, called OAEP for encryption and PSS for signatures, so the same message encrypts differently every time. Never use RSA without it.

Real signatures

Today most new systems use elliptic-curve keys instead of RSA, because they're much smaller for the same strength. Your browser can make and use them itself. The demo below generates a genuine ECDSA key pair on the P-256 curve, the same kind that signs many of the certificates your browser checks every day.

Change even one character, “£20” to “£200”, and verification fails. Sign the same message twice and the signature changes each time, because ECDSA mixes in a fresh random number, yet both verify. Notice what the signature doesn't do: it doesn't hide the message. Signing proves who wrote it; encryption keeps it secret. Real systems usually need both.

Why real systems mix both kinds

Public-key operations are hundreds or thousands of times slower than symmetric encryption, and some can only handle tiny amounts of data. So almost nothing encrypts a whole message with a public key. Instead, it uses hybrid encryption:

1. Make a random symmetric key A fresh AES key, used for this one message.
2. Encrypt the message with it AES is fast and can handle any amount of data.
3. Lock the AES key with the recipient's public key Only a 32-byte key needs public-key encryption. This is called wrapping the key.
4. Send both The recipient unwraps the AES key with their private key, then decrypts the message.

Every HTTPS connection works on this principle. In modern TLS the key is agreed with Diffie–Hellman rather than wrapped with RSA, but the shape is the same: public-key cryptography to set up a shared key, then fast symmetric encryption for everything else.

Whose key is this?

Public keys can be shared openly, but you still need to know they're genuine. If an attacker can slip you their key labelled “Bob”, every guarantee above quietly works for them instead. There are three common answers:

• Check it yourself. Messaging apps like Signal and WhatsApp let you compare a “safety number” derived from both keys, in person or over a call.
• Trust the first one you see. SSH remembers a server's key the first time you connect and warns you loudly if it ever changes.
• Have someone vouch for it. Websites use certificates: a public key signed by an authority your browser already trusts. That's the subject of the certificates lesson.

Why this matters

• Public keys solve key distribution. Strangers can communicate securely without ever meeting to swap a secret.
• One pair, two jobs. Encrypt to someone's public key; sign with your own private key.
• Security rests on one-way problems. Factoring for RSA, discrete logarithms for elliptic curves, and both need keys big enough to stay out of reach.
• The hard question moves. It's no longer “how do we share a key?” but “is this public key really theirs?”