What Is Public-Key Cryptography?

You sit in a café and pay for a book online. Your card number travels over the café’s wifi, through cables and through computers owned by companies you have never heard of. Anyone on that network can copy every message you send. You have never met the shop, and you never agreed on a secret code with it. So how can your card number arrive safely?

How can you send a secret to someone you have never met?

The card number is protected by public-key cryptography, a way of locking messages that uses two different keys instead of one. The public key locks a message, and its owner gives it to everyone. The private key unlocks the message, and its owner never shows it to anyone. Because the locking key can be public, two strangers do not need to meet first.

To see why this was a big step, look at the older way. For thousands of years, secret writing used one shared key for both locking and unlocking. If Ana wanted to write secretly to Ben, they first had to agree on that key in private. Armies, banks and embassies sent couriers with codebooks around the world for this reason. On the internet, where you talk to millions of strangers, that is impossible.

Public-key cryptography is easiest to picture with a padlock.

1. Ben buys many identical padlocks that all open with one key. He keeps the key.
2. He hands out open padlocks to anyone who asks, even to strangers.
3. Ana puts her letter in a box and snaps one of Ben’s padlocks shut. Closing it needs no key.
4. She sends the box by ordinary post. A thief can look at the box, but cannot open it.
5. Only Ben, who has the key, can open the box and read the letter.

The analogy has one weak point. A thief could take a spare padlock apart and use what he learns to make a key. On the internet, the public key is a number that every attacker can study for years. So the real lock must have a special property: knowing everything about it must still not reveal the key.

How can a number work like a padlock?

The lock uses a one-way function, which is a calculation that is easy to do and very hard to undo. Multiplication is the classic example. Multiplying two prime numbers is fast, even if each has 300 digits. Taking the result and finding the two primes again is so slow that no known method on ordinary computers can do it in any useful time. A prime is a whole number that only 1 and itself divide, such as 5, 11 or 23.

The best-known system of this kind is called RSA, after its inventors Ron Rivest, Adi Shamir and Leonard Adleman. It also uses “clock arithmetic”. On a clock, 3 hours after 11 o’clock is 2 o’clock, because you only keep the remainder after 12. RSA does the same with larger numbers. “13 mod 55” means the remainder after you divide by 55.

Here is Ben’s lock with tiny numbers, so that you can follow it by hand.

1. Ben picks two primes, 5 and 11, and multiplies them. 5 × 11 = 55.
2. From the two primes he computes a pair of numbers that fit together, here 3 and 27. To find the second number, 27, you need to know the primes 5 and 11.
3. Ben publishes 55 and 3. That is his public key. He keeps 27 secret. That is his private key.
4. Ana’s message is the number 7. She takes 7 to the power 3, so 7 × 7 × 7 = 343. The remainder after dividing by 55 is 13. She sends 13.
5. Ben takes 13 to the power 27 and keeps the remainder after dividing by 55. A computer does this in a moment. The result is 7, Ana’s message.

Anyone who sees 55, 3 and 13 can try to find 27. With 55 that takes seconds, because everyone can see that 55 = 5 × 11. But a real public number has about 600 digits. To get the private key you would first have to split that number into its two primes, and nobody knows how to do that fast.

How hard is it really? In August 1977, the writer Martin Gardner printed an RSA challenge in Scientific American. It was a secret message locked with a public number of 129 digits. It stayed unbroken for about 17 years. In 1994 a team using about 1,600 computers around the world finally split the number. The message read “The magic words are squeamish ossifrage”. Today’s keys are far longer than that one.

The same idea works in reverse. If Ben locks a number with his private key, anyone can unlock it with his public key. That proves the number came from Ben, because nobody else has his key. This is a digital signature. In our example, Ben signs the number 9 by computing 9 to the power 27, which leaves the remainder 4. Anyone can check it with Ben’s public key. 4 × 4 × 4 = 64, and 64 minus 55 is 9.

There is a second public-key method, and it is easier to picture with paint. Ana and Ben agree in public on a common colour, say yellow. Each one secretly adds their own colour and sends the mixture across. Each then adds their secret colour to the other’s mixture. Both end with the same brown. A listener only saw the yellow and the two mixtures. Separating mixed paint is hard, so the listener cannot make the same brown.

This method is called Diffie-Hellman key exchange. In the real version, the mixing is done with clock arithmetic, not with paint. The analogy fails in one place. A chemist could analyse real paint, while the mathematical version has no known shortcut. Ana and Ben now share a secret number that nobody else knows, and they use it as an ordinary shared key.

What public-key cryptography teaches you

The transferable insight is that some processes are easy in one direction and very hard in the other. Whenever you find such a process, you can build trust on it. Public-key cryptography uses that idea to let strangers share secrets and prove who they are.

• Your own phone. The padlock icon in your browser, messaging apps that call themselves “end-to-end encrypted”, and the passkeys that replace passwords on many sites all use public and private keys. Your device keeps the private key, and the website only stores the public one. So even a stolen website database contains nothing that lets someone sign in as you.
• Software you install. Your phone checks a digital signature before it accepts an update. A fake update cannot carry the maker’s signature, so the phone rejects it.
• Proving a record is genuine. The same need is very old. Medieval England kept debt records on split sticks, and only the two original halves fitted together, as What Were Tally Sticks? explains. A digital signature does the same job with numbers instead of wood.
• Trust between strangers. Yuval Noah Harari argues that human societies grew large once strangers found reasons to trust each other, a claim discussed in “Sapiens” by Yuval Noah Harari: Summary and Review. Online shopping, banking and messaging are a modern example, and public-key cryptography is the mathematics underneath that trust.

The one-way idea also helps outside computers. Many things in life are easy to do and hard to undo, such as breaking trust, sharing a photo or spending savings. Before you act, ask which direction is the easy one.

Where does public-key cryptography break?

This idea has three main limits.

The first limit concerns a common misconception. Many people think the padlock icon means a website is safe. It only means that your connection is locked to whoever holds that website’s private key. A fake shop can lock your card number just as well.

Behind this lies a deeper question. How do you know that a public key really belongs to Ben and not to someone pretending to be Ben? An attacker who sits between Ana and Ben could hand Ana his own public key. On the web, companies called certificate authorities confirm which key belongs to which domain name. That helps, but it moves the trust to those companies.

The second limit is that the security depends on an unproven assumption. Nobody has proved that splitting large numbers must stay hard. It is only true that nobody has found a fast method on ordinary computers. In 1994 the mathematician Peter Shor showed that a large enough quantum computer could split such numbers quickly. It could also break Diffie-Hellman. No quantum computer is that large yet. But messages recorded today could be read in the future, so in August 2024 the US standards agency NIST published the first new public-key standards designed to resist quantum computers.

The third limit is people and software. Most real attacks do not break the mathematics. They steal private keys, trick users or exploit errors in programs. Security engineers therefore think backwards and ask how they would attack their own system, a habit described in What Is Inversion? Thinking Backward to Avoid Mistakes.

Learn more

There is no single inventor of public-key cryptography. The idea was found twice, first in secret and then in public. At GCHQ, the British signals intelligence agency, James Ellis showed around 1970 that encryption without a shared secret was possible, but he had no practical method. In 1973 the young mathematician Clifford Cocks found one that was essentially RSA. In 1974 Malcolm Williamson found a method very close to Diffie-Hellman. So in secret, the two methods appeared in the opposite order to the public story. Their work stayed secret until December 1997, a few weeks after Ellis had died.

In public, Whitfield Diffie and Martin Hellman published “New Directions in Cryptography” in 1976, building on ideas by Ralph Merkle. Rivest, Shamir and Adleman described RSA in 1977, and Diffie and Hellman received the Turing Award, the highest prize in computer science, for 2015.

If you want the whole story of secret writing, from ancient ciphers to the GCHQ discovery, read Simon Singh’s The Code Book (Affiliate Link). It explains RSA and Diffie-Hellman for readers without a mathematics background.