密碼學 - 迪菲-赫爾曼演算法

---

---

迪菲-赫爾曼金鑰交換是一種數字加密方法，兩個不同的參與方可以在公共通道上安全地交換加密金鑰，而無需透過網際網路傳送他們的通訊。雙方都使用對稱加密來加密和解密他們的訊息。

惠特菲爾德·迪菲和馬丁·赫爾曼於1976年發表了它，這是最早的實用公鑰密碼學案例之一。

迪菲-赫爾曼金鑰交換將數字提高到特定的冪以生成解密金鑰。金鑰的組成部分從未直接傳輸，這使得潛在的程式碼破解者在數學上無法完成任務。該方法在金鑰交換過程中不共享任何資訊。即使事先彼此不瞭解，雙方也可以協作生成金鑰。

迪菲-赫爾曼的歷史

惠特菲爾德·迪菲和馬丁·赫爾曼於1976年開發了迪菲-赫爾曼演算法，它為公鑰密碼學鋪平了道路，並極大地提高了數字安全性。它是為解決在不安全通道上安全金鑰交換而開發的，取代了對稱金鑰分發方法，併為SSL/TLS等安全通訊協議奠定了基礎。

該演算法對世界地緣政治產生了相當大的影響，例如在冷戰後期用於確保北約國家之間的絕密通訊。

迪菲-赫爾曼是如何工作的？

要使用迪菲-赫爾曼，兩個終端使用者Alice和Bob必須就正整數p和q達成一致，其中p是素數，q是p的生成元。生成元q是一個數字，當將其提高到小於p的正整數冪時，不會為任何兩個這樣的整數給出相同的結果。p的值可以很大，而q的值通常很小。

在Alice和Bob秘密決定了p和q之後，他們選擇正整數私鑰a和b。兩者都小於素數模p。任何一方都不與任何人共享他們的私鑰；理想情況下，他們記住這些數字，並且不將其寫下或儲存在任何地方。之後，Alice和Bob使用下面的演算法根據他們的私鑰計算公鑰a*和b* −

a* = qa mod p
b* = qb mod p

兩個使用者可以透過不安全的通訊通道（例如網際網路或公司的廣域網）交換他們的公鑰a^*和b^*。使用各自的私鑰，每個使用者都可以根據這些公鑰生成一個數字x。Alice使用以下公式計算x −

x = (b*) mod p

Bob使用以下公式計算x：x = (a^*)^b mod p

上述兩個公式中的任何一個都會給出x值的相同結果。但是，計算x所需的私鑰a和b並沒有透過公共通道傳送。即使藉助能夠進行數百萬次嘗試的高效系統，潛在的駭客也幾乎沒有機會正確確定x，因為它的大小巨大且看似隨機。因此，使用解密金鑰x，兩個使用者理論上可以使用他們選擇的任何加密技術在公共通道上進行私人對話。

分步指南

讓我們以Alice和Bob這兩個朋友的簡單案例來描述迪菲-赫爾曼 −

選擇素數和生成元

Bob和Alice已經決定了一個素數，p = 23。

此外，他們還同意一個生成元，g = 5。

選擇私鑰

Alice選擇一個秘密數字，例如a = 6。

Bob選擇一個秘密數字，例如b = 15。

確定公鑰

Alice首先計算A = g^a mod p，得到A = 5⁶ mod 23，即8。

Bob使用公式B = g^b mod p得到B = 5¹⁵ mod 23，即19。

交換公鑰

Alice向Bob提供她計算出的公鑰A = 8。

Bob向Alice傳送他計算出的公鑰B = 19。

計算共享金鑰

Alice使用Bob的公鑰計算共享金鑰 −

K_A = B^a mod p −

K_A = 19⁶ mod 23，即2。

Bob使用Alice的公鑰計算共享金鑰 −

K_B = A^b mod p −

K_B = 8¹⁵ mod 23，即2。

因此，Alice和Bob現在可以使用相同的共享金鑰K = 2來加密他們的訊息。

即使竊聽者成功獲取素數 p=23 和生成元 g=5，也很難推算出共享金鑰。這是因為他們不知道愛麗絲或鮑勃的私鑰。

Diffie-Hellman 演算法實現

我們將使用 Python、Java 和 C++ 實現 Diffie-Hellman 演算法。

Python 實現

下面的 Python 程式碼演示了 Diffie-Hellman 金鑰交換演算法，實現了愛麗絲和鮑勃之間的安全通訊。

為了避免溢位錯誤，`calculate_power` 函式有效地計算了 a^b mod P，其中 a、b 和 P 是大數。雙方商定的重要引數（例如素數（prime）和生成元值（generator））被初始化。每一方選擇其私鑰（`private_key_bob` 和 `private_key_alice`），然後使用模冪運算計算其公鑰。最終，在交換公鑰後，愛麗絲和鮑勃分別計算共享金鑰（`secret_key_alice` 和 `secret_key_bob`），從而實現安全通訊。

以下是使用 Python 實現的 Diffie-Hellman 演算法：

示例

def calculate_power(base, exponent, modulus):
   """Power function to return value of (base ^ exponent) mod modulus."""
   if exponent == 1:
      return base
   else:
      return pow(base, exponent) % modulus

# Driver code
if __name__ == "__main__":
   prime = 23
   generator = 5
   private_key_alice = 6
   private_key_bob = 15

   # Generating public keys
   x = calculate_power(generator, private_key_alice, prime)
   y = calculate_power(generator, private_key_bob, prime)

   # Generating secret keys after the exchange of keys
   secret_key_alice = calculate_power(y, private_key_alice, prime)
   secret_key_bob = calculate_power(x, private_key_bob, prime)

   # Output
   print("Prime number (P):", prime)
   print("Generator value (G):", generator)
   print("Alice's private key (a):", private_key_alice)
   print("Bob's private key (b):", private_key_bob)
   print("Secret key for Alice:", secret_key_alice)
   print("Secret key for Bob:", secret_key_bob)

以下是上述示例的輸出：

輸入/輸出

Prime number (P): 23
Generator value (G): 5
Alice's private key (a): 6
Bob's private key (b): 15
Secret key for Alice: 2
Secret key for Bob: 2

C++ 實現

這段程式碼使得愛麗絲和鮑勃能夠安全地進行通訊。該方法透過模冪運算有效地計算共享金鑰，併兼容大整數。愛麗絲和鮑勃生成各自的私鑰並計算對應的公鑰。然後，每一方使用這些公鑰以及自己的私鑰分別計算共享金鑰。

以下程式碼在 C++ 中實現了 Diffie-Hellman 金鑰交換演算法。

示例

#include <iostream>
#include <cmath>

using namespace std;

// Function to calculate power modulo P
long long int calculatePower(long long int base, long long int exponent, long long int modulus) {
   if (exponent == 1)
      return base;
   else
      return (((long long int)pow(base, exponent)) % modulus);
}

int main() {
   long long int prime, generator, secretAlice, secretBob, publicAlice, publicBob, secretKeyAlice, secretKeyBob;

   // Prime number and generator value initialization
   prime = 23;
   cout << "Prime number (P): " << prime << endl;

   generator = 5; 
   cout << "Generator value (G): " << generator << endl;

   // Alice's private key initialization
   secretAlice = 6;
   cout << "Alice's private key (a): " << secretAlice << endl;

   // Calculate Alice's public key
   publicAlice = calculatePower(generator, secretAlice, prime); 

   // Bob's private key initialization
   secretBob = 15; 
   cout << "Bob's private key (b): " << secretBob << endl;

   // Calculate Bob's public key
   publicBob = calculatePower(generator, secretBob, prime); 

   // Calculate secret keys for Alice and Bob
   secretKeyAlice = calculatePower(publicBob, secretAlice, prime); 
   secretKeyBob = calculatePower(publicAlice, secretBob, prime); 

   // Output secret keys
   cout << "Secret key for Alice: " << secretKeyAlice << endl;
   cout << "Secret key for Bob: " << secretKeyBob << endl;

   return 0;
}

以下是上述示例的輸出：

輸入/輸出

Prime number (P): 23
Generator value (G): 5
Alice's private key (a): 6
Bob's private key (b): 15
Secret key for Alice: 2
Secret key for Bob: 2

Java 實現

在這個實現中，我們使用了與 C++ 程式中相同的方法。但是，我們建立了一個名為 `DiffieHellman` 的類，其中包含 `calculatePower()` 函式和 `main()` 函式。Java 實現如下：

示例

public class DiffieHellman {

   // Power function to return value of a ^ b mod P
   private static long calculatePower(long base, long exponent, long modulus) {
      if (exponent == 1)
         return base;
      else
         return (((long) Math.pow(base, exponent)) % modulus);
   }

   // Driver code
   public static void main(String[] args) {
      long prime, generator, x, privateKeyAlice, y, privateKeyBob, secretKeyAlice, secretKeyBob;

      // Both parties agree upon the public keys generator and prime

      // A prime number prime is chosen
      prime = 23;
      System.out.println("Prime number (P): " + prime);

      // A primitive root for prime, generator is chosen
      generator = 5;
      System.out.println("Generator value (G): " + generator);

      // Alice chooses her private key privateKeyAlice
      privateKeyAlice = 6;
      System.out.println("Alice's private key (a): " + privateKeyAlice);

      // Gets the generated key
      x = calculatePower(generator, privateKeyAlice, prime);

      // Bob chooses his private key privateKeyBob
      privateKeyBob = 15;
      System.out.println("Bob's private key (b): " + privateKeyBob);

      // Gets the generated key
      y = calculatePower(generator, privateKeyBob, prime);

      // Generating the secret key after the exchange of keys
      secretKeyAlice = calculatePower(y, privateKeyAlice, prime); // Secret key for Alice
      secretKeyBob = calculatePower(x, privateKeyBob, prime); // Secret key for Bob

      System.out.println("Secret key for Alice: " + secretKeyAlice);
      System.out.println("Secret key for Bob: " + secretKeyBob);
   }
}

以下是上述示例的輸出：

輸入/輸出

Prime number (P): 23
Generator value (G): 5
Alice's private key (a): 6
Bob's private key (b): 15
Secret key for Alice: 2
Secret key for Bob: 2

應用/用途

Diffie-Hellman 金鑰交換的目標是為對稱金鑰演算法開發安全的金鑰生成和共享通道。它常用於前向保密、加密和密碼認證金鑰協商。密碼認證金鑰協商可防止中間人攻擊 (MitM)。前向保密過程透過為每個會話生成新的金鑰對來防止金鑰丟失。

Diffie-Hellman 金鑰交換用於多種安全協議，包括傳輸層安全 (TLS)、安全外殼協議 (SSH) 和 IP 安全 (IPsec)。例如，在 IPsec 中，該加密機制用於生成和輪換金鑰。

雖然 Diffie-Hellman 金鑰交換可用於建立公鑰和私鑰，但 Rivest-Shamir-Adleman 演算法（或 RSA 演算法）也是另一種選擇，因為它可以簽名公鑰證書。

Diffie-Hellman 金鑰交換示例

Diffie-Hellman 金鑰交換技術是一種加密技術。例如，愛麗絲和鮑勃可以使用它在開放的公共網路上交換敏感資料，同時保護自己免受駭客和竊聽者的攻擊。這個開放的公共網路可以在咖啡館中找到。

愛麗絲和鮑勃私下選擇秘密金鑰，然後執行一個函式來生成公鑰。共享的是結果，而不是函式本身。即使其他人可以訪問所有相關的數字，也很難推斷出這些數字來自哪個函式。

之後，愛麗絲和鮑勃使用從對方收到的結果、他們獨特的秘密號碼和初始素數值分別執行函式。然後，愛麗絲和鮑勃得到一個其他人無法知道的共享金鑰。現在，鮑勃和愛麗絲可以安全地互相通訊，而無需擔心外部人士。

漏洞

基本版本的 Diffie-Hellman 的主要限制是缺乏身份驗證。僅使用 Diffie-Hellman 的通訊容易受到中間人攻擊 (MitM)。Diffie-Hellman 應與公認的身份驗證方法（如數字簽名）結合使用，以驗證公共通訊介質上的使用者身份。

Diffie-Hellman 金鑰交換也容易受到 Logjam 攻擊，特別是針對 TLS 協議。Logjam 攻擊將 TLS 連線降低到 512 位加密，允許攻擊者訪問和修改透過連線傳輸的資料。如果正確實施，Diffie-Hellman 金鑰交換仍然是安全的。例如，使用 2048 位金鑰時，Logjam 攻擊將失敗。

優勢/益處

• 它是一種有效的金鑰交換和安全連線設定方法，無需事先準備。
• 它提供前向保密性，即使一個金鑰被洩露，也能確保之前的對話安全。
• 無需傳輸安全的秘密金鑰，降低了金鑰在傳輸過程中被洩露的可能性。
• 此技術允許大量使用者安全地進行互動，使其適用於大型應用程式。

劣勢/侷限性

• 需要安全的首次公鑰交換以防止中間人攻擊和竊聽攻擊。
• 容易受到擁有強大計算能力的對手的暴力破解攻擊。
• 計算量很大，可能會影響效能，特別是對於大的素數。
• 缺乏身份驗證，需要採取進一步措施來驗證通訊雙方的身份。

Diffie-Hellman 和 RSA 的區別

差異如下表所示：