Diffie–Hellman key exchange

Diffie–Hellman key exchange
Name	Diffie–Hellman key exchange
Caption	A simplified diagram of the protocol
Designers	Whitfield Diffie, Martin Hellman
First published	1976
Derived to	RSA (cryptosystem), ElGamal encryption
Related to	Public-key cryptography, Key agreement protocol
Key sizes	Variable, commonly 2048–4096 bits for classical DH

Diffie–Hellman key exchange is a foundational method of securely exchanging cryptographic keys over a public channel. It was one of the first practical implementations of the concepts of public-key cryptography, though it is technically a key-agreement protocol. The security of the protocol relies on the computational difficulty of the discrete logarithm problem in finite cyclic groups.

Overview

The protocol enables two parties, traditionally named Alice and Bob, to jointly establish a shared secret key over an insecure communication link. This key can then be used for subsequent symmetric encryption of their communications. A seminal paper detailing the system was published by Whitfield Diffie and Martin Hellman in 1976, with conceptual contributions also attributed to Ralph Merkle. Its invention was a pivotal moment in the cryptography revolution of the 1970s, addressing the fundamental key distribution problem that had long plagued symmetric-key algorithms.

Description

The protocol operates within a large prime modulus *p* and a primitive root *g*. Both *p* and *g* are public numbers agreed upon by the parties, often standardized in groups like those defined by IETF RFCs. Each party generates a private key, a secret integer. Alice computes her public key as *g^a mod p* and sends it to Bob; Bob computes his as *g^b mod p* and sends it to Alice. Each then raises the other's public key to the power of their own private key, mathematically deriving the same shared secret: *(g^b)^a mod p = (g^a)^b mod p = g^ab mod p*. An eavesdropper like Eve sees only *p*, *g*, *g^a mod p*, and *g^b mod p*.

Security

The security rests on the assumption that computing the discrete logarithm—finding the exponent *a* from *g^a mod p*—is computationally infeasible for sufficiently large parameters. This is known as the Diffie–Hellman problem. However, the basic protocol does not provide authentication, making it vulnerable to a man-in-the-middle attack where an adversary like Mallory can impersonate both parties. For long-term security, the parameters must be large enough to resist attacks from powerful adversaries, including entities like the NSA, and must be chosen to avoid vulnerabilities like those exploited by the Logjam attack. The advent of quantum computing poses a future threat through Shor's algorithm.

Practical considerations

In modern practice, the classic finite field Diffie–Hellman is often supplemented or replaced by Elliptic-curve Diffie–Hellman (ECDH), which offers equivalent security with smaller key sizes. Parameters are frequently sourced from standardized groups, such as those in RFC 7919 or curves like Curve25519 designed by Daniel J. Bernstein. The protocol is a core component of many security suites, including TLS, SSH, and IPsec. Proper implementation requires robust random number generation for private keys and protection against side-channel attacks.

Other uses

The fundamental concept is used as a building block in various cryptographic protocols. It forms the basis for the ElGamal encryption system and is integral to the Digital Signature Algorithm. Variations are employed in Off-the-Record Messaging for forward secrecy and within Signal Protocol used by applications like WhatsApp and Signal. The mathematical structure also informs more advanced constructs in secure multi-party computation.

History

The concept was developed in the mid-1970s at Stanford University by Whitfield Diffie and Martin Hellman, with early ideas on public-key distribution contributed by Ralph Merkle. Their landmark paper, "New Directions in Cryptography," was presented at the National Computer Conference and later published in IEEE Transactions on Information Theory. Unbeknownst to them, similar concepts had been developed earlier within the GCHQ by British cryptographers Malcolm J. Williamson and, independently, by James H. Ellis and Clifford Cocks, but this work remained classified until 1997. The publication by Diffie and Hellman ignited widespread academic and commercial research into public-key cryptography, directly leading to the invention of the RSA algorithm by Ron Rivest, Adi Shamir, and Leonard Adleman.

Category:Cryptographic protocols Category:Key agreement protocols Category:1976 in computing