Introduction

Diffie-Hellman 演算法是用來讓兩位使用者能夠安全地交換金鑰，以便之後在通訊中可以使用該金鑰作為對稱式加密之用。而 Diffie-Hellman 演算法的安全性設計是依賴於計算離散對數（discrete logarithm）的困難性。

Diffie-Hellman 演算法

質數 $q$ 與原根 $p$ 是兩個公開的整數，我們假設 Alice 和 Bob 希望共享一把金鑰。

Alice

1. Alice 選擇一個隨機的整數 $X_A$ 且 $X_A \lt q$
2. 計算 $Y_A = p^{X_A} \bmod q$
3. $X_A$ 是私鑰、$Y_A$ 是公鑰
4. 將自己的公鑰 $Y_A$ 傳送給 Bob
5. 收到 Bob 的公鑰 $Y_B$
6. 計算金鑰 $K = (Y_B)^{X_A} \bmod q$

Bob

1. Bob 選擇一個隨機的整數 $X_B$ 且 $X_B \lt q$
2. 計算 $Y_B = p^{X_B} \bmod q$
3. $X_B$ 是私鑰、$Y_B$ 是公鑰
4. 將自己的公鑰 $Y_B$ 傳送給 Alice
5. 收到 Alice 的公鑰 $Y_A$
6. 計算金鑰 $K = (Y_A)^{X_B} \bmod q$

範例

令質數 $q = 11$ 與原根 $p = 7$ 是兩個公開的整數。為了方便說明，這裡選用的質數 $q$ 很小，實際應用場景中會使用超大質數。

Alice

1. Alice 選擇一個隨機的整數 $X_A = 4, \space X_A \lt q$
2. 計算 $Y_A = p^{X_A} \bmod q = 7^4 \bmod 11 = 3$
3. 私鑰 $X_A = 4$
   公鑰 $Y_A = 3$
4. 將自己的公鑰 $Y_A = 3$ 傳送給 Bob
5. 收到 Bob 的公鑰 $Y_B = 2$
6. 計算金鑰 $K = (Y_B)^{X_A} \bmod q = 2^4 \bmod 11 = 5$

Bob

1. Bob 選擇一個隨機的整數 $X_B = 3, \space X_B \lt q$
2. 計算 $Y_B = p^{X_B} \bmod q = 7^3 \bmod 11 = 2$
3. 私鑰 $X_B = 3$
   公鑰 $Y_B = 2$
4. 將自己的公鑰 $Y_B = 2$ 傳送給 Alice
5. 收到 Alice 的公鑰 $Y_A = 3$
6. 計算金鑰 $K = (Y_A)^{X_B} \bmod q = 3^3 \bmod 11 = 5$

透過上面 Diffie-Hellman 演算法後可得雙方共享的金鑰 $K = 5$