Diffie-Hellman Key Agreement Protocol

The Diffie-Hellman key agreement protocol, which we’ll henceforth refer to simply as the Diffie-Hellman protocol from now on, is one of the most influential cryptographic protocols. Not only does it predate the public discovery of RSA, but it remains the basis for the vast majority of modern AKE protocols based on key agreement. We’ll explain the idea behind the Diffie-Hellman protocol and then examine an example of an AKE protocol based on it.

Idea behind the Diffie-Hellman protocol

The Diffie-Hellman protocol requires the existence of:

• A public-key cryptosystem with a special property, which we’ll discuss shortly. We denote the public and private keys of Alice and Bob in this cryptosystem by $(P_A, \space S_A)$ and $(P_B, \space S_B)$, respectively. These may be either temporary key pairs that have been generated specifically for this protocol run or long-term key pairs used for more than one protocol run.

• A combination function $F$ with a special property, which we’ll discuss shortly. By a ‘combination’ function, we mean a mathematical process that takes two numbers, $x$ and $y$ as input and outputs a third number, which we denote with $F(x, y)$. Addition is an example of a combination function, with $F(x, y) = x + y$.

The Diffie-Hellman protocol is designed for environments where secure channels don’t yet exist. Indeed, it’s often used to establish a symmetric key, which can then be used to secure such a channel. It’s important to remember that, unless otherwise stated, we assume all the exchanged messages take place over an unprotected (public) channel that an attacker can observe and, potentially, modify. The basic idea behind the Diffie-Hellman protocol is that:

1. Alice sends her public key $P_A$ to Bob.

2. Bob sends his public key $P_B$ to Alice.

3. Alice computes $F(S_A, \space P_B)$. Alice can conduct this computation since it involves her private key $S_A$.

4. Bob computes $F(S_B, \space P_A)$. Note that only Bob can conduct this computation since it involves his private key $S_B$.

The special property for the public-key cryptosystem and the combination function $F$ is that:

$$F(S_A, \space P_B) = F(S_B, \space P_A)$$

At the end of the protocol, Alice and Bob will thus share this value, which we denote with $Z_{AB}$. As we’ll discuss in a moment, this shared value $Z_{AB}$ can then easily be converted into a key of the required length. Since the private keys of Alice and Bob are both required to compute $Z_{AB}$, it should be computable only by Alice and Bob and not by anyone else (an attacker) who observed the protocol messages. This is true even though the attacker will have seen $P_A$ and $P_B$.

The somewhat surprising aspect of the Diffie-Hellman protocol is that without sharing any secret information, Alice and Bob can jointly generate a secret value by communicating only over a public channel. This was a revolutionary idea when it was first proposed in 1976, and it remains a slightly counterintuitive one. This property makes the Diffie-Hellman protocol extremely useful.

Instantiation of the Diffie-Hellman protocol

To fully specify the Diffie-Hellman protocol, we need to find a suitable public-key cryptosystem and a suitable function $F$. Fortunately, we won’t need any new public-key cryptosystems to describe the most common instantiation of the Diffie-Hellman protocol. This is because the ElGamal cryptosystem has precisely the property we need. Equally fortunately, the required function $F$ is very simple.