Then Notes 隨筆

Diffie-Hellman 金鑰交換演算法

cover

Introduction

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

Diffie-Hellman 演算法

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

Alice

  1. Alice 選擇一個隨機的整數 XAX_A 且 XA<qX_A \lt q
  2. 計算 YA=pXA mod qY_A = p^{X_A} \bmod q
  3. XAX_A 是私鑰、YAY_A 是公鑰
  4. 將自己的公鑰 YAY_A 傳送給 Bob
  5. 收到 Bob 的公鑰 YBY_B
  6. 計算金鑰 K=(YB)XA mod qK = (Y_B)^{X_A} \bmod q

Bob

  1. Bob 選擇一個隨機的整數 XBX_B 且 XB<qX_B \lt q
  2. 計算 YB=pXB mod qY_B = p^{X_B} \bmod q
  3. XBX_B 是私鑰、YBY_B 是公鑰
  4. 將自己的公鑰 YBY_B 傳送給 Alice
  5. 收到 Alice 的公鑰 YAY_A
  6. 計算金鑰 K=(YA)XB mod qK = (Y_A)^{X_B} \bmod q

範例

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

Alice

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

Bob

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

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