Diffie-Hellman Key Exchange

Diffie-Hellman Key Exchange

Published by Whitfield Diffie and Martin Hellman in 1976, the Diffie-Hellman key exchange was the first practical public-key protocol. It allows two parties to establish a shared secret over an insecure channel without ever sending the secret itself.

The Protocol

Both parties agree on public parameters: a prime $p$ and a generator $g$ (a primitive root modulo $p$).

1. Alice picks a private key $a$, computes public key $A = g^a \bmod p$
2. Bob picks a private key $b$, computes public key $B = g^b \bmod p$
3. Alice and Bob exchange $A$ and $B$ publicly
4. Alice computes $s = B^a \bmod p = g^{ab} \bmod p$
5. Bob computes $s = A^b \bmod p = g^{ab} \bmod p$

Both arrive at the same shared secret $s = g^{ab} \bmod p$.

Why It's Secure

An eavesdropper sees $g$, $p$, $A = g^a \bmod p$, and $B = g^b \bmod p$, but cannot compute $g^{ab} \bmod p$ without solving the Discrete Logarithm Problem — finding $a$ from $g^a \bmod p$. This is believed to be computationally hard for large $p$.

Classic Example

$g = 2$, $p = 23$ (a prime), $a = 6$, $b = 15$:

Shared secret: $B^a \bmod 23 = 16^6 \bmod 23 = 4 = A^b \bmod 23$.

Your Task

Implement:

• dh_public_key(g, private_key, p) — compute $g^{\text{private\_key}} \bmod p$
• dh_shared_secret(other_public, private_key, p) — compute $\text{other\_public}^{\text{private\_key}} \bmod p$