Diffie–Hellman key exchange
Diffie–Hellman 'key exchange' is a mathematical method of securely generating a symmetric cryptographic key over a public channel and was one of the first protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography. Published in 1976 by Diffie and Hellman, this is the earliest publicly known work that proposed the idea of a private key and a corresponding public key.
Traditionally, secure encrypted communication between two parties required that they first exchange keys by some secure physical means, such as paper key lists transported by a trusted courier. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric-key cipher.
Diffie–Hellman is used to secure a variety of Internet services. However, research published in October 2015 suggests that the parameters in use for many DH Internet applications at that time are not strong enough to prevent compromise by very well-funded attackers, such as the security services of some countries.
The scheme was published by Whitfield Diffie and Martin Hellman in 1976, but in 1997 it was revealed that James H. Ellis, Clifford Cocks, and Malcolm J. Williamson of GCHQ, the British signals intelligence agency, had previously shown in 1969 how public-key cryptography could be achieved.
Although Diffie–Hellman key exchange itself is a non-authenticated key-agreement protocol, it provides the basis for a variety of authenticated protocols, and is used to provide forward secrecy in Transport Layer Security's ephemeral modes.
The method was followed shortly afterwards by RSA, an implementation of public-key cryptography using asymmetric algorithms.
Expired US patent 4200770 from 1977 describes the now public-domain algorithm. It credits Hellman, Diffie, and Merkle as inventors.
Name
In 2006, Hellman suggested the algorithm be called Diffie–Hellman–Merkle key exchange in recognition of Ralph Merkle's contribution to the invention of public-key cryptography, writing:Description
General overview
Diffie–Hellman key exchange establishes a shared secret between two parties that can be used for secret communication for exchanging data over a public network. An analogy illustrates the concept of public key exchange by using colors instead of very large numbers:The process begins by having the two parties, Alice and Bob, publicly agree on an arbitrary starting color that does not need to be kept secret. In this example, the color is yellow. Each person also selects a secret color that they keep to themselves – in this case, red and cyan. The crucial part of the process is that Alice and Bob each mix their own secret color together with their mutually shared color, resulting in orange-tan and light-blue mixtures respectively, and then publicly exchange the two mixed colors. Finally, each of them mixes the color they received from the partner with their own private color. The result is a final color mixture that is identical to their partner's final color mixture.
If a third party listened to the exchange, they would only know the common color and the first mixed colors, but it would be very hard for them to find out the final secret color. Bringing the analogy back to a real-life exchange using large numbers rather than colors, this determination is computationally expensive; it is impossible to compute in a practical amount of time even for modern supercomputers.
Cryptographic explanation
The simplest and the original implementation, later formalized as Finite Field Diffie–Hellman in RFC 7919, of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. To guard against potential vulnerabilities, it is recommended to use prime numbers of at least 2048 bits in length. This increases the difficulty for an adversary attempting to compute the discrete logarithm and compromise the shared secret. These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to. Here is an example of the protocol, with non-secret values in, and secret values in '.- Alice and Bob publicly agree to use a modulus ' = and base ' = .
- Alice chooses a secret integer
More specifically,
Only a and b are kept secret. All the other values – p, g, ga mod p, and gb mod p – are sent in the clear. The strength of the scheme comes from the fact that gab mod p = gba mod p take extremely long times to compute by any known algorithm just from the knowledge of p, g, ga mod p, and gb mod p. Such a function that is easy to compute but hard to invert is called a one-way function. 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 600 digits, then even the fastest modern computers using the fastest known algorithm cannot find a given only g, p and ga mod p. Such a problem 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.
Secrecy chart
The chart below depicts who knows what, again with non-secret values in, and secret values in '. Here Eve is an eavesdropper – she watches what is sent between Alice and Bob, but she does not alter the contents of their communications.- ', public base, known to Alice, Bob, and Eve. ' =
- ', public modulus, known to Alice, Bob, and Eve. ' =
Now is the shared secret key and it is known to both Alice and Bob, but not to Eve. Note that it is not helpful for Eve to compute ', which equals '+''''' mod. Note: It should be difficult for Alice to solve for Bob's private key or for Bob to solve for Alice's private key. If it is not difficult for Alice to solve for Bob's private key, then an eavesdropper, Eve, may simply substitute her own private / public key pair, plug Bob's public key into her private key, produce a fake shared secret key, and solve for Bob's private key. Eve may attempt to choose a public / private key pair that will make it easy for her to solve for Bob's private key. Generalization to finite cyclic groupsHere is a more general description of the protocol:
For example, the elliptic curve Diffie–Hellman protocol is a variant that represents an element of G as a point on an elliptic curve instead of as an integer modulo n. Variants using hyperelliptic curves have also been proposed. The supersingular isogeny key exchange is a Diffie–Hellman variant that was designed to be secure against quantum computers, but it was broken in July 2022. Ephemeral and/or static keysThe used keys can either be ephemeral or static key, but could even be mixed, so called semi-static DH. These variants have different properties and hence different use cases. An overview over many variants and some also discussions can for example be found in NIST SP 800-56A. A basic list:
|