Skip to content

🤝 07-05: Diffie-Hellman Key Exchange

📌 The Problem: Agreeing on a Secret in Public

RSA (see 07-04: Asymmetric Encryption (RSA)) solves the key distribution problem by letting anyone encrypt a message that only one specific private key can decrypt. But there's a second, subtly different problem worth solving directly:

Can two people who have never met, talking over a line an attacker is actively listening to, agree on a shared secret number — without ever transmitting that secret itself?

This sounds impossible at first. If Alice and Bob only ever send messages an eavesdropper (traditionally named Eve) can also see, how could they end up knowing something Eve doesn't?

Diffie-Hellman (DH) key exchange, published in 1976 by Whitfield Diffie and Martin Hellman, answers "yes" — and it does it with elegant, verifiable math, not obscurity.

💡 Diffie-Hellman doesn't encrypt messages the way RSA does — it's specifically a way for two parties to derive the same shared secret key, which they then typically use as the key for a fast symmetric cipher like AES (07-03: AES & Block Cipher Modes). This exact pattern — DH to agree on a key, then AES to encrypt — is at the heart of how TLS establishes a secure connection (Module 09).

🎨 The Paint-Mixing Analogy

Before the math, here's the intuition. Imagine mixing paint colors:

  1. Alice and Bob publicly agree on a common starting color (say, yellow) — anyone watching sees this.
  2. Alice privately picks a secret color and mixes it with the yellow, sending the resulting mixture to Bob (not her secret color itself).
  3. Bob does the same: picks his own secret color, mixes it with the yellow, and sends his mixture to Alice.
  4. Now Alice takes Bob's mixture and adds her own secret color to it. Bob takes Alice's mixture and adds his own secret color to it.
  5. Both end up with the exact same final color — because mixing is associative (order doesn't matter to the end result), but neither Alice's nor Bob's individual secret color can be "un-mixed" back out of the shared mixtures that were sent over the public channel.

An eavesdropper who only ever saw the yellow base and the two mixed colors sent over the wire cannot reverse the mixing to figure out either secret color — mixing paint is a one-way process. This is the intuitive version of what mathematicians call a one-way function.

🔢 The Real Math: Modular Exponentiation

Diffie-Hellman replaces "mixing paint" with modular exponentiation, which is easy to compute forward but extremely hard to reverse — this hardness is called the discrete logarithm problem.

Public Setup (known to everyone, including any eavesdropper)

p = 23   (a public prime number, the "modulus")
g = 5    (a public "generator" number)

Both p and g can be shouted across the room — they carry no secrecy on their own.

Step 1: Each Side Picks a Private Secret

Alice picks: a = 6   (never shared with anyone)
Bob picks:   b = 15  (never shared with anyone)

Step 2: Each Side Computes a Public Value

Alice computes: A = g^a mod p = 5^6 mod 23  = 8
Bob computes:   B = g^b mod p = 5^15 mod 23 = 19

Alice sends A = 8 to Bob. Bob sends B = 19 to Alice. These values travel over the open network — an eavesdropper (Eve) sees both 8 and 19, plus the public p=23 and g=5.

Step 3: Each Side Computes the Shared Secret

Now the key trick: each side raises the other side's public value to their own private exponent.

Alice computes: s = B^a mod p = 19^6 mod 23  = 2
Bob computes:   s = A^b mod p = 8^15 mod 23  = 2

Both Alice and Bob arrive at s = 2 — the identical shared secret — without either one ever transmitting a, b, or s itself over the network.

Party Knows Computes
Alice p=23, g=5, a=6 (secret), receives B=19 19^6 mod 23 = 2
Bob p=23, g=5, b=15 (secret), receives A=8 8^15 mod 23 = 2
Eve (eavesdropper) p=23, g=5, A=8, B=19 — everything sent over the wire Cannot compute 2 without solving the discrete log problem

💡 Why does this work? Because (g^a)^b mod p = (g^b)^a mod p = g^(ab) mod p — exponents multiply regardless of the order you apply them. Alice computes g^(ab) by raising Bob's g^b to her own a; Bob computes the same value by raising Alice's g^a to his own b. Both paths lead to the same number.

🚫 Why Eve Can't Just Compute It Too

Eve sees everything that crossed the network: p=23, g=5, A=8, B=19. Why can't she compute the shared secret the same way?

Because to follow either side's path, Eve would need Alice's private a or Bob's private b — and the only way to recover those from the public values is to reverse A = g^a mod p, solving for a. That reversal is the discrete logarithm problem: given g, p, and A, find the exponent a such that g^a mod p = A.

  • Forward direction (computing A from a): fast, even for enormous numbers — this is ordinary modular exponentiation.
  • Backward direction (computing a from A): for our toy example with p=23, Eve could just try every exponent from 1 to 22 and brute-force it in seconds.
  • At real-world scale, p is a prime hundreds of digits long. Brute-forcing every possible exponent, or using the best known mathematical shortcuts, is believed to take longer than the age of the universe with classical computers.

💥 This asymmetry — trivial to compute forward, infeasible to reverse at scale — is called a one-way function, and it's the same broad category of "easy forward, hard backward" math that RSA's prime factorization problem belongs to. Different math problem, same underlying strategy: build security on a computation that's provably lopsided in difficulty.

⚖️ Diffie-Hellman vs. RSA

Both solve problems related to "how do strangers communicate securely," but they solve different problems:

RSA Diffie-Hellman
Purpose Encrypt a message directly to a recipient's public key Derive a shared secret key between two parties
Hard problem it relies on Factoring large numbers Discrete logarithm
Output Ciphertext A shared secret (used as a symmetric key)
Typical real-world use Encrypting a symmetric key, or making digital signatures (07-07: Digital Signatures) Establishing a fresh session key for AES, every connection

💡 Modern TLS connections typically use a variant called Ephemeral Diffie-Hellman (DHE / ECDHE), which generates brand-new a and b values for every single connection. This gives a property called forward secrecy: even if an attacker later steals a server's long-term private key, they still cannot decrypt past conversations, because each conversation's key was derived from private values that were thrown away the moment the connection ended.

📌 Key Takeaways

  • Diffie-Hellman key exchange lets two parties agree on a shared secret over a public network without ever transmitting the secret itself.
  • The paint-mixing analogy: combine a public base color with a private secret color, exchange the mixtures, then each side adds their own secret again to land on the same final color.
  • The real math uses modular exponentiation: public p (prime) and g (generator), private exponents a and b, public values A = g^a mod p and B = g^b mod p.
  • Both sides compute the same shared secret: Alice via B^a mod p, Bob via A^b mod p — both equal g^(ab) mod p.
  • Worked example: p=23, g=5, a=6, b=15 → A=8, B=19 → shared secret = 2 for both sides.
  • An eavesdropper sees p, g, A, and B, but cannot derive the shared secret without solving the discrete logarithm problem — feasible to brute-force at toy scale, computationally infeasible at real-world scale (hundreds-of-digits primes).
  • RSA and Diffie-Hellman both rely on one-way functions but solve different problems: RSA encrypts directly to a public key; DH derives a shared symmetric key.
  • Modern protocols use ephemeral Diffie-Hellman (DHE/ECDHE), generating fresh private values per connection to provide forward secrecy — a concept central to how TLS 1.3 (Module 09) protects past sessions even if a server's key is later compromised.