Diffie-Hellman

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 \(p\) and a number \(g\) such that \(1 < g <p.\) (Usually \(g\) 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 \(n,\) and Bob secretly chooses an integer \(m.\)

Now Alice sends Bob the number \( g^n \pmod p,\) and Bob sends Alice \( g^m \pmod p.\)

Using her secret \(n,\) Alice computes \(s \equiv (g^{m})^{n} \equiv g^{mn} \pmod{p}.\) Using his secret \(m,\) Bob computes \(s \equiv (g^{n})^{m} \equiv g^{mn} \pmod{p}.\) Now Alice and Bob have a secret key \( s\) known only to them, which can be used to send messages via any number of secure private-key cryptosystems.

Let \( p = 191\) and \(g=2.\) Suppose Alice picks \( 42\) and Bob picks \( 33.\) Then Alice computes \( 2^{42} \equiv 20 \pmod{191}\) and Bob computes \( 2^{33} \equiv 103 \pmod{191}.\) They send the results of these computations to each other. Upon receiving \( 103,\) Alice computes \( 103^{42} \equiv 115 \pmod{191},\) and Bob computes \( 20^{33} \equiv 115 \pmod{191}.\) 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 \( p,g,g^n \pmod{p},\) and \(g^m \pmod{p}.\) Her goal is to compute \( g^{mn} \pmod p.\) If she can compute \( m\) and \(n,\) then she has the same information as Alice and Bob and hence can read their messages. Computing the exponent \( n\) is like taking a "mod-\(p\) base-\(g\) logarithm" of \( g^n,\) 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 \(\pmod p\) in general.

It is also widely believed that there is no faster way for Eve to compute \( g^{mn} \pmod p\) than by finding \(m\) and \(n,\) 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 \( p=191,\) \( g=2,\) \( 2^n \equiv 20 \pmod{191},\) and \( 2^m \equiv 103\pmod{191}.\) Without access to \(m=33\) or \(n=42,\) she will be unable to use this information to deduce the shared key \( 115.\)

Certain choices of \( p\) and \( g\) are better than others. Here are some guidelines that avoid common insecurities and attacks in the protocol.

(1) The prime \( p\) should be chosen so that the largest prime factor of \( p-1\) is large. If \( p-1 = q_1^{a_1}\cdots q_k^{a_k},\) where the \( q_i \) are all small primes, then an attack called the Pohlig-Hellman algorithm computes the discrete log \(x\) of \( g^x\) by using the Chinese remainder theorem and quickly computing \( x\) mod \( q_i^{a_i}.\)

For this reason, it is common to select values of \(p\) of the form \( p=2q+1,\) where \( q\) is a prime (called a Sophie Germain prime). Such \(p\) are often called safe primes due to the security of the public keys based on arithmetic mod \(p.\)

(2) The base \( g\) should be chosen so that \(g\) has large order, i.e. \( g\) generates a large subgroup of the multiplicative group \( ({\mathbb Z}/p{\mathbb Z})^*.\) This is so that an attacker cannot find a discrete log of \( g^m\) by enumerating all the possibilities for \( g^m\) \((\)it also increases the number of possible secret keys \( g^{mn}).\) When \(p=2q+1\) is a safe prime, \( g\) is often chosen to have order \(q;\) the following exercise explains why this is preferred to order \(2q = p-1:\)

Suppose when Alice is sending a message to Bob announcing \(g^{n} \bmod{p}\), Eve intercepts the message and sends her own number \(g^{t} \bmod{p}\) to Bob. Eventually Bob and Eve agree on a secret key \(g^{tm} \bmod{p}\) and Alice and Eve agree upon the key \(g^{tn} \bmod{p}\).

When Alice sends a message to Bob, she unknowingly uses the secret key \(g^{tn} \bmod p \), and Eve intercepts it, decrypts it, changes it, re-encrypts it using the key \(g^{tm} \bmod n, \) 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 \(p\) to ensure security from state-of-the-art attacks is \( 2048 \) bits \(\big(2^{2048}\big).\) 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 \( ({\mathbb Z}/p{\mathbb Z})^*,\) the set of points on an elliptic curve over \( {\mathbb F}_p\) 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 \( E\) and prime \(p,\) Alice and Bob can agree on a point \( P \in E({\mathbb F}_p), \) compute \( nP \) and \( mP,\) respectively, and then use each other's computations to compute the point \( mnP,\) which can be translated to a shared private key. The advantage of this method is that it allows the use of smaller primes \(p,\) 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).