Diffie-Hellman key exchange

The Diffie-Hellman key exchange (sometimes called an Exponential key exchange) is a protocol used to secretly share information with keys.

Illustration of the Diffie–Hellman Key Exchange

Background

In 1976, Whitfield Diffie and Martin Hellman invented a way for people to encrypt data and send it over an open channel. The idea was based on a concept by Ralph Merkle.

Diffie and Hellman wanted to make Transport Layer Security (TLS), a secure way of computers communicating, more safe to perform. For example, while you can use a password to keep a file safe, if you need to tell the password to somebody there is a risk of the password being seen by third parties. Diffie-Hellman key agreement itself is an anonymous (non-authenticated) key-agreement protocol: people involved in the trade do not need to prove who they are, but both people need to use their secret keys to fully decrypt the data.

Basic Example

1. Alice and Bob agree on a public number (10), which is not hidden.
2. Alice chooses a private number (15), which she keeps secret. She adds this to the public number (10 + 15 = 25) and sends 25 to Bob.
3. Bob does the same, choosing a secret private number (30). He adds it to the public number (10 + 30 = 40) and sends 40 to Alice.
4. With their results swapped, Alice and Bob now add their private numbers to what they receive:
   • Alice has Bob's 40. She adds her private number: 40 + 15 = 55.
   • Bob has Alice's 25. He adds his private number: 25 + 30 = 55.

Alice and Bob both start at the same number (10) and both do half of a sum, which means they both get the same result without seeing what the other person added (15 and 30). This is useful in cryptography because Alice and Bob do not share their private numbers, which means a third party cannot spy on the result (55) unless they can find both private numbers; even if a third party knows Alice sent 10 + 15 = 25, they don't know the result is 55 unless they also know Bob sent 30.

Since only Alice and Bob know their private numbers, this is a good way of sending secure information if the numbers are very big and the calculations are difficult. Since computers can use very complicated math to encrypt things, this stops people from trying a brute force attack to guess the numbers until it works. One example of how big calculations are made this way is the original version of Diffie-Hellman, which used both multiplicative group of integers modulo n and primitive root modulo n.

Risks

While very useful, Diffie-Hellman is at risk of a man-in-the-middle attack. Alice and Bob do not need to prove who they are to swap their information, which means there is a risk that Charlie can look at the information while it is being swapped, and can even pretend to be Alice or Bob to try and figure out their keys. One way this is avoided is to use authentication, where people perform extra steps to prove who they are.

Related pages

• Public-key cryptography
• Diffie-Hellman problem
• MQV
• Station-to-Station protocol
• Internet Key Exchange protocol
• Key-agreement protocol
• Password-authenticated key agreement

References

• Non-secret encryption using a finite field Archived 2008-09-06 at the Wayback Machine 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 Archived 2008-08-07 at the Wayback Machine JH Ellis 1987 (28K PDF file) (HTML version Archived 2010-11-27 at the Wayback Machine)
• The first ten years of public-key cryptography Whitfield Diffie, Proceedings of the IEEE, vol. 76, #5, May 1988, pp: 560-577 (1.9MB PDF file)
• Menezes, Alfred; van Oorschot, Paul; Vanstone, Scot 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 Archived 2005-01-18 at the Wayback Machine Martin E. Hellman, IEEE Communications Magazine, May 2002, pp:42-49. (123kB PDF file)

Other websites

• 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 Archived 2004-08-16 at the Wayback Machine)
• Diffie-Hellman Key Exchange – A Non-Mathematician’s Explanation Archived 2010-03-24 at the Wayback Machine by Keith Palmgren
• Crypt::DH Perl module from CPAN
• Hands-on Diffie-Hellman demonstration
• C implementation using GNU Multiple Precision Arithmetic Library Archived 2008-06-27 at the Wayback Machine