Part I, Foundations · Lesson 2
Public keys, private keys and the locked mailbox
The short version
Imagine a mailbox with a slot anyone can drop letters into, but only you have the key to open it. Public-key cryptography works like that: you hand out the slot (your public key) and keep the key (your private key). It's safe because some math problems, like splitting a huge number into the two primes that made it, are incredibly hard. A big quantum computer would make those problems easy.
You'll learn to
- Explain the key-distribution problem and how public-key cryptography solves it.
- Describe RSA in plain terms and build a toy RSA key yourself.
- Explain the difference between key exchange, public-key encryption and digital signatures.
- Identify the math problems today's public-key cryptography depends on.
For most of history, secret communication had a chicken-and-egg problem. To share a secret safely you needed a shared secret key, and to share the key safely you needed... a secure channel. In practice, that meant keys traveled by trusted courier or were handed over in person.
The internet can't work like that. You connect to websites you've never visited before, run by people you'll never meet, over networks run by strangers. Public-key cryptography is the idea that made this possible, and it's the idea a quantum computer would undo.
The key-distribution problem
In the previous lesson we met symmetric encryption, where both sides use the same secret key. It's fast and strong. But if Alice and Bob have never met, and every message between them can be read by an eavesdropper called Eve, how do they agree on that key?
Any key Alice sends, Eve sees. Any key Bob sends back, Eve sees too. It sounds impossible. In 1976, Whitfield Diffie and Martin Hellman published a paper called "New Directions in Cryptography" showing that it isn't.
The locked mailbox
Picture a mailbox on your street. It has a slot at the top: anyone can drop a letter in. It has a locked door at the bottom: only you have the key that opens it.
- The slot is your public key. You can publish it on your website, print it on business cards, shout it from rooftops. Anyone can use it to send you something.
- The door key is your private key. It never leaves your hands. It's the only way to get letters out.
The two keys are mathematically linked, but knowing the public one doesn't let you work out the private one in any reasonable time. That's the whole trick. It's called asymmetric or public-key cryptography because the two keys are different.
Trapdoors: easy one way, hard the other
How can two numbers be linked, yet one can't be worked out from the other? Through a trapdoor function: a calculation that's easy to do, hard to undo, unless you know a secret shortcut.
The classic example is multiplying primes. A prime is a whole number with no divisors other than 1 and itself, like 53 or 61. Multiplying two primes is easy: 61 × 53 = 3,233. Going backwards, from 3,233 to "61 times 53," is harder. You have to hunt for the factors.
At this size the hunt takes a fraction of a second. But the difficulty grows ferociously with size. A real RSA-2048 key uses a number 617 decimal digits long. Multiplying its two prime factors takes a computer microseconds. Finding them, with the best known methods on ordinary computers, is far beyond what anyone can do.
RSA: the first practical public-key system
In 1977, Ron Rivest, Adi Shamir and Leonard Adleman described the system now called RSA, after their initials. Without the math, it goes like this:
- Pick two large secret primes, p and q. Multiply them to get n.
- From p and q, compute a matched pair of exponents: a public e and a private d.
- Publish n and e. That's the public key. Keep d (and p, q) secret.
- To encrypt a message (written as a number m smaller than n), anyone computes me mod n. ("mod n" means "the remainder after dividing by n," like clock arithmetic.)
- To decrypt, the owner raises the result to the power d, mod n, and the original message pops back out.
Computing d requires knowing p and q. So anyone who can factor n can rebuild the private key. Try it yourself, then play the attacker:
Start with the textbook primes 61 and 53. The attacker factors n instantly. Then try the "Largest toy" preset. Even with roughly 16-digit numbers, simple trial division takes millions of steps. Open "How does this scale?" to see the brute-force estimates for real key sizes balloon into absurd numbers of years.
Two honest caveats about the toy. First, real attackers use far better methods than trial division, which is why real RSA keys are so large. Second, real RSA never encrypts a message directly like this. It adds random padding first. Without padding, the same message always encrypts to the same ciphertext, which leaks information (the "short word" mode shows why).
Diffie-Hellman: agreeing on a secret in public
RSA lets anyone send you an encrypted message. Diffie and Hellman's idea solves a slightly different problem: two people jointly create a shared secret, in public, without either sending it. This is called key exchange.
A popular analogy uses paint. Alice and Bob agree publicly on a common color, say yellow. Each secretly picks a private color and mixes it with the yellow. They swap their mixtures in public. Each then adds their own private color to the mixture they received. Both end up with the same final color: yellow + Alice's + Bob's. Eve saw yellow and both mixtures, but "unmixing" paint to extract a private color is hard.
In the real version, the "mixing" is a mathematical operation that's easy to do and hard to undo: raising a number to a power, modulo a prime. Undoing it is called the discrete logarithm problem.
Elliptic curves: same idea, smaller keys
Modern systems often do the same trick on elliptic curves, a different mathematical setting where the "hard to undo" problem is an elliptic-curve discrete logarithm. The payoff is compactness. An X25519 key-exchange public key is 32 bytes, and an Ed25519 signature is 64 bytes. An RSA-2048 public modulus alone is 256 bytes. That's why elliptic-curve cryptography (ECDH for key exchange, ECDSA and Ed25519 for signatures) has taken over much of the internet.
Signatures: the mailbox in reverse
Public-key cryptography also gives us digital signatures. Flip the mailbox around: now only you can put something in the display case, but anyone can look through the glass and see that it's genuinely yours.
The signer uses the private key to produce a signature over a document (in practice, over its hash). Anyone with the public key can verify it. If even one bit of the document changes, verification fails. Signatures protect software updates, website certificates, legal documents and cryptocurrency transactions.
How it all fits together
Public-key operations are slow compared with symmetric encryption. So real protocols combine them:
| Step | Tool | Typical algorithm today |
|---|---|---|
| Agree on a fresh shared key | Key exchange | ECDH (such as X25519), or classic Diffie-Hellman |
| Prove who you're talking to | Signatures and certificates | RSA, ECDSA, Ed25519 |
| Encrypt the actual data | Symmetric encryption | AES |
This pattern of public-key setup followed by symmetric bulk encryption shows up in HTTPS, messaging apps, VPNs and SSH.
The single point of failure
Look back at what all of this rests on. RSA is safe only if factoring large numbers is hard. Diffie-Hellman, ECDH, ECDSA and Ed25519 are safe only if discrete logarithms are hard. These two problems have resisted classical attack for decades.
In 1994, Peter Shor showed that a large enough quantum computer could solve both efficiently. Not a bit faster: efficiently, in a way that bigger keys can't outrun. Every public-key algorithm in the table above falls to the same idea.
That's why this course exists. Before we get to Shor's algorithm, we need to understand what a quantum computer actually is, and isn't. That's the next lesson.
Go deeper: why RSA decryption works
The private exponent d is chosen so that e · d leaves a remainder of 1 when divided by φ = (p − 1)(q − 1). A theorem of Euler says that raising a number to a multiple of φ, plus 1, mod n, brings you back to the original number. So (me)d = me·d ≡ m (mod n).
Computing φ requires p and q. That's the trapdoor: with the factors it's one line of arithmetic; without them, nobody knows a fast classical method. In the widget, try typing your own e. If it shares a factor with φ, no d exists, and the widget tells you so.
Summary
- Public-key cryptography solves the key-distribution problem: strangers can set up secrets over a public network.
- Your public key is like a mailbox slot anyone can use; your private key is the only way to open it.
- RSA (1977) relies on factoring being hard; Diffie-Hellman (1976) and elliptic-curve cryptography rely on discrete logarithms being hard.
- Real protocols use public-key cryptography to agree on a key and authenticate, then AES for the bulk data.
- Signatures are the mailbox in reverse: only the private key can sign, anyone can verify.
- Shor's algorithm solves both factoring and discrete logarithms, so all of today's public-key algorithms share one weakness.
Questions
Get five of six right to mark the lesson complete. They also feed the final exam.
Sources
- Diffie & Hellman (1976), New Directions in Cryptography, IEEE Trans. Information Theory
- Rivest, Shamir & Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
- Shor (1994/1995), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- NIST IR 8547 (initial public draft): Transition to Post-Quantum Cryptography Standards
