📂Number Theory

Proof of the Diffie-Hellman Key Exchange Algorithm

Buildup

From left to right, let’s call them Alice, Bob, and Eve. Alice and Bob are the parties exchanging messages, and Eve is a passive attacker interested in the messages. The orange box denotes information known only to Alice, the sky-blue box denotes information known only to Bob, and the black box denotes information that is public (also known to Eve).

Alice and Bob intend to exchange messages under the cryptography system $( \mathcal{K} , \mathcal{M} , \mathcal{C} , e_{k} , d_{k} )$. Unfortunately, Eve knows the decryption function $d_{k}$ and cannot directly transmit the key $k$ without Eve finding out. However, if in this situation, Alice and Bob can each generate a key $K$ that only the two of them share, Eve would not be able to decrypt the ciphertext despite knowing $d_{k}$ because she does not know the key $K$. This solution is exactly the Diffie-Hellman Key Exchange Algorithm.

Algorithm ¹

Let $\mathbb{F}_{p}^{ \ast } = \mathbb{F}_{p} \setminus \left\{ 0 \right\} = \left\{ 1, g , g^2 , \cdots , g^{p-2} \right\}$ be a cyclic group with $(p-1)$ elements.

---

Step 1.

A very large prime number $p$ and $\text{ord}_{p} (g)$, which is a large prime number, are chosen and made public.

---

Step 2.

Alice picks an arbitrary integer $a$, and Bob picks an arbitrary integer $b$.

---

Step 3. Encryption

$A \equiv g^{a} \pmod{p}$ and $B \equiv g^{b} \pmod{p}$ are calculated and made public.

---

Step 4. Decryption

By using the cipher $c = e_{K} (m)$ encrypted with $K$ as the key, $K \equiv B^{a} \equiv A^{b} \pmod{p}$ is computed, and Eve realistically cannot know $K$, so she cannot know $m = d_{K} (c)$.

Description

In Step 1., $\text{ord}_{p} (g)$ serves as the order, which should be as large a prime as possible so that $g_{n}$ makes it difficult to predict changes depending on $n$. If it only reaches about $\text{ord}_{p} (g) = 3$, calculating $K$ becomes too easy. If $\text{ord}_{p} (g) = nm$ is a composite number, then when it’s said that $g^{nm} \equiv 1 \pmod{p}$, it means $( g^{n} ) ^{m} \equiv 1 \pmod{p}$; hence it’s essentially the same as using $G:=g^{n}$, which is a smaller order.

It’s important to note that the Diffie-Hellman key exchange algorithm itself does not become some cryptographic system but is merely a method for Alice and Bob to create a secret key $K$ in the presence of a passive attacker. The $K$ obtained in this way is unrelated to the message, and the cryptographic system does not change at all.

Proof

Decryption

Alice and Bob, knowing $a$ and $b$, can easily compute $$\begin{align*} K & \equiv A^{b} \\ & \equiv \left(g^{a} \right)^{b} \\ & \equiv g^{ab} \\ & \equiv \left(g^{b} \right)^{a} \\ & \equiv B^{a} \pmod{p} \end{align*}$$ Therefore, with the public $g$, knowing either $a$ or $b$ is enough to find $K$.

■

Encryption

Since Eve only knows $A$ and $B$, not $a$ and $b$, she has to solve the discrete logarithm problem $A^{x} \equiv K \pmod{p}$ or $B^{x} \equiv K \pmod{p}$. This is very difficult, so Alice and Bob can communicate securely from Eve using $K$ as the key.

■

See Also

• Discrete logarithm problem

Security algorithms utilizing the difficulty of the discrete logarithm problem

• Diffie-Hellman key exchange algorithm
• ElGamal public-key cryptosystem

Attack algorithms for the discrete logarithm problem

• Shanks’ algorithm
• Pollard’s rho algorithm for logarithms
• Conditions under which the discrete logarithm problem is easily solvable