The Key Exchange Problem
Symmetric encryption (Chapter 3's DES/AES) needs both parties to share the same secret key before they can talk securely. But how do you agree on a secret number with someone over a line that anyone can listen to — without ever meeting them in person to hand over a key? That is the problem Diffie-Hellman solves.
Mnemonic — "76 for the Win, 70 in the Dark"
"Diffie & Hellman '76 went public; Williamson '70 stayed secret." If asked "who invented DH and when," the safe textbook answer is Diffie & Hellman, 1976 — Williamson is the trivia footnote for "who actually thought of it first but couldn't publish."
A Key-Distribution Scheme, Not a Cipher
It is critical to understand what Diffie-Hellman is for. It does not encrypt or send messages at all — it only helps two parties land on the same shared number.
It is a public-key distribution scheme. It lets two participants establish a common key, known only to the two of them. The value of that key depends on both participants' private and public key information.
It cannot be used to exchange an arbitrary message — you can't just "Diffie-Hellman" a sentence to someone. It only ever produces a shared secret number, which is then typically fed into a symmetric cipher like AES as the session key.
Easy one way, hard the other
DH is based on exponentiation in a finite (Galois) field — modulo a prime, or a polynomial — which is computationally easy. Its security instead relies on the difficulty of computing discrete logarithms (a problem similar in spirit to factoring), which is hard. The whole scheme is a "one-way street": easy forward, hard in reverse.
Mnemonic — "Distribute, Don't Deliver"
"DH ships a key, not a letter." If an exam question describes sending an actual message through Diffie-Hellman, it's testing whether you know that's not what it's for — DH only ever distributes/establishes a shared key.
Primitive Roots
Before the exchange can happen, everyone must agree on two public numbers: a prime q and a primitive root of that prime, called a.
A primitive root a of a number q is a value whose successive powers (a¹, a², a³, … mod q) generate all the nonzero elements 1 through q−1, in some order, before repeating. In other words, raising a to powers "cycles through everything" mod q, except 0.
Why it matters
Using a primitive root as the generator guarantees the public values yA and yB can take on the full range of possible outputs, which is what makes brute-forcing or guessing the private exponent hard — the output space is as large and unpredictable as possible.
Mnemonic — "Root That Reaches Everywhere"
"Primitive = touches every number." A primitive root's powers "walk" to every nonzero residue mod q before looping back — like a generator that can reach every seat in the room, not just some of them.
Diffie-Hellman Setup
The protocol has two phases: agreeing on public global parameters, then each user privately generating their own key pair.
Step 1 — Agree on Global (Public) Parameters
Step 2 — Each User Generates Their Own Key
Choose a secret key
User A picks a secret number xA where xA < q. This exponent is never transmitted — it stays private forever.
Compute the public key
User A computes yA = axA mod q. This result is sent out publicly.
Publish it
Each user makes their public key yA available to the other party (and, implicitly, to anyone listening on the wire).
Mnemonic — "PPP: Public Prime, Public root, Private exponent"
"Two things are public before you even start (q and a); one thing is private and yours alone (x); the fourth (y) becomes public once you compute it." If you remember which letters are public (q, a, yA, yB) vs. private (xA, xB), the rest of the math falls into place.
Computing the Shared Secret
Once A and B have swapped their public values yA and yB, each side can independently compute the same shared session key KAB — without ever transmitting their private exponent, and without the other side's private exponent either.
KAB = axA·xB mod q
= yAxB mod q (computed by B)
= yBxA mod q (computed by A)
Both computations land on the exact same number, because exponents combine multiplicatively: (axA)xB = (axB)xA = axA·xB, all mod q. Neither side ever needed to know the other's private exponent — each only ever raised the other side's public value to their own private exponent.
Session key use
KAB becomes the shared session key used inside a symmetric-key encryption scheme (like AES) between Alice and Bob — DH itself doesn't encrypt anything.
Consistency across sessions
If Alice and Bob communicate again later, they'll re-derive the same key — unless one of them chooses new public keys, which produces a fresh shared secret.
Why an attacker is stuck
An eavesdropper sees q, a, yA, and yB — all public. To recover xA (or xB) and thus compute KAB, the attacker must solve yA = axA mod q for xA. That's the discrete logarithm problem — computationally hard for large q, which is exactly what keeps DH secure.
Mnemonic — "Swap Public, Raise to Your Own Private"
"Take THEIR public number, raise it to YOUR private number." A takes yB (Bob's public value) and raises it to xA (Alice's own private exponent). B takes yA (Alice's public value) and raises it to xB (Bob's own private exponent). Cross the public, keep the private — that's the whole trick.
Diffie-Hellman Example — Full Walkthrough
This is the exact numeric example from the slides — small numbers, so it's easy to follow the arithmetic by hand (or on a calculator with modular exponentiation).
Step 1 — Agree on Public Parameters
Alice & Bob agree on prime q = 353 and primitive root a = 3.
Step 2 — Each Selects a Secret Key
xA = 97
xB = 233
Step 3 — Compute Public Keys
yA = 397 mod 353 = 40
yB = 3233 mod 353 = 248
Step 4 — Compute the Shared Session Key
KAB = yBxA mod 353 = 24897 mod 353 = 160
KAB = yAxB mod 353 = 40233 mod 353 = 160
Both land on 160
Alice and Bob independently arrive at the same shared secret, KAB = 160, without either one ever transmitting their private exponent (97 or 233) over the wire. Only q, a, yA (40), and yB (248) ever crossed the insecure channel.
| Quantity | Value | Public or Private? |
|---|---|---|
| q (prime modulus) | 353 | Public |
| a (primitive root) | 3 | Public |
| xA (Alice's secret) | 97 | Private — never sent |
| xB (Bob's secret) | 233 | Private — never sent |
| yA = 397 mod 353 | 40 | Public — transmitted |
| yB = 3233 mod 353 | 248 | Public — transmitted |
| KAB (shared session key) | 160 | Never transmitted — derived independently |
Mnemonic — "353-3-97-233-40-248-160"
"Small prime, small root, big secrets, matching answer." You don't need to memorize these exact digits for an exam — but do remember the pattern: 2 public setup numbers (q, a) → 2 private secrets (xA, xB) → 2 public keys (yA, yB) → 1 matching shared secret (KAB) that both sides compute separately and always agree on.
Key Exchange Protocols & the Man-in-the-Middle Attack
Two common ways to use DH in practice, and why both are vulnerable without extra protection:
Users create a random private/public DH key pair fresh each time they communicate. Good for forward secrecy, but nothing proves who you're really talking to.
Users create a known private/public DH key and publish it in a directory; others consult the directory and use it to securely communicate. Convenient, but also nothing proves the directory entry is genuine.
The core weakness
Both approaches are vulnerable to a Man-in-the-Middle (MITM) attack. Plain DH provides secrecy of the resulting key, but it provides no authentication of who you're exchanging keys with — nothing proves that the public value you received really came from Alice or Bob and not an impostor.
Man-in-the-Middle — Step by Step (Darth intercepts Alice & Bob)
Darth prepares
Darth creates two separate private/public DH key pairs ahead of time — one to use toward Alice, one to use toward Bob.
Alice transmits her public key
Alice sends her public key, intending it for Bob.
Darth intercepts and substitutes
Darth intercepts Alice's public key. He transmits his own first public key to Bob instead, and calculates a shared key with Alice using her real public key.
Bob unknowingly shares a key with Darth
Bob receives what he thinks is Alice's public key (really Darth's) and computes a shared key — but it's shared with Darth, not Alice.
Bob transmits his public key
Bob sends his public key back, intending it for Alice.
Darth intercepts again
Darth intercepts Bob's public key, transmits his second public key to Alice instead, and calculates a shared key with Bob using Bob's real public key.
Alice unknowingly shares a key with Darth
Alice receives what she thinks is Bob's public key (really Darth's second key) and computes a shared key — shared with Darth, not Bob.
Darth now shares one key with Alice and a different key with Bob. Every message Alice sends, Darth can decrypt (with the Alice-key), read or modify, re-encrypt (with the Bob-key), and forward to Bob — and vice versa. Neither Alice nor Bob notices anything is wrong, because each one's traffic still decrypts correctly on their end.
Mnemonic — "Darth Wears Two Masks"
"One key for Alice's face, one key for Bob's face." Darth needs two separate key pairs — never one — because he must independently fool each side into thinking he's the other person. The fix in real life is authentication: signed public keys (certificates) or a pre-shared authentication step so Alice and Bob can verify whose public value they actually received.
Where Diffie-Hellman Shows Up Today
Because plain DH has no authentication, real-world protocols pair it with a separate authentication mechanism (certificates, signatures, or a pre-shared secret) rather than using it naked.
TLS / HTTPS
Modern TLS handshakes commonly use Ephemeral Diffie-Hellman (DHE / ECDHE) to establish a fresh session key for every connection, then rely on the server's certificate (signed by a trusted CA) to authenticate the exchange and defeat MITM.
IPsec
The IKE (Internet Key Exchange) protocol inside IPsec uses DH to negotiate shared keying material between two endpoints, combined with authentication (pre-shared keys or certificates).
Ephemeral DH (Forward Secrecy)
Generating a brand-new DH key pair for every session means that even if a long-term key is later compromised, past session keys can't be recovered — this property is called forward secrecy.
Mnemonic — "Ephemeral = Everyday-Fresh"
"Ephemeral DH = a brand new secret every single session." Think of it like a one-time visitor badge instead of a permanent keycard — even if someone later steals today's badge design, it can't unlock yesterday's door.
Exam Tips & Tricks
DH exchanges a key, not a message
If a question implies DH sends an actual encrypted message, that's the wrong framing — DH only establishes a shared secret key, which is then used with a symmetric cipher.
Easy forward, hard backward
Modular exponentiation (computing yA = a^xA mod q) is easy. Reversing it — recovering xA from yA — is the hard discrete logarithm problem. That asymmetry is the entire basis of DH's security.
DH alone has no authentication
Plain, unauthenticated DH is vulnerable to man-in-the-middle. Remember: the fix is authentication (certificates/signatures), not a "stronger" DH — the math itself is fine.
Public vs private, know your letters
q and a are public and agreed on in advance. xA/xB are private and never transmitted. yA/yB are public and are what actually crosses the wire. KAB is never transmitted at all — it's derived independently on each side.
Cross public, raise to own private
The shared secret formula is easy to botch under exam pressure — remember each side takes the other party's public value and raises it to their own private exponent.
Darth needs two key pairs, not one
A common trick question: how many key pairs does the MITM attacker need? Answer: two — one shared secret with Alice, a separate one with Bob.
Quick Reference — Everything at a Glance
| Topic | Key Point |
|---|---|
| Inventors | Diffie & Hellman, 1976 — first public public-key scheme (Williamson/UK CESG secretly proposed it in 1970) |
| What DH is | A public-key distribution scheme — establishes a shared secret key, cannot exchange an arbitrary message |
| Underlying math | Exponentiation in a finite (Galois) field, modulo a prime or polynomial |
| Security basis | Difficulty of the discrete logarithm problem (similar in difficulty to factoring) |
| Primitive root | A number a whose powers mod q generate every nonzero element mod q |
| Global (public) parameters | Prime q and primitive root a — agreed on by all users in advance |
| Private key | xA < q, chosen secretly by each user, never transmitted |
| Public key formula | yA = axA mod q |
| Shared session key formula | KAB = axA·xB mod q = yBxA mod q = yAxB mod q |
| Worked example parameters | q = 353, a = 3, xA = 97, xB = 233 |
| Worked example public keys | yA = 40, yB = 248 |
| Worked example shared secret | KAB = 160 (computed identically by both Alice and Bob) |
| Attacker's task | Must solve a discrete logarithm to recover a private exponent from a public value — computationally hard |
| Ad-hoc key protocol | Random private/public DH keys generated fresh each communication session |
| Static key protocol | Known private/public DH key published in a directory, reused across sessions |
| Shared weakness | Both ad-hoc and static approaches are vulnerable to man-in-the-middle attack without authentication |
| MITM attacker (Darth) needs | Two separate private/public key pairs — one for the Alice-facing side, one for the Bob-facing side |
| MITM outcome | Darth shares a distinct key with each victim and can decrypt, read/modify, and re-encrypt all traffic between them |
| Fix for MITM | Authentication of the exchanged keys (e.g., digital certificates/signatures) |
| Ephemeral DH (DHE/ECDHE) | Fresh DH key pair generated per session; used in TLS to provide forward secrecy |
| Forward secrecy | Compromise of a long-term key does not expose past session keys |
| Real-world usage | TLS/HTTPS handshakes (DHE/ECDHE) and IPsec's IKE protocol, always paired with authentication |