title: 里程碑 02：Diffie-Hellman 密钥交换算法
tags:
  - zk
  - basic
  - cryptography
  - diffie-hellman​

WTF zk 教程 里程碑 02：Diffie-Hellman 密钥交换算法

这一讲，是WTF zk零知识证明教程的第2个里程碑，你应该已经掌握了数论和群论的基础知识。在里程碑中，我们将学习 Diffie-Hellman 密钥交换算法，这是一种在不安全的通信信道上共享密钥的方法。这个算法是密码学中的重要基石，为安全通信提供了基础。

1. 背景介绍

Diffie-Hellman 密钥交换算法是由 Whitfield Diffie 和 Martin Hellman 在 1976 年首次提出的。它是一种公钥密码学算法，允许两个远程用户在不共享密钥的情况下达成一个共同的密钥。

• 公钥密码学： Diffie-Hellman 算法是最早的公钥密码学算法，它的提出打破了以前需要共享密钥的通信模式，为现代安全通信奠定了基础。

• 安全性： 基于离散对数问题的难解性，通信双方可以在不公开密钥的情况下安全协商出一个共享密钥。

• 应用广泛： Diffie-Hellman 算法被广泛应用于安全通信领域，包括 TLS/SSL 协议、SSH 通信等。

2. 算法原理

Diffie-Hellman 算法的核心思想是利用离散对数问题，即给定大素数 p、底数 g 和 A \equiv g^a \mod p，要计算出 a 的值是一个困难问题。算法步骤如下：

2.1 密钥生成

1. 选择参数： 选择两个大素数 p 和它的原根（乘法生成元） g。p 和 g 都是公开的。
2. 私钥生成： 每个通信方选择一个私钥。假设 Alice 选择私钥 a，Bob 选择私钥 b， a 和 b 是隐私的。
3. 计算公钥： Alice 计算 A = g^a \mod p，Bob 计算 B = g^b \mod p。
4. 交换公钥： Alice 将 A 发送给 Bob，Bob 将 B 发送给 Alice，这一步 A 和 B 都是公开的。

这一步，公钥 p, g, A, B 是公开的，而私钥 a, b 是隐私的。

2.2 密钥协商

1. 计算会话密钥： Alice 收到 Bob 的公钥 B 后，计算 K = B^a \mod p；同样，Bob 收到 Alice 的公钥 A 后，计算 K = A^b \mod p。
2. 生成共享密钥： Alice 和 Bob 现在都有相同的密钥 K，该值可以作为会话密钥用于加密通信。由于窃听者没有 a 和 b 的信息，无法计算出 K，因此密钥 K 是隐私的。

3. 示例

为了更好地理解 Diffie-Hellman 算法，我们使用一个简单的示例进行演示。

1. 选择参数： 选择素数 p = 13 和它的原根 g = 6。
2. 私钥生成： Alice 选择私钥 a = 5，Bob 选择私钥 b = 4。
3. 计算公钥： Alice 计算 A = 6^5 = 2 \mod 13，Bob 计算 B = 6^{4} = 9 \mod 13。
4. 交换公钥： Alice 将 A = 2 发送给 Bob，Bob 将 B = 9 发送给 Alice。
5. 计算会话密钥： Alice 计算 K = 9^5 \mod 13 = 3，Bob 计算 K = 2^{4} \mod 13 = 3。
6. 生成共享密钥： Alice 和 Bob 现在都有相同的共享密钥 K = 3，可以用于进一步的加密通信。

4. 算法逻辑

Diffie-Hellman 算法的安全性基于离散对数问题的困难性。对于窃听者，它能得到的公开信息是素数 p，原根 g，Alice的公钥 A = g^a \mod p，和Bob的公钥 B = g^b \mod p。而窃听者要得到共享密钥 K =g^{ab} \mod p，必须要计算出 a = \log_g{A} 或 b = \log_g{B}，但这是离散对数问题，没有有效算法，无法计算。因此，Diffie-Hellman 算法是安全的。

另外，由于 p 是大素数，整数模 p 乘法群 Z^*_p 的阶（元素个数）为 p-1，很大。由于原根 g 是 Z^*_p 的生成元，它的各次幂可以覆盖 Z^*_p 中所有元素，使得暴力穷举来破解离散对数问题是很难。

5. 代码实现

下面是一个简单的 Python 实现，演示了 Diffie-Hellman 密钥交换算法。

import random

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def modinv(a, b):
    m0, x0, x1 = b, 0, 1
    while a > 1:
        q = a // b
        a, b = b, a % b
        x0, x1 = x1 - q * x0, x0
    return x1 + m0 if x1 < 0 else x1

def generate_params():
    p = random_prime()
    g = random.randint(2, p - 2)
    return p, g

def generate_private_key():
    return random.randint(2, 2**16)

def generate_public_key(private_key, p, g):
    return pow(g, private_key, p)

def generate_shared_secret(private_key, public_key, p):
    return pow(public_key, private_key, p)

def random_prime():
    while True:
        num = random.randint(10**3, 10**4)
        if is_prime(num):
            return num

# 示例
p, g = generate_params()
alice_private_key = generate_private_key()
bob_private_key = generate_private_key()

alice_public_key = generate_public_key(alice_private_key, p, g)
bob_public_key = generate_public_key(bob_private_key, p, g)

alice_shared_secret = generate_shared_secret(alice_private_key, bob_public_key, p)
bob_shared_secret = generate_shared_secret(bob_private_key, alice_public_key, p)

print("大素数 (p):", p)
print("原根/生成元 (g):", g)
print("Alice's 私钥:", alice_private_key)
print("Bob's 私钥:", bob_private_key)
print("Alice's 公钥:", alice_public_key)
print("Bob's 公钥:", bob_public_key)
print("共享私钥 (Alice):", alice_shared_secret)
print("共享私钥 (Bob):", bob_shared_secret)

## 输出示例
# 大素数 (p): 2707
# 原根/生成元 (g): 1620
# Alice's 私钥: 8706
# Bob's 私钥: 60566
# Alice's 公钥: 1183
# Bob's 公钥: 2369
# 共享私钥 (Alice): 1776
# 共享私钥 (Bob): 1776
​

6. 总结

Diffie-Hellman 密钥交换算法是一种重要的密码学算法，它解决了在不安全信道上共享密钥的问题，为现代安全通信提供了基础。通过离散对数问题的困难性，Diffie-Hellman 确保了密钥共享的安全性。在实际应用中，Diffie-Hellman 被广泛用于 TLS/SSL 协议、SSH 通信等场景，为通信双方提供了一种安全可靠的密钥共享机制。