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.

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

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: $k = B^6 \bmod 23 = 2$.
• Bob: $k = A^{15} \bmod 23 = 2$.

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.