Imagine Alice and Bob want to agree on a password. But Eve is listening to every word they say. How can they both arrive at the same text string without ever saying it? Whitfield Diffie and Martin Hellman solved this in 1976.
The Paint Analogy
1. Public Paint (Yellow): Alice and Bob agree on a public color (Yellow). Eve sees Yellow.
2. Secret Colors: Alice picks Red. Bob picks Blue. (Eve sees nothing).
3. Mixing:
- Alice mixes Yellow + Red = Orange. Sends Orange to Bob. (Eve sees Orange, but can't un-mix it to find Red).
- Bob mixes Yellow + Blue = Green. Sends Green to Alice. (Eve sees Green).
4. Final Mix:
- Alice takes Bob's Green and adds her Red = Brown.
- Bob takes Alice's Orange and adds his Blue = Brown.
Result: Both have the same color (Brown). Eve only saw Yellow, Orange, and Green. She cannot make Brown because she lacks the secret colors.
1. The Math (Modular Arithmetic)
Instead of paint, we use numbers.
1. Agree on a prime p and a base g.
2. Alice picks secret a. Computes A = g^a mod p. Sends A.
3. Bob picks secret b. Computes B = g^b mod p. Sends B.
4. Shared Secret:
- Alice: s = B^a mod p
- Bob: s = A^b mod p
- Why? Because (g^b)^a is the same as (g^a)^b.
2. Vulnerability: Man-In-The-Middle
Diffie-Hellman has no authentication!
If Eve stands in the middle:
- Alice thinks she is exchanging keys with Bob, but actually exchanges with Eve.
- Eve decrypts messages from Alice, reads them, and re-encrypts them for Bob.
This is why we need RSA / Certificates (Signatures) to verify that we are actually talking to Bob before we start the exchange.