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.

## 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 (_<span style="color:blue">10</span>_), which is not hidden.
1. Alice chooses a private number (***<span style="color:red">15</span>***), which she keeps secret. She adds this to the public number (_<span style="color:blue">10</span>_ + ***<span style="color:red">15</span>*** = 25) and sends 25 to Bob.
1. Bob does the same, choosing a secret private number (***<span style="color:red">30</span>***). He adds it to the public number (_<span style="color:blue">10</span>_ + ***<span style="color:red">30</span>*** = 40) and sends 40 to Alice.
1. 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 + ***<span style="color:red">15</span>*** = **55**.
    - Bob has Alice's 25. He adds his private number: 25 + ***<span style="color:red">30</span>*** = **55**.

Alice and Bob both start at the same number (_<span style="color:blue">10</span>_) and both do half of a sum, which means they both get the same result without seeing what the other person added (***<span style="color:red">15</span>*** and ***<span style="color:red">30</span>***). 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 _<span style="color:blue">10</span>_ + ***<span style="color:red">15</span>*** = 25, they don't know the result is **55** unless they also know Bob sent ***<span style="color:red">30</span>***.

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  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.
- 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, #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. . (Available online)
- Singh, Simon 1999. _The Code Book: the evolution of secrecy from Mary Queen of Scots to quantum cryptography_ New York: Doubleday
- An Overview of Public Key Cryptography  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 )
- 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