🔐 The Postcard Paradox — How Strangers Share Secrets

Ages: 11–15  ·  Duration: 105 minutes  ·  Topics: Modular arithmetic, Prime numbers, One-way functions, Diffie-Hellman key exchange, RSA encryption, Post-quantum cryptography

Part 0 — The Impossible Problem (10 min)

The Big Idea

"You need to send a secret message to someone you've never met. The only way to communicate is by writing on postcards — and every postcard passes through a nosy mail carrier who reads everything. No meeting in advance. No shared password. No secret handshake. Can you do it?"

Let the class argue. Most will say "impossible!" — and that intuition is exactly right for classical codes. Caesar ciphers, Enigma machines, even modern AES all require both sides to share a secret key first.

But in 1976, three mathematicians showed it is possible, and their trick protects every password, every credit card number, every https:// you've ever used.

The secret ingredient? A math problem that's easy in one direction and impossibly hard in reverse.

Quick Warm-Up: One-Way Functions

🗣️ "I'm thinking of two numbers. Their product is 437. What are the numbers?"

This takes a while. (It's $19 \times 23$.) But if I told you my two numbers are 19 and 23, you'd check the product in two seconds.

This asymmetry — easy forward, hard backward — is the foundation of all public-key cryptography.

Part 1 — Clock Arithmetic: The Language of Secrets (≈ 15 min)

Modular Arithmetic

Before we can crack the code, we need a special kind of arithmetic — modular arithmetic, or "clock arithmetic."

On a 12-hour clock: $10 + 5 = 3$ (not 15). We "wrap around" after 12. In math notation:

The number after mod is the modulus — the size of our clock. In cryptography, we use prime-number-sized clocks.

Powers on a Clock

Here's where it gets magical. Pick a base $g = 5$ and a prime modulus $p = 23$. Compute successive powers:

The powers jump around unpredictably. Given $5^k \bmod 23 = 17$, can you figure out $k$? You'd have to try them all. This is called the discrete logarithm problem, and for large numbers it's essentially unsolvable.

Part 2 — Diffie-Hellman: Mixing Paint on a Postcard ⭐ (≈ 15 min)

Whitfield Diffie and Martin Hellman (1976) solved the postcard paradox. Their trick is so elegant it can be explained with paint.

The Paint-Mixing Analogy

Imagine a world where:

• Mixing two paint colours is easy.
• Un-mixing a colour back into its components is impossible.

Alice and Bob agree (in public!) on a starting colour — say, yellow. Then:

1. Alice picks a secret colour (🔴 red) and mixes it with yellow → gets orange. Sends the orange postcard.
2. Bob picks a secret colour (🔵 blue) and mixes it with yellow → gets green. Sends the green postcard.
3. Alice takes Bob's green, mixes in her secret red → gets brown.
4. Bob takes Alice's orange, mixes in his secret blue → gets the same brown!

Eve the eavesdropper sees yellow, orange, and green — but can't un-mix them to recover red or blue, so she can never produce the final brown.

The Real Diffie-Hellman (With Numbers)

Replace "paint" with modular exponentiation on a prime-number clock:

Why do they get the same $s$?

Both arrive at $g^{ab} \bmod p$ — the shared secret — without ever transmitting $a$ or $b$!

☕ Break (5 min)

Part 3 — RSA: Encrypt Without Sharing a Key (≈ 20 min)

Diffie-Hellman lets Alice and Bob agree on a shared secret. But what if Alice wants to receive encrypted messages from anyone — even people she's never talked to?

In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman invented a system where Alice publishes a public key (like a padlock) that anyone can use to lock a message, but only Alice has the private key to unlock it.

The Padlock Analogy

Alice sends open padlocks to everyone. Bob puts his message in a box, snaps the padlock shut, and mails it. Only Alice has the key. Even Bob can't reopen it. Eve sees a locked box and is helpless.

RSA Step by Step

Encryption & Decryption

Where $m$ is the message (as a number) and $c$ is the ciphertext.

Worked Example: RSA with Tiny Primes

Let $p = 11$, $q = 13$.

1. $n = 11 \times 13 = 143$
2. $\phi(n) = 10 \times 12 = 120$
3. Choose $e = 7$   (check: $\gcd(7, 120) = 1$ ✓)
4. Find $d$: we need $7d \equiv 1 \pmod{120}$ → $d = 103$   (because $7 \times 103 = 721 = 6 \times 120 + 1$)

Public key: $(143, 7)$. Private key: $103$.

Encrypt the letter 'B' (ASCII 66):

Using repeated squaring:

Ciphertext: $c = 77$. Send it on the postcard!

Decrypt:

(The interactive widget below will verify this instantly.)

Why Is RSA Secure?

Eve sees the public key $(n, e)$ and the ciphertext $c$. To decrypt, she needs $d$. To find $d$, she needs $\phi(n)$. To find $\phi(n)$, she needs to factor $n = p \times q$.

Part 4 — The Quantum Threat: Why Everything Changes (≈ 15 min)

"Every lock we've built today rests on one assumption: factoring big numbers is hard. What if that assumption breaks?"

Enter the Quantum Computer

Classical computers try one thing at a time (or a few in parallel). A quantum computer exploits superposition — qubits can be 0, 1, or both at once — and entanglement to explore many possibilities simultaneously.

In 1994, mathematician Peter Shor designed an algorithm that can factor large numbers in polynomial time on a quantum computer. Specifically:

Where $n$ is the number of digits. For RSA-2048:

How Does Shor's Algorithm Work? (Simplified)

Shor's brilliant insight: factoring $n$ reduces to finding the period of a function.

1. Pick a random number $a < n$.
2. Consider the function $f(x) = a^x \bmod n$. This function is periodic — it repeats after some period $r$.
3. A quantum computer can find $r$ exponentially faster than a classical computer using the Quantum Fourier Transform.
4. Once you know $r$, some algebra gives you the factors of $n$.

Example: Factor $n = 15$ with $a = 7$.

The sequence repeats with period $r = 4$. Now compute: $\gcd(7^{4/2} - 1, \; 15) = \gcd(48, 15) = 3$ and $\gcd(7^{4/2} + 1, \; 15) = \gcd(50, 15) = 5$.

The factors are 3 and 5. A quantum computer does the period-finding step in polynomial time — that's the game changer.

Part 5 — Post-Quantum Cryptography: Building Locks That Survive (≈ 15 min)

"If quantum computers break multiplication-based locks, we need locks based on problems that quantum computers ALSO find hard."

What Survives a Quantum Computer?

Not all mathematical problems yield to Shor's algorithm. The cryptography community has been racing to find quantum-resistant alternatives. In 2024, NIST (the U.S. standards agency) finalised the first post-quantum standards. The leading approach: lattice-based cryptography.

Lattices: A New Kind of Hard Problem

A lattice is a regular grid of points in space, like the corners of floor tiles extending infinitely in all directions.

In 2D, a lattice is defined by two basis vectors $\mathbf{v}_1$ and $\mathbf{v}_2$. Every lattice point is a combination $a\,\mathbf{v}_1 + b\,\mathbf{v}_2$ where $a$ and $b$ are integers.

The hard problems on lattices:

Learning With Errors (LWE) — The New Trap Door

Here's the idea behind the post-quantum standard ML-KEM (formerly called Kyber, now FIPS 203):

1. Alice generates a secret vector $\mathbf{s}$ and a random matrix $\mathbf{A}$ (modular arithmetic, mod a prime $q$).
2. She computes $\mathbf{b} = \mathbf{A} \cdot \mathbf{s} + \mathbf{e}$, where $\mathbf{e}$ is a small random error.
3. She publishes $(\mathbf{A}, \mathbf{b})$ as her public key. Keeps $\mathbf{s}$ private.
4. Without knowing $\mathbf{s}$, the small error makes the system of equations unsolvable — even for a quantum computer.

It's like trying to solve a jigsaw puzzle where every piece has been trimmed by a random millimetre. Close enough to fit, but impossible to solve exactly without knowing the original template.

The Cryptographic Timeline

Summary

The Encryption Chain

Method Comparison

Extensions & Challenge Problems 🧩

Answer Key

← Back to all lectures