Computational cryptography › Public-key encryption and key exchange › Classical number theory › Finite-field discrete log
KEM / KEY EXCHANGEPrimitive

Finite-field DH key exchange

In plain words

The original 1976 way for two strangers to agree on a secret over a public line, using ordinary big numbers.

The idea: The paint analogy: Alice and Bob agree in public on a common color. Each mixes in a secret color and sends the mixture. Each then adds their own secret color to what they received, and both end up with the same paint: common + Alice's + Bob's. An eavesdropper has seen both half-mixtures but can't unmix paint to get the secret colors. With numbers, "mixing" is raising to a secret power modulo a big prime.

Why it matters: Still found in some VPNs, but mostly replaced by the elliptic-curve version.

Agreeing on a secret in public
AliceBobeveryone seescommongsecret asecret bmixgᵃmixgᵇsame secretgᵃᵇsame secretgᵃᵇBob's mix + aAlice's mix + bcan't unmixthe paint
Alice and Bob start from a public color, each mixes in a secret one, and they swap the mixtures in the open. Each then adds their own secret color to what they received, and both end up with the same paint. An eavesdropper has seen both mixtures but can't unmix them. In the real protocol, mixing is raising g to a secret power, modulo a big prime.

The details

On the map: DHE: IPsec/IKE, older TLS

The original 1976 Diffie-Hellman key exchange[1]: Alice sends g^a, Bob sends g^b, and both compute g^(ab), which an eavesdropper can't.

Still used in IPsec/IKE VPNs and older TLS configurations (DHE). TLS 1.3 keeps standardized finite-field groups (RFC 7919)[2], but almost everyone uses X25519 instead[3]: much smaller keys for the same security. Shor's algorithm breaks it.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Nothing on the map depends on it: it is an end point, something people use directly.

References

  1. Whitfield Diffie and Martin E. Hellman. New Directions in Cryptography. Democratizing Cryptography, 1976. doi:10.1145/3549993.3550007
  2. D. Gillmor. Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS). RFC 7919, 2016. rfc-editor.org/rfc/rfc7919
  3. A. Langley, M. Hamburg and S. Turner. Elliptic Curves for Security. RFC 7748, 2016. rfc-editor.org/rfc/rfc7748