Diffie–Hellman

Eve listens to the exchange. Eve sees these values because they are public:

p

—

g

—

A

—

B

—

Can Eve recover Alice’s private exponent from the public values? She needs an exponent that solves

g^a ≡ A (mod p)

Solving this for the exponent is a discrete logarithm problem. For a small p she can simply try every exponent.

Calculation Alice’s public value Bob’s public value Alice’s shared secret Bob’s shared secret

Square-and-multiply reads the exponent in binary from its last bit. The base is squared at every step and reduced modulo p; where the bit is 1 the result is multiplied by the current base. The power itself is never written out.

Why do the shared secrets match?

Alice publishes A = g^a mod p and Bob publishes B = g^b mod p. Alice raises what she received to her own exponent, and Bob does the same:

K_A = B^a ≡ (g^b)^a = g^ab  ·  K_B = A^b ≡ (g^a)^b = g^ab  (mod p)

Both are g^ab mod p, by the laws of exponents in the multiplicative group modulo p. It is an identity, true for every choice of the four numbers, not a coincidence of this example.

What is a generator?

The nonzero residues modulo a prime p form a group under multiplication with p − 1 elements. A primitive root is a g whose powers reach all of them. To test one, factor p − 1 and check that g^(p−1)/r ≢ 1 for every prime r dividing it.

This page asks for a primitive root to keep the picture simple; a g that is not one would confine the exchange to a smaller subgroup. Real Diffie–Hellman is not required to use primitive roots, and usually does not: it works in a subgroup of large prime order, chosen with care. Being a primitive root does not make parameters secure.

What is the discrete logarithm problem?

Given p, g and a, computing A = g^a mod p is quick: a few dozen multiplications even for enormous numbers. Going back from A to a is the discrete logarithm problem. How hard it is depends on the group and on its size, which is why the parameters matter so much.

Why are small primes insecure?

With p = 23 there are only 21 possible private exponents, and with any prime on this page at most a million: an eavesdropper tries them all, as the experiment above shows. Size alone is not enough either. Real parameters are thousands of bits long and are also chosen so that the known shortcuts (for example, when p − 1 has only small prime factors) do not apply.

Why does key exchange need authentication?

Diffie–Hellman provides key agreement, but it does not authenticate the participants by itself. Someone who can intercept the messages can replace each public value with her own:

Alice ── A ──▶ Eve ── E ──▶ Bob Alice ◀── E ── Eve ◀── B ── Bob

Alice then shares one secret with Eve, and Bob shares another with Eve, while each believes the other end is their partner. Eve can read and alter everything in between. Real protocols prevent this by authenticating the exchange, for example with digital signatures or certificates.

What does a real protocol do with the shared secret?

• It authenticates the exchange, and validates the group parameters and the public values it receives.
• It does not use the shared number directly as a key: it passes it through a key derivation function to obtain symmetric keys.
• It then uses those keys inside a secure protocol, with authenticated encryption.

The small number computed on this page is not an encryption key and must not be used as one.

How is this different from RSA and from ECDH?

RSA is used for public-key encryption or for signatures, depending on the scheme. Diffie–Hellman does neither: it lets two parties agree on a shared secret, and encrypts or decrypts nothing by itself. Elliptic-curve Diffie–Hellman (ECDH) is the same idea in another group: instead of A = g^a mod p it computes A = aG for a point G of an elliptic curve. This page covers the classical version only.