Engineering / Mathematics — Discrete Logarithms and Factoring
The Diffie-Hellman Key Establishment Protocol
Diffie-Hellman key agreement, the assumptions it rests on, and the authentication gap that makes it vulnerable alone.
Executive summary
Diffie-Hellman lets two parties agree a shared secret over a public channel, using only exponentiation in a cyclic group. It was the first practical public-key construction.
It provides no authentication whatever, and unauthenticated Diffie-Hellman falls to a straightforward machine-in-the-middle attack.
Learning objectives
- State the protocol and its correctness.
- Distinguish the computational and decisional assumptions.
- Explain the authentication requirement.
01The protocol
Agree parameters
A group G of prime order q with generator γ, published and shared.
Each party chooses a secret
Alice draws a, Bob draws b, each uniform in {1, ..., q−1}.
Exchange public values
Alice sends γ^a, Bob sends γ^b, over the open channel.
Compute the shared secret
Alice computes (γ^b)^a, Bob computes (γ^a)^b. Both equal γ^{ab}.
Derive a key
Pass γ^{ab} through a key derivation function; never use the raw group element as a key.
(γ^a)^b = γ^{ab} = (γ^b)^a02The assumptions
| Assumption | Statement | Strength |
|---|---|---|
| Discrete logarithm | Given γ^a, find a | Weakest — implied by the others |
| Computational Diffie-Hellman | Given γ^a and γ^b, compute γ^{ab} | Stronger |
| Decisional Diffie-Hellman | Distinguish γ^{ab} from a random element | Strongest |
Breaking the discrete logarithm breaks everything, so it is the weakest assumption. Whether the converse holds — whether computing γ^{ab} requires finding a — is not known in general.
03The authentication gap
The protocol must therefore be combined with authentication of the exchanged values.
- Signatures. Each party signs their public value with a long-term key whose authenticity is established elsewhere, as in the signed key exchange used by TLS.
- Certificates. A trusted authority binds identities to long-term keys, providing the basis for verifying those signatures.
- Pre-shared secrets. A password or shared key authenticates the exchange, as in password-authenticated key exchange protocols.
Ephemeral Diffie-Hellman — generating fresh secrets for every session — provides forward secrecy: compromising a long-term signing key later does not expose past session keys, because those depended on ephemeral values that were discarded. This is why ephemeral modes are preferred in modern protocol design.
04Frequently asked questions
Why derive a key rather than use the shared element directly?
Because the element is uniformly distributed over the group, not over bit strings, and may retain algebraic structure. A key derivation function produces uniform key material of the required length and separates keys for different purposes.
Is finite-field Diffie-Hellman still used?
Less than before. Elliptic curve variants give equivalent security with far smaller parameters and are now the default in most protocols. Finite-field versions persist in legacy deployments and require substantially larger groups.
What is forward secrecy?
The property that compromising long-term keys does not expose past sessions. It requires ephemeral per-session secrets that are securely discarded afterwards, which static Diffie-Hellman does not provide.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 275-282.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.