密码学 - 迪菲-赫尔曼算法

---

---

迪菲-赫尔曼密钥交换是一种数字加密方法，两个不同的参与方可以在公共信道上安全地交换加密密钥，而无需通过互联网发送他们的通信。双方都使用对称加密来加密和解密他们的消息。

惠特菲尔德·迪菲和马丁·赫尔曼于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 的区别

差异如下表所示：