Public-Key Secrets With Paint Mixing
About this lesson, for parents and teachers
How can two people who have never met agree on a secret password while a spy reads every message they send? It sounds impossible. Mix some paint and find out.
Ages 15–18 · about 8 minutes · builds on Hashing: How Passwords Stay Secret
Try this
- Tap a secret colour for Alice and one for Bob. Press Mix and send: each adds their secret to the public yellow and sends the mixture.
- Press Add your secret. Both end up with exactly the same colour, and Eve only ever saw the mixtures.
- Switch to Numbers, press Exchange, then play Eve and brute-force Alice's secret with
p = 23. - Pick
p = 2147483647and let Eve run on auto. How long would she need?
How it works
In the paint picture, everyone knows the public colour, yellow. Alice secretly picks red and Bob secretly picks blue. Each mixes their secret with yellow and sends the mixture openly. Then each adds their own secret to the mixture they received. Alice has yellow + blue + red, Bob has yellow + red + blue: the same paint, because the order of mixing does not matter. The trick is that un-mixing paint is hard, so Eve cannot pull a secret colour back out.
Real Diffie-Hellman key exchange swaps paint for numbers. Everyone agrees on a prime p and a base g. Alice picks a secret a and sends A = g^a mod p; Bob picks b and sends B = g^b mod p. Alice computes B^a mod p and Bob computes A^b mod p. Both equal g^(ab) mod p, so they share a secret that never travelled over the network.
mod p means "the remainder after dividing by p", like a clock that wraps around. Computing g^a mod p is fast even for huge numbers, using repeated squaring. Going backwards, finding a from A, is the discrete logarithm problem, and nobody knows a fast way to do it for well-chosen large primes. That one-way street plays the role of un-mixing paint.
With p = 23, Eve just tries every exponent and wins in a moment. Real systems use primes around 2048 bits (about 617 digits), or the same idea on elliptic curves, so trying every possibility is hopeless. One honest caveat: Diffie-Hellman alone does not prove who you are talking to. An attacker in the middle could swap in her own numbers, so real protocols such as TLS also use digital signatures and certificates.
Where engineers use this
Every time a browser shows the padlock for HTTPS, it runs an elliptic-curve version of Diffie-Hellman (such as X25519) to agree on encryption keys. Messaging apps like Signal and WhatsApp use the same idea, and VPNs and SSH do too.
Words to know
- Key exchange
- A method for two parties to agree on a shared secret key over a channel others can read.
- Modular arithmetic
- Arithmetic with remainders:
x mod pis what is left after dividing x by p. - Discrete logarithm
- Finding the exponent a in
g^a mod p = A. Believed to be very hard for large primes. - Eavesdropper
- Someone who can read messages on a network but is not meant to understand them.
Talk about it
Goal: Agree on a shared secret in public using the paint-mixing picture of Diffie-Hellman.
- Why does it matter that mixing paint is easy but un-mixing it is hard?
- Eve can see A and B. Why can't she just multiply them together to get the secret?
- If someone could pretend to be Bob, could they still trick Alice? What extra protection would help?
Without a screen: Use food colouring and three clear cups of water with a drop of yellow each. Two players secretly add one drop of their own colour, swap cups in front of a third player, then add their own drop again. Compare the final colours. Then let the third player try to recreate them from what they saw.
Curriculum links: CSTA K-12 3A-NI-05 (give examples to illustrate how sensitive data can be affected by malware and other attacks) and 3B-NI-04 (compare ways software developers protect devices and information from unauthorized access); AP CSP Computing Systems and Networks (public key encryption); Common Core HSN-RN (properties of exponents)
Questions
What is Diffie-Hellman in simple terms?
Diffie-Hellman is a way for two people to create the same secret key by exchanging public messages. Each keeps a private number, sends a scrambled version of it, and combines what they receive with their own private number to reach the same result.
Why is the paint mixing analogy used for Diffie-Hellman?
Mixing paint is easy but separating a mixture back into its colours is very hard, and the order you mix in does not matter. Those two properties match the maths of Diffie-Hellman, where exponentiation mod p is easy but undoing it is hard.
How does HTTPS keep my data secret?
When your browser connects to a site, it uses a key exchange such as elliptic-curve Diffie-Hellman to agree on a secret key with the server, checks the server's certificate to make sure it is the real site, and then encrypts everything with that key.