Skip to content

Latest commit

 

History

History
144 lines (104 loc) · 6.13 KB

readme.md

File metadata and controls

144 lines (104 loc) · 6.13 KB
Raw
title tags
里程碑 02：Diffie-Hellman 密钥交换算法
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 通信等场景，为通信双方提供了一种安全可靠的密钥共享机制。