Skip to main content
Be Bitwise

Diffie-Hellman Key Exchange

Asymmetric Encryption · Networking & Cryptography track

7 min read

In this module

Agreeing on a Secret in Public

Picture Alice and Bob in a crowded room where everyone can hear their conversation. They need to agree on a secret number that only the two of them know, even though every word they say is overheard. Sounds impossible. Diffie-Hellman key exchange makes it work anyway.

Published in 1976 by Whitfield Diffie and Martin Hellman, this protocol was the first practical method for two parties to establish a shared secret over an insecure channel. Diffie-Hellman doesn't encrypt messages itself; it produces a shared key you then feed into a symmetric cipher.

The Protocol

Alice and Bob agree on two public parameters:

  • p: A large prime number
  • g: A generator (a number whose powers mod p produce many different values)

Both p and g are public - the eavesdropper knows them too.

Why do they get the same value?

text
Alice computes: B^a mod p = (g^b)^a mod p = g^(ab) mod p
Bob computes: A^b mod p = (g^a)^b mod p = g^(ab) mod p

Both arrive at g^(ab) mod p, but neither ever transmitted a or b.

Key Concept

Diffie-Hellman lets two parties compute a shared secret by exchanging public values. Each party combines their private secret with the other's public value. The eavesdropper sees both public values but cannot compute the shared secret because that would require solving the discrete logarithm problem.

A Numeric Example

text
Public parameters: p = 23, g = 5
Alice chooses: a = 6
Alice computes: A = 5^6 mod 23 = 15625 mod 23 = 8
Alice sends A = 8 to Bob
Bob chooses: b = 15
Bob computes: B = 5^15 mod 23 = 30517578125 mod 23 = 19
Bob sends B = 19 to Alice
Alice computes: s = 19^6 mod 23 = 47045881 mod 23 = 2
Bob computes: s = 8^15 mod 23 = 35184372088832 mod 23 = 2
Shared secret: 2

An eavesdropper knows p=23, g=5, A=8, B=19. To get back to a or b from those values, they'd have to solve the discrete logarithm problem, which is computationally infeasible for large primes.

Compute the shared secret for a = 4 and b = 3 by hand, then check it below. The second half plays Eve: she brute-forces a by multiplying by g until she reaches A, in groups of growing size. Before you run it, guess why Eve's answer for p = 101 doesn't match Alice's.

Try itCheck your hand calculation, then compare the real a with the one Eve finds in each group.
C (GCC 9.2.0)

For p = 101, 5 only reaches 50 of the 100 possible values before cycling round (5^50 mod 101 = 1), so 9 and 59 give the same A and Eve's smaller answer works just as well. That's one reason real groups are chosen with care. Otherwise the cost tracks the size of the group: a 2048-bit p puts brute force, and every cleverer algorithm we know, far out of reach.

The Discrete Logarithm Problem

Given g, p, and A = g^a mod p, finding a is called the discrete logarithm problem. For small numbers, brute force works fine. For 2048-bit primes, the computation is infeasible with anything we can build today.

It's the cousin of RSA's factoring problem. Both are "easy one way, hard the other way" relationships, and together they form the bedrock of public key cryptography.

That hardness depends on choosing p well. Real deployments use safe primes (p = 2q + 1 with q also prime), usually from vetted fixed groups such as those in RFC 7919, and at least 2048 bits. The 2015 Logjam attack showed why: a few widely shared 512-bit primes could be precomputed against once and then broken per connection in minutes, and the authors estimated a nation-state could do the same for a common 1024-bit prime.

The shared secret s also isn't used as a key directly. It's a number with structure, not a uniformly random string, so protocols feed it through a key derivation function first (a later module covers this).

The Man-in-the-Middle Problem

Basic Diffie-Hellman is vulnerable to a man-in-the-middle (MITM) attack. If Eve sits between Alice and Bob, she can:

  1. Intercept Alice's A, send her own A' to Bob
  2. Intercept Bob's B, send her own B' to Alice
  3. Establish one shared secret with Alice and a different one with Bob
  4. Decrypt, read, and re-encrypt all messages passing through

The fix is authentication. Alice and Bob must verify each other's identities, typically via digital signatures or certificates. TLS uses signed Diffie-Hellman parameters to shut MITM attacks down at the door.

Ephemeral Diffie-Hellman and Forward Secrecy

Ephemeral Diffie-Hellman (DHE or ECDHE) generates fresh random values for every session. If an attacker later compromises a long-term private key, they still can't decrypt past sessions, because every session used a unique ephemeral key that got thrown away.

That property is called perfect forward secrecy (PFS), and it's mandatory in TLS 1.3. Every HTTPS connection you make today almost certainly uses ephemeral Diffie-Hellman.

Elliptic Curve Diffie-Hellman (ECDH)

The same protocol can be performed using elliptic curve mathematics instead of modular exponentiation. ECDH operates on points on an elliptic curve, where scalar multiplication (computing kP) replaces modular exponentiation (computing g^k mod p).

Security comes from the elliptic curve discrete logarithm problem (ECDLP), which is even harder than the integer DLP at the same key size. ECDH gets equivalent security with much smaller parameters. A 256-bit ECDH key holds up about as well as a 3072-bit DH key.

The Protocol That Enabled the Internet

Diffie-Hellman cracked a problem that had haunted cryptography for centuries: how to establish a shared secret between two parties who'd never communicated before. Before 1976, every secure channel needed a pre-arranged key, which itself required a secure channel to deliver. A perfect chicken-and-egg loop. By making it possible to negotiate a shared secret over a public channel, Diffie-Hellman and its elliptic curve variant became the foundation of secure internet communication. Every TLS connection, every SSH session, every VPN tunnel uses a variant of this protocol. Understand Diffie-Hellman and you understand the mechanism that makes secure communication between strangers possible.