The Diffie-Hellman Key Exchange

What is the Diffie-Hellman key exchange protocol?

The Diffie-Hellman Key Exchange (DHKE) protocol was the first publicly published algorithm for public key exchange, which offered an elegant solution to Alice’s and Bob’s dilemma, who want to share a joint common, secret key for a symmetric cipher, whereas their only possible communication channel is insecure and eavesdropped on by Eve.

The DHKE solves this problem by making use of the difficulty of computing the so-called discrete logarithm over the finite field $\mathbb{Z}_{p}$. To use Diffie-Hellman, Alice and Bob have to choose a cyclic group. The classic Diffie-Hellman key exchange protocol works in the multiplicative group $\mathbb{Z}_{p}^{*}$. In summary, the Diffie-Hellman protocol is a cryptographic protocol that allows Alice and Bob to establish a shared secret over an insecure channel.

In the first step, Alice and Bob agree on specific domain parameters, namely on a large prime $p$ and an integer $\alpha \quad mod \space p$, where $\alpha$ should have a large order, ideally is a generator of the multiplicative group $\mathbb{Z}_{p}^{*}$, and publish these parameters. Now, they can generate a joint secret key $k$ with the DHKE protocol as follows:

Alice picks a secret integer $a$ and computes

$$A \equiv \alpha^{a} \space mod \space p$$

and Bob chooses a secret integer $b$ and computes

$$B \equiv \alpha^{b} \space mod \space p.$$

Now, Alice and Bob exchange these values, i.e., Alice sends $A$ to Bob whilst Bob sends $B$ to Alice. At this point, Eve notices these values since she’s eavesdropping on the insecure channel over which these computations are sent. Finally, they again use their secret integers, whereas Alice computes

$$B^{a} \equiv\left(\alpha^{b}\right)^{a} \equiv \alpha^{b a} \equiv \alpha^{a b} \space\space mod \space p,$$

and Bob computes

$$A^{b} \equiv\left(\alpha^{a}\right)^{b} \equiv \alpha^{a b} \space\space mod \space p.$$

As we can see, Alice and Bob computed the same value $k=B^{a}=A^{b}$, and this shared value is their exchanged joint key $k$, which can be used to establish a secure communication by using $k$ as a secret key for a symmetric cipher.

Note that Eve knows $p$ and $\alpha$ since these are public knowledge, and she also knows the computed values $A$ and $B$ and hence $\alpha^{a}$ and $\alpha^{b}$. But she doesn’t know the shared secret value $\alpha^{a b}$, and this is exactly the problem Eve has to solve in order to acquire the key. This problem is known as the Diffie-Hellman problem (Jeffrey Hoffstein et al. (2014)Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. An Introduction to Mathematical Cryptography. Undergraduate Texts in Mathematics. New York, 2014. Springer.).