Diffie-Hellman is a cryptographic handshake that allows two parties to agree on a shared secret key over an insecure channel without ever explicitly sending that secret key.
Imagine Alice and Bob want to establish a secure communication channel. They’ve never met, and they’re communicating over a public, noisy phone line where Eve is listening. They need a way to agree on a secret password (the key) that Eve can’t figure out, even though she hears everything they say. Diffie-Hellman is their method.
Here’s how they do it, using a simple analogy with paint colors:
-
Public Agreement on Base Colors: Alice and Bob publicly agree on two base colors. Let’s say a common yellow and a common blue. These are like the public parameters in Diffie-Hellman: a prime number
p(the modulus) and a baseg(the generator). In a real crypto system, these are large numbers, not colors. For example,p = 23andg = 5. -
Private Color Mixing:
- Alice secretly chooses a private color, say red. She mixes this red with the public yellow. She gets an orange-ish color.
- Bob secretly chooses a private color, say green. He mixes this green with the public yellow. He gets a lime-ish color.
In Diffie-Hellman, Alice picks a secret private integer
a(e.g.,a = 6) and Bob picks a secret private integerb(e.g.,b = 15). -
Public Exchange of Mixed Colors:
- Alice sends her orange-ish mixture (red + yellow) to Bob.
- Bob sends his lime-ish mixture (green + yellow) to Alice.
Crucially, Eve, listening in, sees the public yellow and blue, and she sees Alice’s orange and Bob’s lime. But it’s computationally infeasible for Eve to separate the original red from Alice’s orange, or the original green from Bob’s lime. It’s easy to mix colors, hard to unmix.
Alice calculates
A = g^a mod pand sendsAto Bob. Bob calculatesB = g^b mod pand sendsBto Alice.- Alice:
A = 5^6 mod 23 = 15625 mod 23 = 8. She sends8to Bob. - Bob:
B = 5^15 mod 23 = 30517578125 mod 23 = 19. He sends19to Alice. Eve seesp=23,g=5,A=8, andB=19.
-
Deriving the Shared Secret:
- Alice receives Bob’s lime-ish mixture. She takes her own private red and mixes it with Bob’s mixture. Her resulting color (red + green + yellow) is a unique shade of brown.
- Bob receives Alice’s orange-ish mixture. He takes his own private green and mixes it with Alice’s mixture. His resulting color (green + red + yellow) is the exact same shade of brown.
Now they both have the same brown color, which is their shared secret. Eve, who only has yellow, blue, orange, and lime, cannot derive this specific shade of brown because she doesn’t have Alice’s private red or Bob’s private green.
- Alice takes Bob’s public value
Band raises it to her private powera:S_Alice = B^a mod p.S_Alice = 19^6 mod 23 = 47045881 mod 23 = 2. - Bob takes Alice’s public value
Aand raises it to his private powerb:S_Bob = A^b mod p.S_Bob = 8^15 mod 23 = 35184372088832 mod 23 = 2.
Both Alice and Bob arrive at the same shared secret value:
2. This value2is then used as the symmetric encryption key for their subsequent communication. Eve, knowing onlyp,g,A, andB, would have to solve the discrete logarithm problem (e.g.,5^a mod 23 = 8to finda) to find the secret key, which is computationally infeasible for large numbers.
The magic here is that the associative and commutative properties of modular exponentiation allow for this shared secret derivation. (g^a)^b mod p is mathematically identical to (g^b)^a mod p, which both simplify to g^(ab) mod p.
The one thing most people don’t immediately grasp is that the order in which you apply the private exponent and the public value doesn’t matter. Bob can’t derive Alice’s secret a from g^a mod p because it’s the discrete logarithm problem, and Alice can’t derive Bob’s secret b from g^b mod p. But both can independently calculate g^(ab) mod p by combining their own secret exponent with the other party’s public result.
The next step in securing communication after agreeing on a key is typically to use that key with a symmetric encryption algorithm like AES.