Diffie-Hellman lets two parties who have never met agree on a shared secret over a public channel. Each picks a private number, publishes a public value, and combines the other's public value with their own private number. Both arrive at the same shared secret. An eavesdropper who sees the public values cannot compute the secret without solving the discrete logarithm problem.
Diffie-Hellman with small numbers
Pick a prime p and a generator g of the cyclic group Z*p. Alice picks secret a, publishes A = ga mod p. Bob picks secret b, publishes B = gb mod p. Alice computes Ba mod p. Bob computes Ab mod p. Both get gab mod p. An eavesdropper sees g, p, A, B but not a or b.
Scheme
; Diffie-Hellman key exchange with small numbers
(define p 23) ; prime
(define g 5) ; generator of Z*_23;; Modular exponentiation: base^exp mod m
(define (mod-exp base exp m)
(let loop ((result 1) (b (modulo base m)) (e exp))
(if (= e 0) result
(loop (if (odd? e) (modulo (* result b) m) result)
(modulo (* b b) m)
(quotient e 2)))))
;; Alice's secret
(define a 6)
(define A (mod-exp g a p)) ; g^a mod p;; Bob's secret
(define b 15)
(define B (mod-exp g b p)) ; g^b mod p
(display "Public parameters: p=") (display p)
(display ", g=") (display g) (newline)
(display "Alice publishes A = g^a mod p = ") (display A) (newline)
(display "Bob publishes B = g^b mod p = ") (display B) (newline)
;; Both compute the shared secret
(define alice-secret (mod-exp B a p)) ; B^a = g^(ab) mod p
(define bob-secret (mod-exp A b p)) ; A^b = g^(ab) mod p
(display "Alice computes B^a mod p = ") (display alice-secret) (newline)
(display "Bob computes A^b mod p = ") (display bob-secret) (newline)
(display "Same secret? ") (display (= alice-secret bob-secret))
Python
# Diffie-Hellman in Python
p, g = 23, 5# prime and generator
a = 6# Alice's secret
b = 15# Bob's secret
A = pow(g, a, p) # Alice publishes
B = pow(g, b, p) # Bob publishesprint(f"Alice publishes A = {A}")
print(f"Bob publishes B = {B}")
alice_secret = pow(B, a, p) # B^a mod p
bob_secret = pow(A, b, p) # A^b mod pprint(f"Alice's shared secret: {alice_secret}")
print(f"Bob's shared secret: {bob_secret}")
print(f"Same? {alice_secret == bob_secret}")
The discrete logarithm problem
Given g, p, and A = ga mod p, find a. For small p this is easy (try all values). For a 2048-bit prime, no known algorithm solves it efficiently. The best general algorithm (number field sieve) runs in sub-exponential but still impractical time. This hardness assumption is the foundation of DH security.
Scheme
; Discrete log by brute force (only works for small p)
(define (mod-exp base exp m)
(let loop ((result 1) (b (modulo base m)) (e exp))
(if (= e 0) result
(loop (if (odd? e) (modulo (* result b) m) result)
(modulo (* b b) m)
(quotient e 2)))))
(define p 23)
(define g 5)
(define A 8) ; = g^a mod p, find a
(define (brute-force-dlog g A p)
(let loop ((a 0))
(if (= (mod-exp g a p) A) a
(loop (+ a 1)))))
(display "g=5, A=8, p=23") (newline)
(display "Discrete log (brute force): a = ")
(display (brute-force-dlog g A p)) (newline)
;; Verify
(define a-found (brute-force-dlog g A p))
(display "Check: g^a mod p = ") (display (mod-exp g a-found p)) (newline)
(display "For p with 2048 bits, brute force is impossible.")
Man-in-the-middle attack
Plain DH is vulnerable to an active attacker (Mallory) who intercepts the exchange. Mallory runs separate DH with Alice and Bob, establishing different shared secrets with each. She decrypts Alice's messages, re-encrypts for Bob, and neither party knows. The fix: authenticated key exchange, where each party proves their identity (via signatures or certificates) alongside the DH exchange.
Scheme
; Man-in-the-middle: Mallory intercepts DH
(define (mod-exp base exp m)
(let loop ((result 1) (b (modulo base m)) (e exp))
(if (= e 0) result
(loop (if (odd? e) (modulo (* result b) m) result)
(modulo (* b b) m)
(quotient e 2)))))
(define p 23)
(define g 5)
;; Alice and Bob's real secrets
(define a 6)
(define b 15)
;; Mallory's secrets
(define m1 10) ; for Alice
(define m2 3) ; for Bob;; Alice sends g^a, Mallory intercepts, sends g^m1 to Bob
(define A (mod-exp g a p))
(define M1 (mod-exp g m1 p))
;; Bob sends g^b, Mallory intercepts, sends g^m2 to Alice
(define B (mod-exp g b p))
(define M2 (mod-exp g m2 p))
;; Alice thinks shared secret is (g^m2)^a
(define alice-key (mod-exp M2 a p))
;; Mallory knows this too: (g^a)^m2
(define mallory-alice-key (mod-exp A m2 p))
(display "Alice's key: ") (display alice-key) (newline)
(display "Mallory's key (Alice): ") (display mallory-alice-key) (newline)
(display "Match? ") (display (= alice-key mallory-alice-key)) (newline)
;; Bob thinks shared secret is (g^m1)^b
(define bob-key (mod-exp M1 b p))
(define mallory-bob-key (mod-exp B m1 p))
(display "Bob's key: ") (display bob-key) (newline)
(display "Mallory's key (Bob): ") (display mallory-bob-key) (newline)
(display "Match? ") (display (= bob-key mallory-bob-key)) (newline)
(display "Alice and Bob have DIFFERENT keys!")
Neighbors
Cross-references
🔗 Judson Ch. 1 — groups: Diffie-Hellman operates in cyclic groups
Diffie-Hellman key exchange · CC BY-SA 4.0