Diffie–Hellman Key Exchange

The problem it solves

AES is fast and strong, but both sides need the same secret key first. How can your browser and a server you have never contacted agree on a key when every packet between you can be read?

In 1976 Whitfield Diffie and Martin Hellman published the answer, the first public-key idea ever printed. (Malcolm Williamson at the British agency GCHQ had found it a few years earlier, but it stayed classified until 1997.)

The paint analogy

1. Alice and Bob agree in public on a common colour, say yellow.
2. Each secretly picks their own colour: Alice red, Bob blue.
3. Each mixes yellow with their secret colour and sends the mixture: Alice sends orange, Bob sends green.
4. Each adds their own secret colour to the mixture they received. Both get yellow + red + blue, the same brown.

Eve sees yellow, orange and green, but mixing paint is easy and unmixing it is practically impossible. In the maths, “mixing” is modular exponentiation and “unmixing” is the discrete logarithm.

The algorithm

Public: a large prime p and a generator g (a number whose powers mod p reach every value from 1 to p − 1).

Step	Alice	Bob
1. Pick a secret	a, with 1 < a < p − 1	b, with 1 < b < p − 1
2. Compute and send	A = gᵃ mod p	B = gᵇ mod p
3. Compute the shared secret	s = Bᵃ mod p	s = Aᵇ mod p

Both get the same number because

Bᵃ = (gᵇ)ᵃ = gᵃᵇ = (gᵃ)ᵇ = Aᵇ (mod p)

The shared secret s is then turned into an AES key.

Worked example (p = 23, g = 5)

	Alice	Bob
Secret	a = 6	b = 15
Public value	A = 5⁶ mod 23 = 15625 mod 23 = 8	B = 5¹⁵ mod 23 = 19
Receives	B = 19	A = 8
Shared secret	19⁶ mod 23 = 2	8¹⁵ mod 23 = 2

Eve sees p = 23, g = 5, A = 8 and B = 19, but never a, b or s.

Why Eve is stuck: the discrete logarithm

To compute s, Eve needs a or b. Finding a from A = gᵃ mod p is the discrete logarithm problem. For g = 5 and p = 23, the powers jump around unpredictably:

k	1	2	3	4	5	6	7	8	9	10	11
5ᵏ mod 23	5	2	10	4	20	8	17	16	11	9	22
k	12	13	14	15	16	17	18	19	20	21	22
5ᵏ mod 23	18	21	13	19	3	15	6	7	12	14	1

All 22 values from 1 to 22 appear exactly once, so 5 is a generator (primitive root) mod 23. Eve can find A = 8 at k = 6 by trying, because p is tiny. With a 2048-bit p there are about 10⁶¹⁶ values to try, and even the cleverest known methods are hopeless.

Man in the middle

Diffie–Hellman protects against someone who listens, not against someone who can change messages. Mallory catches A and B and sends her own M = gᵐ mod p to both sides. Alice unknowingly agrees on a key with Mallory, and so does Bob. Mallory decrypts everything, reads it, and re-encrypts it for the other side.

The fix is authentication. In HTTPS the server signs its Diffie–Hellman value with the private key in its certificate (RSA or ECDSA), and your browser checks the signature. A man in the middle cannot forge that signature.

Where it is used

• TLS 1.3 (HTTPS): every full handshake does an ephemeral elliptic-curve Diffie–Hellman (ECDHE, usually X25519).
• SSH, WireGuard, IPsec and the Signal protocol (WhatsApp, Signal) all start with Diffie–Hellman.
• Forward secrecy: the secrets a and b are thrown away after each session. Even if the server’s long-term key is stolen later, past sessions cannot be decrypted.

Diffie–Hellman vs RSA

	Diffie–Hellman	RSA
What it does	Agrees on a shared key	Encrypts and signs
Hard problem	Discrete logarithm	Factoring n = p × q
Keys	A fresh pair for every session	A long-term key pair
Forward secrecy	Yes (ephemeral)	No
Authentication	None on its own	Signatures

Code

import secrets

p, g = 23, 5                            # public (real p: 2048 bits)
a = secrets.randbelow(p - 3) + 2        # Alice's secret, 2 … p − 2
b = secrets.randbelow(p - 3) + 2        # Bob's secret

A = pow(g, a, p)                        # Alice sends A
B = pow(g, b, p)                        # Bob sends B
s_alice = pow(B, a, p)
s_bob = pow(A, b, p)
assert s_alice == s_bob                 # always equal

print(pow(5, 6, 23), pow(5, 15, 23))    # 8 19
print(pow(19, 6, 23), pow(8, 15, 23))   # 2 2

def discrete_log(g, A, p):              # Eve's brute force: O(p)
    v = 1
    for k in range(1, p):
        v = v * g % p
        if v == A:
            return k

print(discrete_log(5, 8, 23))           # 6

#include <cstdint>
#include <iostream>
using namespace std;

uint64_t power(uint64_t g, uint64_t e, uint64_t p) {     // square-and-multiply
    uint64_t r = 1;
    g %= p;
    for (; e; e >>= 1, g = g * g % p)
        if (e & 1) r = r * g % p;
    return r;
}

int main() {
    uint64_t p = 23, g = 5, a = 6, b = 15;
    uint64_t A = power(g, a, p), B = power(g, b, p);
    cout << "A = " << A << ", B = " << B << '\n';                                  // A = 8, B = 19
    cout << "Alice: " << power(B, a, p) << ", Bob: " << power(A, b, p) << '\n';    // Alice: 2, Bob: 2
}

Common mistakes

• Sending the secret. Alice sends A = gᵃ mod p, never a. The shared secret s is never sent either.
• Mixing up whose value to use. Alice raises Bob’s B to her own a: s = Bᵃ mod p.
• Thinking it encrypts messages. Diffie–Hellman only agrees on a key; AES then encrypts the data.
• Assuming it stops every attacker. Without signatures, a man in the middle breaks it completely.
• Picking a bad g. If g is not a generator, its powers cover only part of the numbers, which makes Eve’s search easier.