Diffie-Hellman key exchange
The Diffie-Hellman key exchange is a way for people to secretly share information. When two people want to use cryptography, they often only have an insecure channel to exchange information. Martin Hellman, Whitfield Diffie and Ralph Merkle developed a protocol that allows this information exchange over an insecure channel. The resulting protocol has become known as Diffie-Hellman key exchange. Sometimes it is called Diffie-Hellman key agreement, Diffie-Hellman key establishment, Diffie-Hellman key negotiation or Exponential key exchange. Using this protocol, both parties agree on a secret key. They use this key to encrypt their communication using a symmetric-key cipher.
The scheme was first published by Whitfield Diffie and Martin Hellman in 1976. Diffie-Hellman key agreement itself is an anonymous (non-authenticated) key-agreement protocol, it provides the basis for a variety of authenticated protocols, and is used to provide perfect forward secrecy in Transport Layer Security's short-lived modes.
In the original description papers, the Diffie-Hellman exchange by itself does not provide authentication of the communicating parties and is thus susceptible to a man-in-the-middle attack. An attacking person in the middle may establish two different Diffie-Hellman key exchanges, with the two members of the party "A" and "B", appearing as "A" to "B", and vice versa, allowing the attacker to decrypt (and read or store) then re-encrypt the messages passed between them. A method to authenticate the communicating parties to each other is generally needed to prevent this type of attack.
Many cryptographic authentication solutions include a Diffie-Hellman exchange. When two parties "A" and "B" have a public key infrastructure, they may digitally sign the agreed key "G", or GA and GB, as in MQV, STS and the IKE component of the IPsec protocol suite for securing Internet Protocol communications. When "A" and "B" share a password, they may use a password-authenticated key agreement form of Diffie-Hellman.
The simplest and the original implementation of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. Here is an example of the protocol, with non-secret values in blue, and secret values in red.
- Alice and Bob agree to use a prime number p = 23 and base g = 5 (which is a primitive root modulo 23).
- Alice chooses a secret integer a = 6, then sends Bob A = ga mod p
- A = 56 mod 23 = 8
- Bob chooses a secret integer b = 15, then sends Alice B = gb mod p
- B = 515 mod 23 = 19
- Alice computes s = Ba mod p
- s = 196 mod 23 = 2
- Bob computes s = Ab mod p
- s = 815 mod 23 = 2
- Alice and Bob now share a secret (the number 2).
Both Alice and Bob have arrived at the same value, because (ga)b (for Bob, 815 mod 23 = (ga mod p)b mod p = (ga)b mod p) and (gb)a are equal mod p. Note that only a, b, and (gab mod p = gba mod p) are kept secret. All the other values – p, g, ga mod p, and gb mod p – are sent in the clear. Once Alice and Bob compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel.
Of course, much larger values of a, b, and p would be needed to make this example secure, since there are only 23 possible results of n mod 23. However, if p is a prime of at least 300 digits, and a and b are at least 100 digits long, then even the fastest modern computers cannot find a given only g, p and ga mod p. The problem such is called the discrete logarithm problem. The computation of ga mod p is known as modular exponentiation and can be done efficiently even for large numbers. Note that g need not be large at all, and in practice is usually a small integer (like 2, 3, ...).