Diffie-Hellman: The Key Exchange That Made RSA Possible

#TL;DR

In November 1976, Whitfield Diffie and Martin Hellman published “New Directions in Cryptography” — the paper that proved two strangers could agree on a shared secret over a public channel without ever meeting, and without an attacker who sees every message being able to learn the secret. A year later, Rivest, Shamir, and Adleman would publish RSA — the first practical public-key encryption system. But it was Diffie and Hellman who showed the idea was possible, and their key-exchange protocol is still the primitive that TLS, SSH, and Signal use to set up session keys. Fifty years later, the algorithm in the paper has been upgraded to run on elliptic curves, but the trick is the same.

#The Problem: Two Strangers, One Secret

Suppose you and I want to exchange encrypted messages. We need a shared key — some sequence of bytes we both know and nobody else does. Symmetric encryption, which is the only kind that existed before 1976, assumes this key already exists.

How did we get it?

Before Diffie-Hellman, there were two answers:

We meet in person and exchange the key on a piece of paper, a USB stick, or a punch card.
We trust a courier — typically a government — to deliver the key on our behalf.

Neither scales. If a bank wants to exchange encrypted messages with a million customers, it cannot mail a million envelopes. If two ARPANET researchers need to communicate privately, they cannot fly to each other’s institutions first. The key distribution problem was the fundamental obstacle to cryptography at network scale, and for most of the 20th century, cryptographers considered it a precondition, not a thing you could solve with math.

Diffie and Hellman solved it with math.

#The Shared-Paint Analogy

Before the equations, a standard explanatory trick: imagine you and I each have an identical can of paint. We want to agree on a shared color, using only a public channel — any paint shipments we send go through a warehouse where an eavesdropper can peek at them.

Here’s what we do:

We publicly agree on a starting color — let’s say yellow. Everyone in the world knows we started with yellow.
I privately pick a color — blue. I mix yellow + blue, producing green. I ship the green can to you.
You privately pick a color — red. You mix yellow + red, producing orange. You ship the orange can to me.
I receive your orange can. I mix in my private blue, producing (orange + blue) = brown.
You receive my green can. You mix in your private red, producing (green + red) = brown.

We both have brown. The eavesdropper in the warehouse saw yellow, green, and orange — but the combination that makes brown requires at least one of the private colors, which they never saw.

The trick relies on two properties of paint-mixing:

Mixing is easy — given two colors, you can mix them in seconds.
Un-mixing is hard — given a mixed color, figuring out the original components is essentially impossible.

That’s a one-way function. Diffie and Hellman’s insight was that modular exponentiation has the same property, and you can build a real protocol on it.

#The Math

Diffie-Hellman replaces “paint” with numbers modulo a large prime.

Public parameters (everyone knows these):
  p = a large prime number
  g = a generator of the multiplicative group mod p  (in practice, g=2 or g=5)

Alice's secret:  a (random number, kept private)
Bob's secret:    b (random number, kept private)

Alice sends:     A = g^a mod p
Bob sends:       B = g^b mod p

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

They both have s. An attacker has p, g, A, B — but not a or b.

The shared secret is g^(ab) mod p. Both Alice and Bob compute it from the other party’s public value raised to their own private exponent. They arrive at the same number because modular exponentiation is commutative in the exponent: (g^a)^b = (g^b)^a = g^(ab).

p = 23     # toy prime — real Diffie-Hellman uses 2048+ bit primes
g = 5

# Alice picks a secret
a = 6
A = pow(g, a, p)  # 5^6 mod 23 = 8

# Bob picks a secret
b = 15
B = pow(g, b, p)  # 5^15 mod 23 = 19

# Public channel: Alice → Bob sends A=8; Bob → Alice sends B=19

# Alice computes the shared secret
s_alice = pow(B, a, p)  # 19^6 mod 23 = 2

# Bob computes the shared secret
s_bob = pow(A, b, p)    # 8^15 mod 23 = 2

assert s_alice == s_bob == 2

The eavesdropper sees p=23, g=5, A=8, B=19. To find the shared secret, they’d need either Alice’s private a or Bob’s private b. Recovering a from A = g^a mod p is called the discrete logarithm problem — and it’s the hardness that makes the scheme secure.

#Why Discrete Log Is Hard

Computing g^a mod p given a, g, and p is fast — a few milliseconds even for 2048-bit numbers, because exponentiation-by-squaring lets you do it in roughly log(a) multiplications.

Going the other direction — given g^a mod p, recovering a — requires solving the discrete logarithm problem, and no known algorithm does it efficiently on a classical computer.

The best algorithms for generic prime fields are in the general number field sieve family, and their running time grows sub-exponentially with the size of p. For a 2048-bit prime, the computational cost is comparable to factoring a 2048-bit RSA key — well beyond the capability of any known system.

Discrete log and integer factoring aren’t the same problem, but they’re both in the same cryptographic family: problems that are believed hard classically but that fall to quantum computers running Shor’s algorithm. That shared weakness is why the post-quantum transition affects both RSA and classical Diffie-Hellman at the same time.

#Diffie-Hellman Is Not RSA

A subtle point that trips people up: Diffie-Hellman doesn’t encrypt anything. It’s a key agreement protocol — at the end of it, Alice and Bob share a secret. What they do with that secret is a separate question.

In practice, the shared secret gets fed into a key derivation function (like HKDF) to produce one or more symmetric keys, and those keys are used for something like AES-GCM to encrypt the actual conversation.

RSA, by contrast, can encrypt (you can encrypt data with someone’s public key) and also sign (you can sign data with your private key). RSA does more. Diffie-Hellman is more narrow: it’s optimized for the one job of establishing a shared symmetric key.

This is actually why Diffie-Hellman has aged better in practice than RSA. Modern protocols almost never RSA-encrypt conversation data directly — RSA is too slow for bulk encryption, and RSA’s use for key transport has been replaced by Diffie-Hellman-based key agreement. Modern TLS does an ECDHE (elliptic-curve Diffie-Hellman, ephemeral) handshake to derive session keys, and only uses RSA for the server’s certificate signature (which proves the server’s identity).

#The “Ephemeral” Trick: Forward Secrecy

If Alice and Bob always use the same long-lived DH private keys, an attacker who later steals one of those keys can decrypt every past conversation they recorded. This is called a forward-secrecy failure.

The fix is ephemeral Diffie-Hellman (DHE or ECDHE). Alice and Bob generate fresh, random a and b for every session, discard them immediately after deriving the session key, and never write them to disk. If an attacker later steals their long-term identity keys, they still can’t decrypt old sessions — the ephemeral a and b are gone forever.

Modern TLS insists on ephemeral key agreement by default. The “E” in ECDHE stands for “ephemeral” and is not optional in TLS 1.3.

#Elliptic Curve Diffie-Hellman

Classical Diffie-Hellman operates in the multiplicative group of integers mod a prime. Elliptic Curve Diffie-Hellman (ECDH) does the exact same protocol over the group of points on an elliptic curve.

The trick is that on an elliptic curve, the discrete logarithm problem appears to be harder per bit. A 256-bit ECDH key offers security roughly comparable to a 3072-bit classical DH key. This means ECDH keys and messages are much smaller, which matters enormously on mobile devices, embedded systems, and any protocol where every byte counts.

The specific curve matters: Curve25519 (designed by Daniel J. Bernstein) is the de facto default for most modern protocols, because it’s fast, has simple implementation rules, and avoids several classes of subtle bugs that earlier curves allowed. Signal, WireGuard, modern SSH, TLS 1.3, and Noise-based protocols all use Curve25519 for key agreement.

Elliptic-curve math is a whole topic and the RSA post gestures at it. The important thing here is that the protocol of Diffie-Hellman is identical — same handshake, same math structure, same security argument — just over a different group.

#The One Thing Diffie-Hellman Can’t Do

Diffie-Hellman establishes a shared secret between two parties. What it can’t do is tell you who you established that secret with.

If Mallory sits in the middle of the connection, she can run the Diffie-Hellman protocol twice — once with Alice, once with Bob — and end up sharing a different key with each of them. Alice thinks she’s talking to Bob. Bob thinks he’s talking to Alice. Mallory relays every message between them, decrypting and re-encrypting as she goes, reading everything.

This is the man-in-the-middle attack, and it’s why raw Diffie-Hellman is never used in practice. You need authentication — some way to prove that the public value you received actually came from the party you meant to talk to.

This is what digital signatures solve. In TLS, the server presents a certificate signed by a trusted CA, the client verifies the signature, and then they run Diffie-Hellman with confidence that the public values are authentic. The two primitives complement each other: Diffie-Hellman establishes the key; signatures authenticate the parties.

#What Diffie-Hellman Actually Proved

The RSA post calls Diffie-Hellman’s paper “the concept was elegant and provably possible.” That undersells what happened in November 1976. The paper:

Introduced the idea of public-key cryptography. Before this paper, there was no academic concept of “encryption with different keys for locking and unlocking.” Diffie and Hellman named the thing and proved it was mathematically coherent.
Gave a working protocol for one of the two problems (key agreement). They couldn’t yet do encryption or signatures in a single primitive — that was RSA’s contribution — but they showed the key-distribution problem was solvable.
Made cryptography a public-academic subject. Before 1976, serious cryptography research was essentially all classified. The Diffie-Hellman paper was the moment the field crossed from government to open science.

Rivest, Shamir, and Adleman would finish the job a year later with a full public-key encryption system. But they were building on Diffie and Hellman’s result, and modern protocols have circled back to it: most of the public internet’s session keys today come out of an elliptic-curve Diffie-Hellman exchange, not an RSA encryption. The primitive has outlasted its younger, more famous cousin. Not bad for a protocol that just agrees on a number.