difficulty levels — click green to claim

> DIFFIE–HELLMAN KEY EXCHANGE

diffie-hellman difficulty: 4–7 field: public-key cryptography

The idea in plain English — the paint analogy: Imagine Alice and Bob each have a can of paint. They want to end up with the same secret color but can only talk in front of an eavesdropper (Eve). Here's the trick:

Alice and Bob publicly agree on a common color (say, yellow). Everyone knows this.
Alice mixes her own secret color (say, red) with the yellow → sends the mixture to Bob.
Bob mixes his own secret color (say, blue) with the yellow → sends the mixture to Alice.
Alice adds her secret red to Bob's mixture → she gets yellow+red+blue = brown.
Bob adds his secret blue to Alice's mixture → he gets yellow+blue+red = the same brown.

Eve sees the yellow, the yellow-red mixture, and the yellow-blue mixture — but she never sees the individual secret colors, so she can't recreate the shared brown. That's Diffie–Hellman. The math equivalent uses modular exponentiation instead of paint, but the logic is identical: two parties mix a public base with their private secrets, swap the results, then mix again with their own secret to arrive at a shared value.

Why this really exists: Before Diffie–Hellman, two parties who had never met simply could not establish a shared secret over an insecure channel. Every encryption system required a key to be delivered in person, by courier, or by some other pre-arranged method (this is the key distribution problem). Diffie–Hellman solved it with 30 lines of math. Every HTTPS connection, every secure chat, every VPN — they all use this idea, often in elliptic-curve form (ECDH). It is the foundation of forward secrecy: even if a server's long-term key is stolen later, past sessions remain secure because the ephemeral DH keys are discarded.

▸ Concrete Example

Public parameters: prime p = 23, generator g = 5.

Alice picks secret a = 6 → sends Bob: g^a mod p = 5⁶ mod 23 = 8
Bob picks secret b = 15 → sends Alice: g^b mod p = 5¹⁵ mod 23 = 19

Alice computes: (g^b)^a mod p = 19⁶ mod 23 = 2
Bob computes: (g^a)^b mod p = 8¹⁵ mod 23 = 2 ✓

Shared secret = 2. Eve sees only 8 and 19 (and p=23, g=5) — finding the secret requires solving the discrete log problem.

With small numbers like this, Eve could brute-force: try every possible secret a (0–22) and see if g^a mod 23 equals 8. But with p of size 2²⁰⁴⁸ (the modern standard), that's computationally infeasible. The puzzle keeps p small enough to be solvable with baby-step-giant-step or simple brute force.

▸ How to Solve (Step by Step)

1. You are given p, g, and the two public values (g^a mod p, g^b mod p)

2. Compute Alice's secret a = discrete_log(g, g^a mod p) — use baby-step-giant-step or Pollard's rho

3. Compute shared secret s = (g^b)^a mod p

4. The shared secret s is an ASCII code (or concatenation of codes)

5. Convert to character(s) → the answer word

def discrete_log(g, h, p):
  m = int(p**0.5) + 1
  table = {pow(g, j, p): j for j in range(m)}
  factor = pow(g, -m, p)  # g^(-m) mod p
  cur = h
  for i in range(m):
    if cur in table:
      return i * m + table[cur]
    cur = (cur * factor) % p
  return None

a = discrete_log(5, 8, 23)  # → 6
s = pow(19, a, 23)  # → 2 = shared secret

▸ Why This Matters — History

1976: Whitfield Diffie and Martin Hellman publish "New Directions in Cryptography" — the paper that invents public-key cryptography. The key exchange is their landmark contribution.
1974 (classified): Malcolm J. Williamson at GCHQ (UK intelligence) independently discovered the same scheme three years earlier — but it remained a government secret until 1997.
Modern impact: Every HTTPS connection uses ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) for forward secrecy. Signal, WhatsApp, iMessage all rely on DH-style key agreement.
Post-quantum future: DH is broken by Shor's algorithm on a quantum computer — which is why NIST standardized ML-KEM (Kyber) as a replacement in 2024.

▸ Real-World Applications

HTTPS/TLS: Every encrypted website uses ECDHE during the TLS handshake to agree on session keys
SSH: The key exchange phase of SSH uses Diffie–Hellman (often Curve25519)
VPNs: WireGuard, IPsec, OpenVPN all use DH-style key agreement for session establishment
End-to-end encryption: Signal's X3DH protocol uses DH for initial key agreement between devices
Blockchain: Many cryptocurrency wallets use ECDH for stealth addresses and key derivation

← Back to all ciphers