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$