Diffie-Hellman key exchange
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.
Cryptographic explanation[change | change source]
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, ...).
References[change | change source]
- Non-Secret Encryption Using a Finite Field MJ Williamson, January 21, 1974.
- Thoughts on Cheaper Non-Secret Encryption MJ Williamson, August 10, 1976.
- New Directions in Cryptography W. Diffie and M. E. Hellman, IEEE Transactions on Information Theory, vol. IT-22, Nov. 1976, pp: 644-654.
- Cryptographic apparatus and method Martin E. Hellman, Bailey W. Diffie, and Ralph C. Merkle, U.S. Patent #4,200,770, 29 April 1980
- The History of Non-Secret Encryption JH Ellis 1987 (28K PDF file) (HTML version)
- The First Ten Years of Public-Key Cryptography Whitfield Diffie, Proceedings of the IEEE, vol. 76, no. 5, May 1988, pp: 560-577 (1.9MB PDF file)
- Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997). Handbook of Applied Cryptography Boca Raton, Florida: CRC Press. ISBN 0-8493-8523-7. (Available online)
- Singh, Simon (1999) The Code Book: the evolution of secrecy from Mary Queen of Scots to quantum cryptography New York: Doubleday ISBN 0-385-49531-5
- An Overview of Public Key Cryptography Martin E. Hellman, IEEE Communications Magazine, May 2002, pp:42-49. (123kB PDF file)
Other pages[change | change source]
- Public-key cryptography
- Diffie-Hellman problem
- Station-to-Station protocol
- Internet Key Exchange protocol
- Key-agreement protocol
- Password-authenticated key agreement
Other websites[change | change source]
- Oral history interview with Martin Hellman, Charles Babbage Institute, University of Minnesota. Leading cryptography scholar Martin Hellman discusses the circumstances and fundamental insights of his invention of public key cryptography with collaborators Whitfield Diffie and Ralph Merkle at Stanford University in the mid-1970s.
- RFC 2631 - Diffie-Hellman Key Agreement Method E. Rescorla June 1999.
- Summary of ANSI X9.42: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography (64K PDF file) (Description of ANSI 9 Standards)
- Diffie-Hellman Key Exchange – A Non-Mathematician’s Explanation by Keith Palmgren
- Crypt::DH Perl module from CPAN
- Hands-on Diffie-Hellman demonstration
- C implementation using GNU Multiple Precision Arithmetic Library