Diffie-Hellman Key Exchange

Diffie-Hellman (DH), invented in 1976 by Whitfield Diffie and Martin Hellman, lets 2 parties agree on a shared secret key using only publicly exchanged information. Security rests on the difficulty of computing discrete logarithms.

This is the Discrete Logarithm Problem (DLP) over the finite field $\mathbb{Z}_p^*$: recovering the secret $a$ from $g^a \bmod p$ is computationally intractable for large $p$, while computing $g^a \bmod p$ from $a$ is cheap.

The interactive guide to Diffie-Hellman key exchange walks through the exchange and the discrete logarithm problem behind it.

Public Parameters

• A large prime modulus $p$, defining the multiplicative group $\mathbb{Z}_p^*$.
• A generator $g$, a primitive root modulo $p$.

$g$ is a primitive root modulo $p$ iff every $a$ coprime to $p$ (i.e. $\gcd(a,p) = 1$) satisfies $a \equiv g^i \pmod p$ for some integer $i$, called the discrete logarithm of $a$ to base $g$.

For prime $p$, the $p - 1$ values $i = 1, \dots, p-1$ generate $\{1, \dots, p-1\}$, in some order, via $g^i \bmod p$.

Choosing $g$ as a primitive root maximises the order of the group it generates to $p - 1$, so its powers span every non-zero residue class modulo $p$ and stay in no small subgroup, where the discrete logarithm would be easy to solve.

Choosing a Modulus

$p$ is chosen as a safe prime: a prime of the form $p = 2q + 1$ where $q$ is also prime. $(p,q)$ are a Sophie-Germain prime pair.

Reasons:

• Pohlig-Hellman reduces the discrete logarithm modulo $p$ to one discrete logarithm per prime factor of $p - 1$. A safe prime forces $p - 1 = 2q$, leaving only the factors $2$ and the large prime $q$.
• No small-order subgroup exists, so an attacker cannot confine the shared secret to a short list of values.
• Every $g \neq \pm 1$ has order $q$ or $2q$, so almost any candidate generates a large group.

Choosing a Generator

Factor $p - 1$ into its distinct prime factors $q_1, \dots, q_k$. Then $g$ is a primitive root modulo $p$ iff

Test $g = 2, 3, 5, \dots$ in turn. Primitive roots are dense, so a small $g$ passes after few tries. Each candidate costs $k$ modular exponentiations.

Factoring $p - 1$ is the hard step, so $p$ is chosen in advance to keep it known.

A safe prime is a prime $p = 2q + 1$ where $q$ is also prime. Then $p - 1 = 2q$ has 2 prime factors, so $g$ is a primitive root iff $g^2 \not\equiv 1 \pmod p$ and $g^q \not\equiv 1 \pmod p$. Published standards use safe primes and usually take $g = 2$.

For $p = 23$, $p - 1 = 22 = 2 \cdot 11$. Testing $g = 5$ gives $5^2 \equiv 2$ and $5^{11} \equiv 22$. Neither is $1$, so $5$ is a primitive root. $g = 2$ fails, since $2^{11} \equiv 1 \pmod{23}$.

Key Pair Generation

Each party chooses a secret integer and publishes its exponentiation modulo $p$.

• Alice chooses secret $a \in \mathbb{Z}_p^*$, computes public $A \equiv g^a \pmod p$.
• Bob chooses secret $b \in \mathbb{Z}_p^*$, computes public $B \equiv g^b \pmod p$.

Exchange of Public Keys

Public keys need no confidentiality, only authenticity and integrity, since a forged public key lets an attacker substitute their own key undetected.

Methods:

• a trusted public key server
• in-person or verified exchange
• a CA-issued digital certificate.

Shared Secret Key

Alice computes $k = B^a \bmod p = g^{ba} \bmod p$. Bob computes $k = A^b \bmod p = g^{ab} \bmod p$. Both arrive at the same value since $g^{ab} \equiv g^{ba} \pmod p$.

Ephemeral Diffie-Hellman

Also known as DHE. Runs a new DH exchange for every session.

Session Lifecycle

• Alice generates a fresh DH exponent $a_s$, computes $A_s = g^{a_s} \bmod p$
• Bob generates a fresh DH exponent $b_s$, computes $B_s = g^{b_s} \bmod p$
• Both derive $k_s = g^{a_sb_s} \bmod p$ and use a key derivation function to obtain session traffic keys.
• Both delete $a_s$ and $b_s$ after the exchange.

This gives perfect forward secrecy. If an attacker steals a long-term authentication key later, past session keys remain unavailable because the ephemeral private exponents no longer exist. Recovering $a_s$ or $b_s$ from recorded public values requires solving the DLP.

Normal DH reuses the same private exponents across sessions. A compromised static private exponent exposes every session derived from it. DHE adds fresh public-key generation for every session. Both forms still require 1 shared-secret exponentiation per party per session.

Authenticating the Ephemeral Keys

Raw DHE has no identity binding. A fresh, unsigned $A_s$ or $B_s$ is exactly what a man-in-the-middle substitutes. DHE provides forward secrecy, not authentication.

A protocol combines DHE with long-term signatures or certificates to authenticate the ephemeral public keys. The authentication key proves the sender’s identity. The ephemeral private exponent derives the session secret.

• Alice signs the exchange with $SK_A$, sends $(A_s, \text{signature})$.
• Bob verifies the signature with $PK_A$, then proceeds with $A_s$ exactly as in plain DH.

ECDHE

Also known as Elliptic-Curve Ephemeral Diffie-Hellman. Uses an elliptic-curve group instead of the multiplicative group $\mathbb{Z}_p^*$.

• The curve and base point $G$ are public parameters.
• Alice chooses a fresh private scalar $a_s$ and sends the public point $A_s = a_sG$.
• Bob chooses a fresh private scalar $b_s$ and sends the public point $B_s = b_sG$.
• Alice computes $S = a_sB_s$.
• Bob computes $S = b_sA_s$.

Both obtain $S = a_sb_sG$. A key derivation function converts $S$ into session traffic keys. Recovering $a_s$ from $A_s$ requires solving the Elliptic-Curve Discrete Logarithm Problem.

ECDHE keeps the same roles as DHE. The ephemeral scalars derive $S$. Long-term keys authenticate the exchanged points. ECDHE uses smaller public keys for comparable security.

Man-in-the-Middle Attack

Preventing the Attack

The attack works because $A$ and $B$ carry no proof of who sent them. Every fix binds the exchanged keys to a verified identity.

• Digital signature
  Sign the exchanged public key with a long-term signing key, as in ephemeral DH authentication. Bob verifies the signature before trusting $A$.
• Certificate
  A CA-issued certificate binds a long-term public key to an identity, letting Bob verify Alice’s signing key without a prior direct exchange with her.
• Station-to-Station protocol
  Each party signs both exchanged values $A$ and $B$ together and encrypts the signature under the just-derived shared key. Mallory’s substituted keys cannot produce a valid signature over the real $A$ and $B$.
• Out-of-band verification
  Compare a short fingerprint of the exchanged keys over a separate trusted channel, e.g. reading it aloud on a phone call.

Every fix needs a trust anchor Mallory cannot also forge or intercept, a long-term signing key, a CA, or a side channel. Plain DH supplies none of these on its own.

Worked Examples

Choosing $p$

Select the safe prime $p$ from $15$, $17$, $19$, $23$, and $29$.

Evaluate every candidate before revealing the solution.

Choosing $q$

Let $p = 23$. Select the value of $q$ satisfying $p = 2q + 1$ from $7$, $9$, $11$, $13$, and $15$.

Evaluate every candidate before revealing the solution.

Alice’s Calculations

Let $p = 23$, $g = 5$, $a = 6$, and $B = 19$. Select Alice’s public key $A$ and shared secret $k$:

• $(A,k) = (4,2)$
• $(A,k) = (8,2)$
• $(A,k) = (8,4)$
• $(A,k) = (16,2)$
• $(A,k) = (8,19)$

Compute both values before revealing the solution.

Bob’s Calculations

Let $p = 23$, $g = 5$, $b = 15$, and $A = 8$. Select Bob’s public key $B$ and shared secret $k$:

• $(B,k) = (8,2)$
• $(B,k) = (19,2)$
• $(B,k) = (19,4)$
• $(B,k) = (16,2)$
• $(B,k) = (19,8)$

Compute both values before revealing the solution.