Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 40 ยท Public-Key Cryptography

Diffie-Hellman Key Exchange

Learn how two people agree on a shared secret over an open channel, try it with a small prime, break it by brute force, mount a man-in-the-middle, and run X25519.

In 1976 Whitfield Diffie and Martin Hellman published a surprising idea: two people who have never met can agree on a secret number by talking in public, even though everyone is listening. The Diffie-Hellman key exchange (DH) was the first public-key algorithm, and a descendant of it, run on elliptic curves, sits in almost every HTTPS connection you make today.

The trick uses the one-way function from the previous lesson: modular exponentiation is fast, while the discrete logarithm is hard to reverse. This lesson walks through the protocol with tiny numbers, shows how fast it breaks when the numbers stay tiny, demonstrates the man-in-the-middle attack that plain DH cannot stop, and ends with the real-world elliptic-curve version, X25519.

The protocol

Alice and Bob publicly agree on two parameters: a large prime p and a number g (the generator). These are not secret.

  1. Alice picks a secret number a and sends A = g^a mod p.
  2. Bob picks a secret number b and sends B = g^b mod p.
  3. Alice computes B^a mod p. Bob computes A^b mod p.

Both results equal g^(ab) mod p, because (g^b)^a = g^(ba) = (g^a)^b. That number is the shared secret. An eavesdropper sees p, g, A and B, but computing g^(ab) from these appears to require solving a discrete logarithm. (This link, called the Diffie-Hellman problem, is believed to be as hard as the discrete logarithm for the groups used in practice.)

sequenceDiagram
    participant A as Alice
    participant E as Eavesdropper
    participant B as Bob
    A->>B: public p, g
    Note over A: secret a
    Note over B: secret b
    A->>B: A = g^a mod p
    B->>A: B = g^b mod p
    Note over E: sees p, g, A, B only
    Note over A: s = B^a mod p
    Note over B: s = A^b mod p

Both sides compute the same s = g^(ab) mod p; the eavesdropper sees only the public values.

Here is the classic small example with p = 23 and g = 5, which you can follow with a calculator.

Python Diffie-Hellman with p = 23

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The shared number is then fed to a key derivation function such as HKDF, never used directly as a cipher key, because it has algebraic structure and is not uniformly random bytes.

Why the numbers must be large

With p = 23 there are only 22 possible exponents, so an eavesdropper tries them all and finds a instantly. The same brute force works on any prime that is small enough to enumerate. The next example plays the attacker: it recovers Alice's secret from her public value and counts the guesses needed. The cost grows linearly with p, while the legitimate computation grows with the number of digits of p.

Python Breaking small Diffie-Hellman by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In real deployments the prime is at least 2048 bits, and it must be a carefully chosen safe prime (p = 2q + 1 with q also prime) or come from a standardized group such as those in RFC 7919. A prime for which p - 1 has only small factors lets attackers solve the discrete logarithm in pieces, no matter how large p is. Never invent your own parameters.

Man-in-the-middle: DH does not authenticate

Plain Diffie-Hellman protects against a passive eavesdropper. It does not tell Alice who she is talking to. An active attacker, Mallory, who can intercept and replace messages, runs two separate exchanges, one with each side, and relays traffic between them, reading and modifying everything.

sequenceDiagram
    participant A as Alice
    participant M as Mallory
    participant B as Bob
    A->>M: A = g^a
    M->>B: M2 = g^m2
    B->>M: B = g^b
    M->>A: M1 = g^m1
    Note over A,M: key K1 = g^(a*m1)
    Note over M,B: key K2 = g^(b*m2)
    A->>M: message encrypted with K1
    M->>B: re-encrypted with K2

Alice shares a key with Mallory and Bob shares another with Mallory; neither shares one with the other.

Python A man-in-the-middle against unauthenticated DH

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fix is to authenticate the exchanged values. TLS has the server sign its DH value with the private key behind its certificate, so Mallory cannot substitute her own. Signed ephemeral DH is the standard pattern, and it is why digital signatures appear next to key exchange in every protocol.

Ephemeral keys and forward secrecy

If Alice and Bob generate fresh secrets a and b for every session and delete them afterwards, the key is called ephemeral (the variants are written DHE or ECDHE). Even if an attacker later steals the server's long-term signing key, the old session keys cannot be recomputed from recorded traffic, since a and b no longer exist anywhere. This property is forward secrecy, and TLS 1.3 requires it. The TLS lesson shows where it fits.

Elliptic-curve Diffie-Hellman and X25519

The same protocol works in any group where the discrete logarithm is hard. On an elliptic curve (see Elliptic Curve Cryptography), "raise to the power" becomes "multiply a point by a number", and the keys are much smaller: 32 bytes for a Curve25519 key against roughly 256 bytes for a 2048-bit DH value, at comparable or better security.

X25519, specified in RFC 7748, is the most widely used instance. A private key is any 32 random bytes (clamped internally), a public key is 32 bytes, and the whole function is a single call: x25519(scalar, u_coordinate). The version below is a direct transcription of the algorithm (the Montgomery ladder) in pure Python. It checks itself against the test vectors published in the RFC, which is the right way to trust code you wrote from a specification. It is for learning only: it is not constant-time, so use a vetted library in real programs.

Python X25519 key exchange, verified against RFC 7748

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In practice, you call a library function (for example X25519PrivateKey in the cryptography package), pass the result through HKDF, and never write the ladder yourself.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In Diffie-Hellman, what does Alice send to Bob?

    She sends the public value A = g^a mod p. The secret a never leaves her machine, and recovering it from A is the discrete logarithm problem.
  2. 2. Why is a small prime like p = 10007 useless for real key exchange?

    Exhaustive search over the exponents costs about p steps, which is trivial for small p. Real groups have 2048-bit primes or use elliptic curves.
  3. 3. What does a man-in-the-middle do to plain Diffie-Hellman?

    Unauthenticated DH cannot tell who sent a public value, so an active attacker substitutes her own and relays everything.
  4. 4. How do protocols such as TLS defend against that attack?

    The server signs its DH value with its certified private key, so an attacker cannot replace it without being detected.
  5. 5. What does an ephemeral DH key give you?

    Fresh secrets are deleted after the session, so recorded traffic cannot be decrypted later. Authentication is a separate requirement.

Summary

  • Diffie-Hellman lets two parties derive the same secret g^(ab) mod p from public values g^a and g^b; the eavesdropper would need a discrete logarithm.
  • Parameters must be large, standardized safe primes (2048+ bits) or an elliptic curve; toy sizes fall to brute force immediately.
  • Plain DH is not authenticated: an active man-in-the-middle can run two exchanges. Protocols sign or otherwise authenticate the values.
  • Fresh (ephemeral) keys per session give forward secrecy.
  • X25519 is the modern elliptic-curve variant with 32-byte keys; always pass the raw shared secret through a KDF.

Next: RSA from Scratch, the first algorithm that does public-key encryption and signatures with one key pair.