Diffie-Hellman key exchange

How two strangers agree on a shared secret over a public channel using nothing but a prime, a generator and one exponentiation each, and why the exchange alone cannot tell them who they are really talking to.

Compute both public values and the shared secret given p, g, a and b, showing every step.
Explain algebraically why Alice's and Bob's independent computations land on the same key.
Trace a person-in-the-middle attack step by step and state what the attacker ends up holding.
Explain why digital signatures close the gap that makes the attack possible.

20 min read

Intuition

Symmetric encryption needs both sides to already hold the same key. RSA solves that by letting anyone encrypt with a public key that only one person can decrypt, but that means committing to a whole public-key infrastructure just to move a session key. Diffie-Hellman does something narrower and, for this one job, simpler: two people who share nothing in advance can still walk away from a conversation an eavesdropper heard in full, holding a secret number the eavesdropper cannot compute.

Mechanism

Alice and Bob start from two values that are public from the beginning: a prime $p$ , and $g$ , a primitive root (generator) of $p$ . Anyone, including an attacker, may know both.

	Alice	Bob
1. Pick a private value	random $a < p$	random $b < p$
2. Compute a public value	$X = g^{a} \bmod p$	$Y = g^{b} \bmod p$
3. Send it	sends $X$ to Bob	sends $Y$ to Alice
4. Compute the shared secret	$K = Y^{a} \bmod p$	$K = X^{b} \bmod p$

$a$ and $b$ never leave their owner. Only $p$ , $g$ , $X$ and $Y$ cross the channel, and all four are things an eavesdropper is allowed to see without threatening the outcome.

Why the two computations agree. Substitute what $X$ and $Y$ actually are:

$K = Y^{a} \bmod p = (g^{b})^{a} \bmod p = g^{ba} \bmod p$ $K = X^{b} \bmod p = (g^{a})^{b} \bmod p = g^{ab} \bmod p$

Since $ba = ab$ , both sides land on the identical value $g^{ab} \bmod p$ , computed two different ways, without either exponent ever being transmitted.

Why an eavesdropper is stuck. Someone who only watches the exchange knows $p$ , $g$ , $X$ and $Y$ , but not $a$ or $b$ . Recovering either one from its public value (finding $a$ such that $X = g^a \bmod p$ ) is the discrete logarithm problem from the earlier page on trapdoor functions, believed infeasible for a large enough $p$ . Diffie-Hellman’s security is that problem, applied directly: a passive listener is locked out.

Diffie–Hellman key exchange

Alice and Bob agree on p and g in public, each picks a private exponent, and each publishes gᵃ mod p or gᵇ mod p. Both then raise the other's public value to their own private exponent and land on the same K — because (gᵃ)ᵇ ≡ (gᵇ)ᵃ ≡ gᵃᵇ (mod p) — without either exponent ever crossing the wire. Security rests on the discrete logarithm problem: recovering a from gᵃ mod p is believed infeasible for a large enough prime p.

Worked example

Answerp=23, g=5, a=6, b=15: Alice sends X=8, Bob sends Y=19, and both independently compute the shared secret K=2.

Public parameters: $p = 23$ , $g = 5$ .
Alice picks $a = 6$ . Bob picks $b = 15$ . Neither value is sent.
Alice computes $X = 5^{6} \bmod 23$ by repeated squaring: $5^1 = 5$ , $5^2 = 25 \bmod 23 = 2$ , $5^4 = 2^2 = 4$ . $6 = 4+2$ , so $X = 5^4 \times 5^2 \bmod 23 = 4 \times 2 = 8$ .
Bob computes $Y = 5^{15} \bmod 23$ . Continuing the same powers: $5^8 = 4^2 = 16$ . $15 = 8+4+2+1$ , so $Y = 5^8 \times 5^4 \times 5^2 \times 5^1 \bmod 23$ : $16 \times 4 = 64 \bmod 23 = 18$ , then $18 \times 2 = 36 \bmod 23 = 13$ , then $13 \times 5 = 65 \bmod 23 = 19$ . So $Y = 19$ .
Alice sends $X = 8$ to Bob. Bob sends $Y = 19$ to Alice. Both values cross the open channel.
Alice computes $K = Y^{a} \bmod p = 19^{6} \bmod 23$ . $19^2 = 361 \bmod 23 = 16$ , $19^4 = 16^2 = 256 \bmod 23 = 3$ . $19^6 = 19^4 \times 19^2 \bmod 23 = 3 \times 16 = 48 \bmod 23 = 2$ .
Bob computes $K = X^{b} \bmod p = 8^{15} \bmod 23$ . $8^2 = 64 \bmod 23 = 18$ , $8^4 = 18^2 = 324 \bmod 23 = 2$ , $8^8 = 2^2 = 4$ . $15 = 8+4+2+1$ , so $8^{15} = 8^8 \times 8^4 \times 8^2 \times 8^1 \bmod 23$ : $4 \times 2 = 8$ , then $8 \times 18 = 144 \bmod 23 = 6$ , then $6 \times 8 = 48 \bmod 23 = 2$ .
Both sides reach $K = 2$ , computed independently, with $a$ and $b$ never sent.

Threat

Person-in-the-middle. The exchange authenticates nobody: a public value is accepted regardless of who actually sent it. An active attacker sitting between Alice and Bob intercepts both public values and runs two independent Diffie-Hellman exchanges: one posing as Bob to Alice, one posing as Alice to Bob. Each exchange completes normally and produces a valid shared key, so the attacker ends up holding two working keys: one matching what Alice thinks she shares with Bob, one matching what Bob thinks he shares with Alice, while Alice and Bob each believe they are talking directly to the other.

Diffie–Hellman under a person-in-the-middle attack

Passive eavesdropping cannot recover K without solving the discrete logarithm problem, but Diffie-Hellman on its own authenticates no one. Mallory runs two separate exchanges — one impersonating Bob to Alice, one impersonating Alice to Bob — and ends up holding both resulting keys, invisibly relaying (and reading) every message. The fix is to sign each side's public value, so a substituted Xₘ or Yₘ fails verification.

Worked example

AnswerWith Eve using private value 9 against Alice (a=6) and Bob (b=15), Alice ends up sharing key 9 with Eve and Bob ends up sharing key 10 with Eve: two different keys, and neither notices.

Same $p = 23$ , $g = 5$ , Alice’s $a = 6$ , Bob’s $b = 15$ . Eve intercepts the exchange and uses her own private value $9$ in both directions.

Eve and Alice. Alice still computes her real $X = 5^6 \bmod 23 = 8$ (as above) and sends it, straight to Eve, who intercepts it. Eve computes a public value using her own private $9$ : $5^9 \bmod 23$ . Continuing the powers from the previous derivation: $5^9 = 5^8 \times 5^1 \bmod 23 = 16 \times 5 = 80 \bmod 23 = 11$ . Eve sends $11$ to Alice, posing as Bob’s $Y$ .
Alice computes what she believes is the shared secret: $11^{6} \bmod 23$ . $11^2 = 121 \bmod 23 = 6$ , $11^4 = 6^2 = 36 \bmod 23 = 13$ . $11^6 = 11^4 \times 11^2 \bmod 23 = 13 \times 6 = 78 \bmod 23 = 9$ . Alice’s key is $9$ .
Eve computes the same leg from her side: $X^{9} \bmod 23 = 8^{9} \bmod 23$ . From the earlier powers of $8$ : $8^8 = 4$ , so $8^9 = 8^8 \times 8^1 \bmod 23 = 4 \times 8 = 32 \bmod 23 = 9$ . Eve gets $9$ too. This leg of the exchange is internally consistent, exactly like a real one.
Eve and Bob. Eve reuses her public value $11$ (still $5^9 \bmod 23$ ) and sends it to Bob, posing as Alice’s $X$ . Bob still computes his real $Y = 5^{15} \bmod 23 = 19$ (as above) and sends it, straight to Eve.
Bob computes what he believes is the shared secret: $19^{9} \bmod 23$ . Continuing from $19^6 = 2$ : $19^7 = 2 \times 19 = 38 \bmod 23 = 15$ , $19^8 = 15 \times 19 = 285 \bmod 23 = 9$ , $19^9 = 9 \times 19 = 171 \bmod 23 = 10$ . Bob’s key is $10$ .
Eve computes the same leg from her side: $11^{15} \bmod 23$ . Continuing from $11^6 = 9$ by repeated multiplication: $11^7 = 9 \times 11 = 99 \bmod 23 = 7$ , $11^8 = 7 \times 11 = 77 \bmod 23 = 8$ , $11^9 = 8 \times 11 = 88 \bmod 23 = 19$ , $11^{10} = 19 \times 11 = 209 \bmod 23 = 2$ , $11^{11} = 2 \times 11 = 22$ , $11^{12} = 22 \times 11 = 242 \bmod 23 = 12$ , $11^{13} = 12 \times 11 = 132 \bmod 23 = 17$ , $11^{14} = 17 \times 11 = 187 \bmod 23 = 3$ , $11^{15} = 3 \times 11 = 33 \bmod 23 = 10$ . Eve gets $10$ too.
Eve now holds two working keys: $9$ , shared with Alice, and $10$ , shared with Bob. Alice’s key ( $9$ ) and Bob’s key ( $10$ ) do not match each other. Neither Alice nor Bob can tell, because each of them completed a valid-looking exchange and reached a key that is genuinely shared, just with Eve, not with each other.

Control

Digital signatures. Have each party sign their own public value with a private signing key established out of band, and have the other party verify that signature before trusting the value. Eve can still intercept $X$ and $Y$ , but she cannot produce a signature over her own substituted public value that verifies against Alice’s or Bob’s real signing key: she does not hold either one. The Diffie-Hellman exchange itself is unchanged; what changes is that a forged public value now fails a check before it is ever used to compute a key.

Exam detail

The exam pairs this attack with its fix as a single question shape: name the vulnerability (no authentication of the public values), describe the attack (two independent exchanges, two different keys, both parties deceived), and name the control (signed public values). Diffie-Hellman is secure against a passive eavesdropper because of the discrete logarithm problem; it is not secure against an active attacker on its own, because the protocol as given has no way to check who sent a public value.

Pitfall

Do not describe the person-in-the-middle attack as “breaking” the discrete logarithm problem. Eve never computes a private exponent from a public value. She does not need to, because she generates her own valid key pair and runs two ordinary exchanges. The failure is entirely about missing authentication, not about the underlying maths giving way.

Recall

Alice and Bob complete a Diffie-Hellman exchange and both compute the same K. Does this prove they were talking to each other, and not to an attacker in the middle?

No. Each side only proves that some exchange completed correctly on their end. The maths guarantees agreement with whoever sent the public value they received, not that the sender was who they think it was. Diffie-Hellman on its own authenticates nobody, which is exactly what makes the person-in-the-middle attack possible.

Source

Week 5 notes PDF