Diffie-Hellman key exchange

Diffie-Hellman key exchange is a cryptographic protocol that allows two communicators (conventionally named Alice and Bob) to agree on a secret key over an insecure communication channel. Once the shared secret key has been established, Alice and Bob can use it to conventionally encrypt their secret communication. It is named for its inventors, Whitfield Diffie and Martin Hellman.

The protocol is as follows:

1. Alice and Bob agree on a group G and an element g in G. (This is usually done long before the rest of the protocol; g is assumed to be known by all attackers.) We will write the group G multiplicatively.
2. Alice picks a random natural number a and sends g^a to Bob.
3. Bob picks a random number b and sends g^b to Alice.
4. Alice computes (g^b)^a.
5. Bob computes (g^a)^b.

Both Alice and Bob are now in possession of the group element g^ab (see exponentiation) which can serve as the shared secret key.

The protocol is considered secure against eavesdroppers if G and g are chosen properly: the eavesdropper ("Eve") has difficulty to compute the element g^ab, because she would have to solve the Diffie-Hellman problem related to discrete logarithms in order to deduce a from g^a and b from g^b.

If Alice and Bob use random number generators whose outputs are not completely random but can be predicted to some extent, then Eve's task is much easier.

The protocol is vulnerable to the man in the middle attack in which the attacker is able to read and modify all messages between Alice and Bob. Workarounds exist, such as digitally signing each message, which is possible if Alice and Bob have a public key infrastructure.

Diffie-Hellman key exchange was invented in 1975 or 1976 during a collaboration between Whitfield Diffie, Martin Hellman and Ralph Merkle and was the first practical method for establishing a shared secret over an unprotected communications channel. It had been discovered by Malcolm Williamson of GCHQ in the UK some years previously, but GCHQ chose not make it public until 1997, by which time it had no influence on research.

The method was followed shortly afterwards by RSA, the first publicly announced implementation of public key cryptography using asymmetric algorithms.

Diffie-Hellman key exchange is used, in conjunction with several alternative authentication methods, in the IKE component of the IPSec protocol suite.