How Public-Key Cryptography Works: Two Keys, One Secret

Public-key cryptography, also called asymmetric cryptography, uses a pair of related keys: a public key that can be shared with anyone and a private key that its owner keeps secret. Whatever one key does, only the other can undo. This solves an old problem, which was how two people who have never met can communicate secretly. It underpins HTTPS, secure shell logins, signed software and more. This article explains the idea, the two main uses and the limits.

The problem it solved

Before the 1970s, all ciphers were symmetric: the sender and receiver used the same secret key. That meant the key had to be delivered securely in advance, which is hard at scale. If you wanted to talk privately to a thousand strangers, you would need a safe way to give each one a key first.

The US National Institute of Standards and Technology (NIST) defines public-key cryptography as a system using two related keys, one public and one private, where data protected with one key can be recovered only with the other, and where deriving the private key from the public key should be practically impossible. That last condition is the heart of the matter.

Encryption: lock with the public key

To send a secret message, you take the recipient's public key and encrypt the message with it. Anyone can do this, because the public key is meant to be shared. Only the holder of the matching private key can decrypt the result. A useful comparison is a padlock that anyone can snap shut, but that only its owner can open. Encryption hides the content, but it does not by itself prove who sent the message.

Signatures: prove it came from you

Digital signatures run the other way round. The sender signs a message with their private key. Anyone with the public key can check the signature. A valid signature shows that the message came from the holder of the private key and that it has not been altered since. The message itself is not hidden. Software updates and certificates commonly rely on signatures.

Key exchange and the hybrid approach

Public-key operations are much slower than symmetric ones. So real systems combine them. Wikipedia explains that protocols such as TLS, SSH and OpenPGP use public-key methods to agree a symmetric key, then encrypt the bulk of the data with that faster symmetric key.

One method for agreeing the key is Diffie-Hellman. Two parties swap public values, and each combines the other's public value with their own private one to compute the same shared secret, which an eavesdropper watching the exchange cannot easily work out. RSA, another well-known scheme, uses modular exponentiation with the product of two very large primes, and its security depends on how hard it is to factor large integers.

A short history

According to Wikipedia, British intelligence at GCHQ reached these ideas first, in secret. James Ellis conceived non-secret encryption in 1970, Clifford Cocks devised an RSA-like scheme in 1973 and Malcolm Williamson developed a Diffie-Hellman-like method in 1974, but all of it stayed classified until 1997. Publicly, Whitfield Diffie and Martin Hellman published a practical key-agreement method in 1976, and Rivest, Shamir and Adleman developed RSA in 1977 and published it in 1978.

Limits and weak points

• Private key theft. Whoever obtains a private key can read what it protects. Forward secrecy reduces this by using short-lived keys for each session.
• Fake public keys. If an attacker swaps in their own public key, they can sit between two people unnoticed. This is a man-in-the-middle attack, and it is why keys must be shown to be authentic.
• Trust in authorities. On the web, certificate authorities vouch for keys. A compromised authority can issue fraudulent certificates.
• Quantum computers. Many current asymmetric algorithms are considered vulnerable to a large enough quantum computer, which has driven work on quantum-resistant schemes.
• Metadata. Encryption usually leaves sizes, timing and addresses visible.

Where you meet it

Every time a browser shows a padlock, public-key methods have been used to check the site's identity and set up a session key. They also sit behind secure shell logins, signed emails, signed software and some digital currencies. The core idea is the same everywhere: a pair of keys, one open and one secret, where the maths makes it impractical to get from one to the other.

Sources

• Public-key cryptography, Wikipedia
• Public key cryptography, NIST Computer Security Resource Center glossary