The Diffie-Hellman protocol is a scheme for exchanging information over a public channel. If two people (usually referred to in the cryptographic literature as Alice and Bob) wish to communicate securely, they need a way to exchange some information that will be known only to them. In practice, Alice and Bob are communicating remotely (e.g. over the internet) and have no prearranged way to exchange information.
The main idea is that each of them has some secret information that is known only to them, which they combine into a suitable key, or password, which they can then use to set up a secure communication platform. The Diffie-Hellman protocol allows them to accomplish this even if an antagonist is monitoring their messages, as long as their secret information remains secret. The security of the protocol is based on the widely held belief that a certain computational number theory problem called the discrete log problem is sufficiently hard.
Together Alice and Bob choose a large prime number and a number such that (Usually is chosen to be quite small, for ease of computation.) These numbers do not need to be secret, so they can be communicated freely over a public channel. Alice secretly chooses an integer and Bob secretly chooses an integer
Now Alice sends Bob the number and Bob sends Alice
Using her secret Alice computes Using his secret Bob computes Now Alice and Bob have a secret key known only to them, which can be used to send messages via any number of secure private-key cryptosystems.
Let and Suppose Alice picks and Bob picks Then Alice computes and Bob computes They send the results of these computations to each other. Upon receiving Alice computes and Bob computes So they have a key that they have agreed on without disclosing their secret numbers to each other. They can use this key to communicate securely via a cryptosystem of their choosing.
An eavesdropper (often called Eve) will see the results of any transmissions over public channels, so she will know and Her goal is to compute If she can compute and then she has the same information as Alice and Bob and hence can read their messages. Computing the exponent is like taking a "mod- base- logarithm" of but this is expected to be a hard problem in general. It is known as the discrete log problem. There is no known algorithm for efficiently computing discrete logs in general.
It is also widely believed that there is no faster way for Eve to compute than by finding and so that the security of the Diffie-Hellman protocol is as strong as the difficulty of the discrete log problem.
Continuing the above example, Eve knows and Without access to or she will be unable to use this information to deduce the shared key
Certain choices of and are better than others. Here are some guidelines that avoid common insecurities and attacks in the protocol.
(1) The prime should be chosen so that the largest prime factor of is large. If where the are all small primes, then an attack called the Pohlig-Hellman algorithm computes the discrete log of by using the Chinese remainder theorem and quickly computing mod
For this reason, it is common to select values of of the form where is a prime (called a Sophie Germain prime). Such are often called safe primes due to the security of the public keys based on arithmetic mod
(2) The base should be chosen so that has large order, i.e. generates a large subgroup of the multiplicative group This is so that an attacker cannot find a discrete log of by enumerating all the possibilities for it also increases the number of possible secret keys When is a safe prime, is often chosen to have order the following exercise explains why this is preferred to order
Let and You may assume that is prime and is a primitive root mod
Suppose Alice and Bob are carrying out the Diffie-Hellman protocol with these parameters. As a first step, Alice sends Bob and Bob sends Alice where and are secret positive integers less than known only to Alice and Bob, respectively.
An eavesdropper Eve knows the values of and , and sees the transmissions. In particular, she sees that Alice sends Bob the number and Bob sends Alice the number What can Eve deduce about and quickly? (That is, much more quickly than computing and --please don't compute and to solve the problem!)
Suppose when Alice is sending a message to Bob announcing , Eve intercepts the message and sends her own number to Bob. Eventually Bob and Eve agree on a secret key and Alice and Eve agree upon the key .
When Alice sends a message to Bob, she unknowingly uses the secret key , and Eve intercepts it, decrypts it, changes it, re-encrypts it using the key and sends it to Bob. In this way, Eve can read every message between Alice and Bob, modify the messages before passing them along, and do many other nefarious and disruptive things to Alice and Bob's communications. Note that this is accomplished without solving the discrete log problem.
In practice, there are variants of classic Diffie-Hellman that avoid this weakness, using signature schemes and other ideas. The resulting protocol is often referred to as the STS (station-to-station) protocol.
As of 2016, the recommended size of a Diffie-Hellman modulus to ensure security from state-of-the-art attacks is bits Another way to avoid certain special attacks that can handle large primes is to change the underlying group in which the arithmetic is done: instead of using the set of points on an elliptic curve over furnishes a group of about the same size, on which the discrete log problem seems to be much more difficult.
That is, given a suitable elliptic curve and prime Alice and Bob can agree on a point compute and respectively, and then use each other's computations to compute the point which can be translated to a shared private key. The advantage of this method is that it allows the use of smaller primes so that Alice and Bob's computations are cheaper while still maintaining an acceptable level of security.
There are also cryptosystems based on the Diffie-Hellman protocol directly, which use the presumed security of the discrete log problem to ensure that decrypting messages is hard for an unauthorized user. That is, Alice and Bob use the mechanism of Diffie-Hellman to send messages rather than simply agreeing on a key. The current industry standard cryptosystem in this family is known as the Integrated Encryption Scheme (IES).