Pointer Walk

Public-Key Cryptography

A lock anyone can close and only one person can open. How two keys solve the problem of sharing a secret with a stranger.

SecurityIntermediate10 min read

The key problem

Encryption has been around for thousands of years, and for nearly all that time it worked one way: the sender and the receiver share a secret key. The same key scrambles the message and unscrambles it. This is symmetric encryption. It is fast and, done properly, unbreakable in practice.

It has one stubborn flaw. Before you can send a secret message, you and the other person must already share a secret key. How do you get the key to them?

One key for both: the problemInteractive
Alice
Eve, listening
knows: nothing
Bob

Alice and Bob have never met. Eve can read every message that passes between them.

If you can send the key safely, you did not need encryption. If you cannot, the encryption is worthless. For most of history the answer was a trusted courier. That does not work for a web browser talking to a shop it has never heard of.

Two keys

In the 1970s a different idea appeared. Instead of one key, generate two keys that are mathematically linked:

  • a public key, which you give to everyone, and
  • a private key, which you never show to anyone.

What one key locks, only the other can unlock.

Example

A padlock anyone can close

Bob makes thousands of identical open padlocks and hands them out freely. He keeps the only key.

Alice wants to send Bob a secret. She puts it in a box and snaps one of his padlocks shut on it. Now nobody can open that box. Not Eve, who saw the padlock. Not even Alice. Only Bob.

The padlock is the public key. Bob's key is the private key.

Two keys: a public one and a private oneInteractive
Alice
Eve, listening
knows: nothing
Bob
private key: kept

Alice and Bob have never met. Eve can read every message that passes between them.

Nothing secret was ever sent. Eve has the public key and the scrambled message, and neither helps her. This is asymmetric, or public-key, cryptography, and it is what makes secure communication between strangers possible.

How can a key lock but not unlock?

It rests on mathematical operations that are easy to do and practically impossible to undo.

Multiplying two large prime numbers takes a computer an instant. Given only the result, finding the two primes would take longer than the age of the universe, if the primes are big enough. The public key is built from the product. The private key needs the primes.

Example

RSA with tiny numbers

Real keys use numbers hundreds of digits long. The same recipe works with small ones.

Pick two primes, 3 and 11. Multiply them: 33. The public key is the pair (3, 33). The private key is (7, 33).

To encrypt the message 4: raise it to the power 3 and take the remainder after dividing by 33. 4 × 4 × 4 = 64, and 64 leaves remainder 31. Send 31.

To decrypt: raise 31 to the power 7 and take the remainder after dividing by 33. The answer is 4.

Anyone can do the first step with the public numbers. Undoing it requires the 7, and working out the 7 requires knowing that 33 is 3 × 11. Trivial here. Hopeless when the number has 600 digits.

The other direction: signatures

The keys work both ways round, and the reverse is just as useful.

If Alice uses her private key on a message, anyone with her public key can check the result. Since only Alice has her private key, a successful check proves two things: the message came from her, and it has not been changed since.

The other direction: signingInteractive
Alice
private key: kept
Eve, listening
Bob
has: Alice's public key

Alice and Bob have never met. Eve can read every message that passes between them.

That is a digital signature.

GoalLock withUnlock or check with
Keep a message secretThe receiver's public keyThe receiver's private key
Prove who sent itThe sender's private keyThe sender's public key
One key for both: the problemInteractive
Scenario
Alice
Eve, listening
knows: nothing
Bob

Alice and Bob have never met. Eve can read every message that passes between them.

Why both kinds are used together

Public-key operations are slow: thousands of times slower than symmetric encryption. So real systems use each for what it is good at.

  1. Use public-key cryptography to agree on a secret

    Just once, at the start of a connection.

  2. Use that secret as a symmetric key

    For all the actual data, at full speed.

That is exactly what happens every time you open an https page. See HTTPS and the TLS Handshake.

One problem remains: whose key is it?

Public-key cryptography guarantees that only the holder of the matching private key can read your message. It does not tell you who that holder is. If Eve can hand Alice a public key and say "this is Bob's", Alice will happily encrypt to Eve.

So public keys need to be vouched for. On the web that is the job of certificates: a trusted authority signs a statement that a given public key belongs to a given site.

Where you use it every day

  • HTTPS: proving a website's identity and agreeing on keys.
  • SSH and Git: you put a public key on a server and prove your identity with the private one, with no password sent.
  • Software updates: signed by the publisher, checked by your device before installing.
  • Messaging apps: end-to-end encryption, where only the two phones hold the private keys.
  • Passkeys: logging in to a site with a key pair in place of a password.

Key takeaways

  • Symmetric encryption uses one shared key, which leaves the problem of sharing it safely.
  • Public-key cryptography uses a pair: a public key to give away and a private key to keep.
  • Anything locked with the public key can only be opened with the private key.
  • Used the other way, the private key signs and the public key verifies.
  • It is slow, so it is used to set up a shared key, and symmetric encryption does the rest.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    8 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress