Diffie-Hellman key exchange

Published by Whitfield Diffie and Martin Hellman in 1976, the Diffie-Hellman (DH) key exchange was the first published practical method for two parties to establish a shared secret over an insecure channel — without any prior shared secret.

The classical version relies on the discrete logarithm problem in modular arithmetic: given a large prime p, a generator g, and g^a mod p, it's hard to recover a. Alice picks a secret a and sends g^a mod p; Bob picks a secret b and sends g^b mod p. Each raises the received value to their own secret: (g^b)^a = (g^a)^b = g^ab mod p — the shared secret, which an eavesdropper watching only g^a and g^b cannot feasibly compute.

Take the small prime p = 23 and generator g = 5. Alice picks secret a = 6 and computes A = 5⁶ mod 23 = 8. Bob picks secret b = 15 and computes B = 5¹⁵ mod 23 = 19. They exchange A and B in the open.

Alice now computes B^a mod p = 19⁶ mod 23 = 2. Bob computes A^b mod p = 8¹⁵ mod 23 = 2. Same answer, reached independently — and an eavesdropper who saw p, g, A, and B has to solve a discrete logarithm to recover a or b, which is infeasible once these numbers are hundreds of digits long instead of two.

Plain Diffie-Hellman guarantees secrecy from a passive eavesdropper, but nothing about who's actually on the other end. An active attacker sitting between Alice and Bob can run two separate DH exchanges — one with each of them — and relay traffic through itself, decrypting and re-encrypting everything, while both Alice and Bob believe they're talking directly to each other.

This is exactly why real protocols never use bare DH: TLS combines the DH (or ECDH) exchange with a certificate-backed signature over the handshake transcript, and the Signal Protocol's X3DH verifies identity keys out of band — the key exchange handles secrecy, but authentication has to come from somewhere else entirely.

The same idea maps onto elliptic curves: instead of modular exponentiation, parties combine points on a curve, using exactly the scalar multiplication (kG) and point addition covered in the ECC module. X25519 (ECDH over Curve25519) is the default key exchange in TLS 1.3 and in most modern SSH and messaging protocols, valued for speed and resistance to several classes of implementation error.

The choice of p and g isn't arbitrary. If p is chosen carelessly, the group of values reachable by exponentiation can have small subgroups, and an attacker can sometimes force a DH exchange into one of those subgroups, drastically shrinking the search space for the discrete logarithm. Real implementations use "safe primes" (p where (p−1)/2 is also prime) specifically to avoid this, and validate that received public values aren't degenerate (like 0 or 1) before using them.

When DH parameters are generated fresh for each session (ephemeral Diffie-Hellman, denoted DHE or ECDHE), a compromise of a server's long-term private key doesn't let an attacker decrypt previously recorded sessions — each session's key existed only in memory and is gone once the connection ends. This property, forward secrecy, is now mandatory in TLS 1.3.