How can two strangers agree on a secret while everyone is listening?

Two strangers can agree on a secret in public by using keys that come in pairs. In public-key cryptography, each person has a private key they never share and a public key they can hand out to anyone. Anyone can use your public key to lock a message, but only your private key can unlock it. The public key can be broadcast to the world without weakening security.

This solved a problem as old as secret writing. For most of history, both sides used the same key, so they first had to exchange it safely, through some secure channel. That's impossible when your phone talks to a website it has never met.

The classic way to picture the trick is with paint. Alice and Bob publicly agree on a common colour. Each secretly picks a private colour, mixes it with the common one, and they swap their mixtures in plain sight. Then each adds their own secret colour to the mixture they received. Both end up with exactly the same final colour. An eavesdropper who saw everything would find it very hard to unmix the paints. With huge numbers instead of paint, it becomes impossible even for supercomputers.

Whitfield Diffie and Martin Hellman published such a method in 1976, and the RSA system followed in 1977. Surprise: British government mathematicians at GCHQ had found an equivalent system in secret in 1973. Today these ideas underpin the security of internet connections through standards like TLS.