Diffie-Hellman Key Exchange

Diffie-Hellman key exchange is a protocol, not an encryption scheme: it produces a shared secret value that two parties can later use as a symmetric key, but it does not itself encrypt messages. The protocol operates in a finite cyclic group, most classically the multiplicative group of integers modulo a large prime $p$, generated by an element $g$ of large order. Both $p$ and $g$ are public and can be reused across many sessions or standardized in advance. The security of the exchange rests on the Discrete Logarithm Problem (DLP): given $g$, $p$, and $g^a \bmod p$, finding $a$ is believed to require time exponential in the bit-length of $p$ for the best known classical algorithms, even though computing $g^a \bmod p$ from $a$ takes only polynomial time via fast modular exponentiation. A closely related assumption, the Computational Diffie-Hellman (CDH) assumption, states that given $g^a \bmod p$ and $g^b \bmod p$ alone, computing $g^{ab} \bmod p$ is also hard — this is the precise assumption the protocol's secrecy needs, and it is implied by (but not obviously equivalent to) hardness of the DLP itself. The clean trick is commutativity of exponentiation in the exponent: $(g^a)^b = g^{ab} = (g^b)^a$. Alice raises the public generator to her secret power $a$ and sends the result; Bob does the same with his secret $b$. Each then raises the other party's public value to their own private exponent, and both land on $g^{ab} \bmod p$ without either ever transmitting $a$, $b$, or the final shared secret directly.

The protocol has three phases: public parameter setup (which can be done once and reused), private key generation, and the exchange itself.

Setup (once, can be public and long-lived). Choose a large prime $p$ and a generator $g$ of a large-order subgroup of $\mathbb{Z}_p^*$. These are published or standardized (e.g., RFC 3526 / RFC 7919 groups for classical DH, or elliptic-curve groups for ECDH).

Per-session exchange. ``` // Public, agreed in advance: prime p, generator g // --- Alice --- function ALICE_STEP1(): a <- random_integer(1, p - 2) // Alice's private key A <- mod_exp(g, a, p) // A = g^a mod p send(A) to Bob store a, A function ALICE_STEP2(B): if not VALID_PUBLIC_VALUE(B, p): // reject 1, 0, p-1, etc. abort() s <- mod_exp(B, a, p) // s = B^a mod p = g^(ab) mod p return DERIVE_KEY(s) // e.g. K = KDF(s) // --- Bob --- function BOB_STEP1(): b <- random_integer(1, p - 2) // Bob's private key B <- mod_exp(g, b, p) // B = g^b mod p send(B) to Alice store b, B function BOB_STEP2(A): if not VALID_PUBLIC_VALUE(A, p): abort() s <- mod_exp(A, b, p) // s = A^b mod p = g^(ab) mod p return DERIVE_KEY(s) // --- Fast modular exponentiation (square-and-multiply) --- function mod_exp(base, exp, mod): result <- 1 base <- base mod mod while exp > 0: if exp is odd: result <- (result base) mod mod exp <- exp >> 1 base <- (base base) mod mod return result ``` `VALID_PUBLIC_VALUE` guards against small-subgroup and degenerate values (e.g. rejecting $1$, $0$, or $p-1$) — a real-world hardening step absent from the textbook description but essential in practice. `DERIVE_KEY` runs the raw shared secret $s$ through a key-derivation function (a hash-based KDF) rather than using $s$ directly as a symmetric key, since $s$ is not uniformly random and may leak structure. At the end, Alice computed $s = B^a \bmod p = (g^b)^a \bmod p = g^{ab} \bmod p$, and Bob computed $s = A^b \bmod p = (g^a)^b \bmod p = g^{ab} \bmod p$ — the same number, derived from different private inputs, using only publicly transmitted values $A$ and $B$.

Time complexity. Each party performs one modular exponentiation to produce their public value and one more to produce the shared secret — two calls to `mod_exp`. Using square-and-multiply, exponentiation with exponent of bit-length $n$ takes $O(n)$ modular multiplications, and each multiplication of $n$-bit numbers costs $O(n^2)$ with schoolbook arithmetic (or $O(n \log n)$ with fast multiplication), giving each party $O(n^3)$ total bit operations in the naive analysis, or better with optimized big-integer libraries. For $p$ a 2048-bit prime, this is a few modular multiplications' worth of work — milliseconds on ordinary hardware. Total protocol cost is $O(1)$ round trips and $O(n^3)$ (or better) computation per side; contrast this with brute-force discrete-log attacks, which cost $O(\sqrt{p})$ time using Pollard's rho for generic groups, or sub-exponential time $L_p[1/3]$ using index calculus for the multiplicative group mod $p$ specifically — astronomically larger than the honest computation for well-chosen parameter sizes (2048+ bits).

Space complexity. Each party stores $O(n)$ bits: the prime $p$, generator $g$, one private exponent, and one received public value. No party needs to store the other's private information, and no trusted third party's state is required at all.

Correctness argument. The invariant to verify is purely algebraic and requires no probabilistic reasoning: exponentiation in $\mathbb{Z}_p^*$ obeys $(g^a)^b \equiv g^{ab} \equiv (g^b)^a \pmod p$, which follows directly from the group being abelian (multiplication mod $p$ commutes, so repeated multiplication — exponentiation — composes associatively and commutatively across exponents). Alice computes $B^a \bmod p$ where $B = g^b \bmod p$, so:

Bob computes $A^b \bmod p$ where $A = g^a \bmod p$, so:

Both expressions equal $g^{ab} \bmod p$ exactly, with probability 1 — this is a deterministic algebraic identity, not a heuristic. The protocol terminates correctly on every run because modular exponentiation is a total, well-defined function on any input in $\mathbb{Z}_p$.

Security argument (informal). Correctness (both sides land on the same value) is unconditional; secrecy is conditional on a computational assumption. An eavesdropper who sees $p$, $g$, $A = g^a$, and $B = g^b$ but not $a$ or $b$ must compute $g^{ab}$ — exactly the CDH problem. No efficient algorithm for CDH is known when $p$ is large and $g$ generates a large prime-order subgroup, so the protocol is secure against passive eavesdropping under this assumption. This is a crucial qualifier: the guarantee is computational (based on unproven hardness), not information-theoretic, and it says nothing about active attackers — the man-in-the-middle caveat discussed below.

Honest tradeoffs. Classical (finite-field) Diffie-Hellman needs large parameters (2048+ bit primes) to resist index-calculus attacks, making it slower than elliptic-curve variants (ECDH), which achieve comparable security with far smaller keys (256 bits) because no sub-exponential attack analogous to index calculus is known for well-chosen elliptic curve groups. Both variants are, as currently understood, breakable by a large-scale quantum computer running Shor's algorithm, which solves discrete log (and factoring) in polynomial time — motivating post-quantum key exchange research as a distinct, harder problem.

Use small numbers purely for hand-tracing; real deployments use primes hundreds of digits long. Let the public parameters be:

($5$ generates a large subgroup of $\mathbb{Z}_{23}^*$, which has order 22.)

Both parties arrive at $s = 2$. Trace step 3 for Bob explicitly using square-and-multiply, since $15 = 1111_2$:

confirming $B = 19$. An eavesdropper Eve who intercepts $p=23$, $g=5$, $A=8$, $B=19$ would need to solve $5^a \equiv 8 \pmod{23}$ for $a$ (or the analogous equation for $b$) — trivial to brute-force here because $p$ is tiny (only 22 possible exponents), but this brute-forceability is exactly why toy primes are insecure: with $p$ a 2048-bit prime, the analogous search space makes brute force and even the best sub-exponential algorithms infeasible.

Diffie-Hellman (and its elliptic-curve descendant ECDH) underlies session-key negotiation in the TLS Handshake used by HTTPS, securing the vast majority of web traffic. SSH uses DH-family key exchange to establish encrypted terminal sessions between clients and servers. The Signal Protocol, and by extension WhatsApp and other end-to-end encrypted messengers, layers a "triple DH" (X3DH) construction atop ECDH to bootstrap secure conversations asynchronously. IPsec VPNs negotiate tunnel keys via DH during the IKE (Internet Key Exchange) phase. In every one of these deployments, raw DH is never used alone — it is always composed with authentication (certificates, pre-shared identity keys, or signatures) precisely because of the man-in-the-middle gap, and understanding that gap is a prerequisite for understanding sound Key Management in any larger security architecture.

Ask the tutor: How does the TLS handshake use ephemeral Diffie-Hellman to achieve forward secrecy while still authenticating the server?