Alice and Bob each pick a secret exponent, exchange $g^a \mod p$ and $g^b \mod p$ publicly, then independently compute the shared secret $K = g^{ab} \mod p$.

* Both sides reach K = g^(ab) mod p; only g^a and g^b ever cross the wire. *

Public parameters: Prime $p$ and generator $g$ of $\mathbb{Z}_p^*$

Protocol:

1. Alice: Chooses secret $a$, computes $A = g^a \mod p$, sends $A$ to Bob
2. Bob: Chooses secret $b$, computes $B = g^b \mod p$, sends $B$ to Alice
3. Alice computes: $K = B^a = (g^b)^a = g^{ba} \mod p$
4. Bob computes: $K = A^b = (g^a)^b = g^{ab} \mod p$

Both arrive at the same key $K = g^{ab} \mod p$ without it ever crossing the channel!

What Eve sees: $p$, $g$, $A = g^a \mod p$, $B = g^b \mod p$. To find $K$, she'd need $a$ or $b$ — which requires solving the discrete logarithm problem (infeasible for large $p$).

Critical limitation: DH is a key exchange protocol only — it cannot encrypt messages or create signatures. Neither Alice nor Bob can choose what the shared key will be; it's determined by both random exponents.

Go deeper:

• Secret Key Exchange (Diffie-Hellman) — Computerphile — the paint-mixing intuition for the whole exchange.
• Diffie-Hellman key exchange — Wikipedia — canonical reference for the protocol and its math.

With p=31 and generator g=3: Alice picks a=8, sends $3^8 \mod 31 = 20$. Bob picks b=6, sends $3^6 \mod 31 = 16$. Both compute $K = 4$.

* Worked example: secrets a=8 and b=6 both land on the shared key K = 4. *

The reason to work it with tiny numbers is to watch the two sides land on the same $K$ without it ever crossing the wire — and to feel why the security evaporates once $p$ is small: here Eve really could just try every exponent, which is exactly the work that becomes hopeless when $p$ has hundreds of digits.

Setup: $p = 31$, $g = 3$ (a generator of $\mathbb{Z}_{31}^*$)

Alice (secret a = 8):

• Computes $A = 3^8 \mod 31 = 6561 \mod 31 = 20$
• Sends $A = 20$ to Bob

Bob (secret b = 6):

• Computes $B = 3^6 \mod 31 = 729 \mod 31 = 16$
• Sends $B = 16$ to Alice

Shared key computation:

• Alice: $K = 16^8 \mod 31 = 4$
• Bob: $K = 20^6 \mod 31 = 4$

Both get $K = 4$ — the shared secret!

Eve knows: $p = 31$, $g = 3$, $A = 20$, $B = 16$. She'd need to solve $3^a \equiv 20 \mod 31$ to find $a = 8$ — easy for small numbers, but infeasible when $p$ has 1000+ digits.

Go deeper:

• Diffie-Hellman, the Mathematics bit — Computerphile — works the modular exponentiation by hand.
• Diffie-Hellman key exchange — Wikipedia — includes its own worked numeric example.