Diffie-Hellman Key Exchange

Diffie and Hellman published ‘New Directions in Cryptography' in IEEE Transactions on Information Theory, November 1976. The paper proposed both public-key encryption (as a goal) and the key-exchange protocol (as a working example). Three British researchers at GCHQ — James Ellis, Clifford Cocks, and Malcolm Williamson — had discovered the same ideas between 1969 and 1974 but classification kept their work secret until 1997. The 1976 paper directly inspired Rivest, Shamir, and Adleman to find RSA the following year.

Both parties agree on a large prime p and a generator g. Alice picks a secret integer a and sends g^a mod p. Bob picks a secret integer b and sends g^b mod p. Each computes the shared value K = g^ab mod p — Alice raises Bob's value to her secret, Bob raises Alice's value to his. An eavesdropper sees p, g, A = g^a and B = g^b. Recovering an exponent a or b is a discrete logarithm problem (DLP). Computing only the shared value K is the computational Diffie–Hellman problem (CDH). A DLP solver gives a CDH solver: recover a, then compute B^a. The converse is not established for arbitrary groups. See Reduction & Proof for why the direction of an implication matters.

With p = 23, g = 5, A = 8 and B = 19, a discrete-log solver finds a = 6 because 5⁶ mod 23 = 8. It can then compute the shared value 19⁶ mod 23 = 2. These tiny parameters are for arithmetic only.

Source: Boneh and Shoup, A Graduate Course in Applied Cryptography, version 0.6 (January 2023), §10.4.2. Learning whether the value looks random is a further security question, distinct from merely computing it.

Resistance to recovering the shared value rests on the computational Diffie–Hellman assumption in the selected group; discrete-log hardness alone does not establish that assumption. Parameter size, subgroup choice and public-key validation all matter; a bit length alone does not establish security. The 2015 Logjam attack exploited servers using common 512-bit primes — the lesson was to use larger groups and to switch to elliptic curves where 256-bit keys suffice (X25519). DH is vulnerable to active man-in-the-middle attacks because the exchanged values are unauthenticated — in practice DH is always combined with authentication (for example signatures, certificates or a suitable pre-shared-key protocol). A human password requires a properly designed password-authenticated key exchange, not an improvised password check.