What is public key cryptography? Keys, locks and trust

Public key cryptography is a way of securing messages with a matched pair of keys: a public key you can hand to anyone and a private key only you keep. What one key locks, only the other can unlock. That lets two strangers exchange secrets, and prove who sent what, without ever having met to agree on a shared password.

In short

• Each person has two linked keys: a public one to share freely and a private one never shown to anyone.
• Lock a message with someone's public key and only their private key opens it; sign with your private key and anyone can check it with your public key.
• It secures web browsing, messaging apps and every crypto wallet, and it rests on math problems that are easy one way and very hard to reverse.

What problem does it solve?

For most of history, encryption was symmetric: the same key locked and unlocked a message. That works if two people can meet first and agree on the key. It fails on the internet, where you want to talk securely to a bank or a shop you have never dealt with, over wires anyone might be listening to. Sending the key along with the message would hand it to the eavesdropper.

In 1976, Whitfield Diffie and Martin Hellman published New Directions in Cryptography, which showed that two parties could agree on a secret over an open channel, and proposed keys that come in public and private halves. A year later, Ron Rivest, Adi Shamir and Leonard Adleman found a practical way to build such keys, now called RSA after their initials. The idea had been found first in secret: at Britain's signals intelligence agency, GCHQ, James Ellis conceived of "non-secret encryption", his colleague Clifford Cocks worked out what became known as RSA in 1973, and Malcolm Williamson then devised a method of key exchange. The work stayed classified until it was announced in December 1997, according to GCHQ.

How does it work, in plain terms?

Think of a padlock that anyone can snap shut but only you can open. You hand out copies of the open padlock, which is your public key. Anyone who wants to send you something puts it in a box and snaps your padlock on. Once locked, not even the sender can open it again. Only your key, the private one, opens the box.

The math behind it uses a trapdoor: an operation that is easy to do and very hard to undo unless you know a secret. In RSA, the trapdoor is multiplication. Multiplying two large prime numbers takes a computer a fraction of a second. Taking the product apart again, when each prime is hundreds of digits long, would take longer than anyone can wait. The public key is built from the product; the private key is built from the two primes.

A worked example with small numbers

Real keys use numbers more than 600 digits long, but the steps are the same with tiny ones, as set out in the original RSA paper.

1. Pick two primes: 61 and 53. Multiply them: n = 3,233.
2. Work out (61 − 1) × (53 − 1) = 3,120. Pick a number with no common factor with it: e = 17. The public key is the pair (3,233, 17).
3. Find the number d that makes 17 × d leave a remainder of 1 when divided by 3,120. That is d = 2,753, since 17 × 2,753 = 46,801 = 15 × 3,120 + 1. The private key is 2,753.
4. To send the message 65, raise it to the 17th power and keep the remainder after dividing by 3,233. The result is 2,790. That is the locked message.
5. To unlock it, raise 2,790 to the power 2,753 and take the remainder after dividing by 3,233. Out comes 65.

Anyone can see 3,233 and 17. To find 2,753 they would need to know that 3,233 is 61 × 53, which is trivial here and practically impossible when the primes are each about 300 digits long. The security is the gap between how easy it is to multiply and how hard it is to factor.

What is a digital signature?

Run the keys the other way and you get a signature. You lock a short fingerprint of a message with your private key, and anyone can unlock it with your public key. If it opens, it can only have been locked by you, and the message can't have changed since. In the toy example above, signing the number 42 with the private key 2,753 gives 3,065, and anyone holding the public key can turn 3,065 back into 42 and see the match.

A common mix-up is to think the public key only encrypts and the private key only decrypts. For signatures it runs the opposite way: the private key signs and the public key checks. Many systems today use elliptic-curve keys rather than RSA, because they give the same strength with far shorter keys, and the US standard for signatures, FIPS 186-5, covers both.

Where do you already rely on it?

Every time a browser shows a padlock beside a web address, public key cryptography has just run. In HTTPS, the site proves who it is with a certificate, a public key signed by an authority the browser trusts, and the two sides use public key methods to agree on a fresh symmetric key. The rest of the visit is encrypted with that faster symmetric key. Public key math is slow, so it is used to set up the secret, not to carry every byte. The note on how the internet works follows that traffic from your device to the server.

Messaging apps with end-to-end encryption do the same between phones, so the company in the middle can't read the messages. Software updates are signed, so your computer can tell a real update from a tampered one.

And Bitcoin runs on signatures. An address is derived from a public key, and spending coins means signing a transaction with the matching private key, which is why a crypto wallet is really a keyring. Every node on the blockchain checks the signature with the public key before accepting the payment. Nobody needs to know who you are, only that you hold the key.

Can quantum computers break it?

In principle, yes, for the methods most used today. In 1994 the mathematician Peter Shor described an algorithm that a large enough quantum computer could use to factor big numbers and solve the related elliptic-curve problems quickly, which would break RSA and the elliptic-curve keys behind HTTPS and Bitcoin. No machine that large has been publicly shown.

In August 2024, the US National Institute of Standards and Technology published its first three post-quantum standards, FIPS 203, 204 and 205, built on math problems that quantum computers are not known to shortcut, and urged administrators to start switching to them immediately.

Still argued

When a quantum computer able to break today's keys will exist is genuinely uncertain. NIST's 2024 announcement noted that some experts predict one could appear within a decade; others think the engineering obstacles will take far longer, or may not be overcome. The reason to move early is that data recorded now could be decrypted later, once such a machine exists.

Check yourself

• With the page closed, explain why handing out your public key is safe.
• Which key signs a message, which checks it, and what does a valid signature prove?
• Why does HTTPS use public key cryptography only at the start of a connection?

Sources

• New Directions in Cryptography — Whitfield Diffie and Martin Hellman, IEEE Transactions on Information Theory, 1976
• A Method for Obtaining Digital Signatures and Public-Key Cryptosystems — Ron Rivest, Adi Shamir and Leonard Adleman, 1978
• James Ellis — GCHQ
• FIPS 186-5, Digital Signature Standard — National Institute of Standards and Technology, 2023
• NIST releases first 3 finalized post-quantum encryption standards — National Institute of Standards and Technology, 2024