How public-key cryptography works

What problem does public-key cryptography solve?

Until the mid-1970s, every cipher was symmetric: sender and receiver used the same secret key. That raised an awkward question. How do two parties agree on a key before they have a secure way to talk? Historically the answer was to meet in person or rely on a trusted messenger, and the burden grew quickly. Every pair of people who wanted private conversations needed their own key, and keys ought to be changed often.

Public-key cryptography, also called asymmetric cryptography, removes that bottleneck. Each participant generates a pair of keys that are mathematically linked. The public half can be posted on a website or handed to anyone. Only the private half needs protecting, and it never has to travel.

How does it work, step by step?

The key pair is produced from a mathematical problem that is easy to compute in one direction and very hard to reverse, known as a one-way function. Two uses follow from that pair.

For encryption, anyone can scramble a message with the recipient's public key, producing ciphertext. Only the matching private key can turn it back into readable text. A newsroom, for example, can publish its public key so that sources can send material that an eavesdropper on the network cannot read.

For digital signatures, the roles flip. The signer combines a message with the private key to produce a signature, and anyone holding the public key can confirm that the two match. A software maker can ship its public key with its programs and sign every update; a computer receiving an update can then tell a genuine one from a forgery, as long as the private key stays secret.

In practice, asymmetric operations are much slower than symmetric ones. So protocols such as TLS, SSH and PGP use public-key methods only at the start, to agree on or transport a fresh symmetric key, and then switch to fast symmetric encryption for the rest of the session. These are called hybrid cryptosystems.

What does a worked example look like?

The best-known scheme, RSA, rests on multiplication being easy and factoring being hard. To build a tiny toy key, pick two primes, say 13 and 17. Multiplying them gives 221, and 221 becomes part of the public key. The primes themselves stay private, because the private key is derived from them.

Anyone can encrypt using 221 and a second public number. To decrypt, though, one needs information that follows from knowing 13 and 17. With a number as small as 221, an attacker could find the factors in moments. Real keys use primes so large that the public number runs to thousands of bits; a common size is 2,048 bits. Multiplying such primes takes a computer an instant, while recovering them from their product is believed to be out of reach. That gap is the whole trick.

Where did it come from and where is it used?

The idea was anticipated long before computers. William Stanley Jevons, writing in The Principles of Science in 1874, noted how hard it is to work out which two numbers were multiplied to give a large result. The public concept was published by Whitfield Diffie and Martin Hellman in 1976, and in 1977 three MIT researchers, Ron Rivest, Adi Shamir and Leonard Adleman, described RSA. Inside Britain's GCHQ, James Ellis had explored the idea around 1970 and Clifford Cocks devised an equivalent system in 1973, but that work stayed classified until 1997.

Today it underpins HTTPS through TLS, secure remote logins through SSH, signed and encrypted email through S/MIME and OpenPGP, email authentication through DKIM, and time-stamping and non-repudiation services.

Where does it fail or get misused?

The mathematics is rarely the weakest link. The chief risk is that a private key leaks, after which everything protected by it is exposed. Modern TLS limits the damage with forward secrecy, which creates temporary keys for each session.

A second risk is trust in the public key itself. If an attacker can swap in their own key while it is in transit, they can sit invisibly between two parties, a man-in-the-middle attack. Certificate authorities exist to vouch that a key belongs to who it claims, but that only moves the trust: a compromised authority can certify a fake key. PGP takes a different route, a decentralised web of trust built from personal endorsements.

Other limits are easy to overlook. Encryption usually hides the body of a message but not its metadata, such as who wrote to whom and when. Some once-promising schemes, such as knapsack-based ones, were broken outright. Side-channel attacks can leak secrets through how an implementation behaves. And many current algorithms are considered vulnerable to future quantum computers, which is why quantum-resistant schemes are under development.

What does it teach about thinking?

Public-key cryptography turns an asymmetry into an asset: some operations are cheap one way and practically impossible the other. Security then comes from making the attacker's side of that gap enormous, which is why longer keys add a margin that grows faster than the effort of using them.

Its history also shows that strong mathematics does not make a strong system. The breaches tend to come from people, processes and trust arrangements around the keys, so the useful question is always where the weakest link sits.

Questions people ask

The thinking behind it

• margin of safety
• systems thinking
• bottleneck

More algorithms, explained

• How Dijkstra's algorithm finds the shortest path
• How gradient descent works
• How Bayesian inference works
• How binary search works