Diffie-Hellman & Key Exchange

Diffie–Hellman (1976) was the first published solution to a problem that had looked impossible: two parties who have never met, communicating entirely over a channel an adversary can read, end up holding the same secret. It is the mechanism behind forward secrecy in TLS, the handshake in Signal and WireGuard, and — with the group swapped for an elliptic curve — essentially every session key negotiated on the internet today.

The protocol #

Agree publicly on a large prime $p$ and a generator $g$. These are not secret and are typically shared by everyone.

$$\begin{aligned} &\text{Alice picks secret } a, \text{ sends } A = g^a \bmod p \\ &\text{Bob picks secret } b, \text{ sends } B = g^b \bmod p \\ &\text{Alice computes } B^a = g^{ba}, \quad \text{Bob computes } A^b = g^{ab} \end{aligned}$$

Both hold $g^{ab} \bmod p$. An eavesdropper has $p, g, A, B$ and must compute $g^{ab}$ from $g^a$ and $g^b$ — the Computational Diffie–Hellman problem. Solving the discrete logarithm would break it; whether the two are equivalent is still open.

Unauthenticated DH is trivially MITM'd #

DH gives you a shared secret with somebody. It says nothing about who.

sequenceDiagram
    participant A as Alice
    participant M as Mallory
    participant B as Bob
    A->>M: g^a
    M->>B: g^m
    B->>M: g^b
    M->>A: g^m
    Note over A,M: shared key g^am
    Note over M,B: shared key g^mb
    Note over M: decrypts, reads, re-encrypts — both sides see a valid session

Mallory runs two exchanges and relays. Neither side detects anything. The fix is always to authenticate the exchange: sign the DH share (digital signatures + a certificate, as TLS does), or bind it to a pre-shared identity key (Signal's X3DH, WireGuard's Noise handshake). Anonymous DH ciphersuites were removed from TLS for exactly this reason.

Why ephemeral: forward secrecy #

If both sides reuse long-term DH secrets (static DH), one later key compromise decrypts every past session an attacker recorded. With ephemeral exponents — fresh $a$, $b$ per handshake, discarded afterwards (DHE/ECDHE) — a compromised long-term signing key lets an attacker impersonate you going forward but cannot retroactively decrypt captured traffic. This is forward secrecy, and it is the single strongest argument for DH over RSA key transport. TLS 1.3 made it mandatory by deleting RSA key exchange from the protocol.

Parameter choice is where it breaks #

Practical guidance today: use X25519 (RFC 7748) unless a compliance regime forces finite-field DH; if it does, use RFC 7919 named groups at 2048+ bits and never a self-generated or hardcoded prime of unknown provenance.

Key agreement is a protocol, not one multiplication #

NIST SP 800-56A Rev. 3 makes explicit what textbook DH leaves implicit. A conforming key-establishment scheme includes approved domain parameters, key-pair generation, assurances about private and public keys, a shared-secret computation, a key-derivation method, identifiers/context, error handling, and—where required—key confirmation.

The derived keying material should bind the parties and protocol purpose through FixedInfo or an equivalent transcript/context input. Otherwise the same mathematical shared secret can be interpreted under different roles or protocols. Key confirmation adds a MAC under derived confirmation material so one party proves it actually derived the same key; it is distinct from identity authentication.

Static and ephemeral keys also change the guarantees:

The publication was issued in 2018, and NIST announced in January 2026 that a revision is planned to align it with SP 800-186 and newer requirements. Use Rev. 3 for the current complete scheme mechanics while checking the NIST publication page for transition updates.

ElGamal: DH turned into an encryption scheme #

ElGamal (1985) is Diffie–Hellman restructured so the sender needn't wait for a reply. The recipient publishes $(p, g, y)$ where $y = g^x \bmod p$ and $x$ is private. To encrypt, the sender picks a random $k$ and sends the pair:

$$(c_1, c_2) = \left(g^k \bmod p,\ m \cdot y^k \bmod p\right)$$

The recipient computes $c_1^x = g^{kx} = y^k$ and divides it out. In practice $y^k$ is used as a symmetric key for a real cipher rather than multiplied into the message, which makes it a hybrid scheme.

Source claims audit #

Seeded from a university lab manual (Diffie–Hellman / ElGamal lab). Status of its load-bearing claims: