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.

The protocol has 4 parts: define public parameters, generate key pairs, exchange public keys, compute the shared secret.

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$ 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.

Here:

• $q$: the Sophie Germain prime paired with $p$

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

Here:

• $q_i$: a distinct prime factor of $p - 1$

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, or 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$.

Worked Example

$p = 23$, $g = 5$, $a = 6$, $b = 15$.

• $A = 5^6 \bmod 23$.
• $B = 5^{15} \bmod 23$.
• Alice computes $k = B^6 \bmod 23 = 2$.
• Bob computes $k = A^{15} \bmod 23 = 2$.

Ephemeral Diffie-Hellman

Ephemeral Diffie-Hellman (DHE) generates a fresh key pair for every session and deletes both private keys once the shared secret is set up. Long-term keys authenticate the exchange only, they do not derive the session key.

This gives perfect forward secrecy: if the long-term keys are stolen later, past session keys stay safe, because the private keys that produced them no longer exist and cannot be recovered from the recorded public values.

Static DH

Both parties reuse the same key pair across every session instead of generating a fresh one.

• A single compromised private key exposes every past and future session, since the same $a$ or $b$ derives every session’s shared secret.
• Costs 1 exponentiation total per party, instead of 1 per session.

Authenticating the Ephemeral Keys

Raw DH has no identity binding, so a fresh, unsigned $A$ or $B$ is exactly what a man-in-the-middle substitutes. DHE fixes this by signing the ephemeral public key with a separate long-term signing key, not by deriving the session key from it.

• Alice signs $A$ with her long-term private signing key, sends $(A, \text{signature})$.
• Bob verifies the signature against Alice’s long-term public key, then proceeds with $A$ exactly as in plain DH.

Why forward secrecy holds:

• $a$ and $b$ are generated fresh per session and destroyed once $k$ is computed.
• Recovering $a$ from the recorded public $A$ requires solving the DLP, not merely knowing the long-term signing key.
• A long-term key compromised later lets an attacker forge future signatures, but supplies no way to recompute a past session’s $a$ or $b$.

Man-in-the-Middle Attack

The basic DH protocol has no authentication of public keys, so it is vulnerable to a man-in-the-middle attack.

Mallory now holds a separate shared key with each party, and can decrypt, inspect, modify, or inject messages in the supposedly secure channel between Alice and Bob.

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.