10 — Asymmetric
Diffie-Hellman Key Exchange
Two parties derive a shared secret over a public channel — without ever sending the secret itself.
Public parameters
Large prime p (2048+ bits, ideally safe prime p = 2q+1)
Generator g of a subgroup of Z_p* (often g = 2 or 5)
The math
### Alice
picks secret a ∈ {2, ..., p−2}
computes A = g^a mod p → sends A
### Bob
picks secret b ∈ {2, ..., p−2}
computes B = g^b mod p → sends B
### Shared secret (same both sides)
Alice: K = B^a mod p = (g^b)^a = g^(ab) mod p
Bob: K = A^b mod p = (g^a)^b = g^(ab) mod p
K is identical — and never traveled the wire.
Worked example — every multiply shown
p = 23, g = 5, a = 6, b = 15
# Alice: A = 5^6 mod 23
5² = 25 mod 23 = 2
5⁴ = 2² = 4
5⁶ = 5⁴·5² = 4·2 = 8 → A = 8
# Bob: B = 5^15 mod 23
5⁸ = 4² = 16
5¹² = 16·4 = 64 mod 23 = 64 − 46 = 18
5¹⁵ = 5¹²·5²·5¹ = 18·2·5 = 180 mod 23 = 180 − 161 = 19
# Shared: Alice computes 19^6; Bob computes 8^15
19 ≡ −4: (−4)²=16, (−4)⁴=16²=256 mod23=3, (−4)⁶=3·16=48 mod23=2
8¹⁵ = 2⁴⁵; ord(2)=11 mod23, 45 mod11=1 → 2¹=2 ✓
K = 2 both sides.
Diagram
Public values A, B cross the wire; the secrets a, b never do.
Theory — Discrete Logarithm Problem
Given g, p, A, finding a = log_g A mod p is infeasible for large p (no polynomial-time classical algorithm). That asymmetry — exponentiation easy, logarithm hard — is the entire security. Use safe primes and validate peer values (reject 0, 1, p−1) to block small-subgroup attacks. Prefer ephemeral DHE (fresh a,b per session) for forward secrecy.Critical caveat
Plain DH has no authentication. An active attacker can substitute values — see MITM next. Defenses: sign DH values (TLS, STS, SIGMA).Exam one-liner:
A=g^a, B=g^b, K=g^ab — secrecy from discrete-log hardness, authenticity from nothing (needs signatures).