加解密模式分析 - DH 密钥交换协议
今天我们将分析 Diffie-Hellman 密钥交换协议（DH Key Exchange Protocol），这是一种基于离散对数问题的非对称加密算法。这和之前的 ElGamal 加密算法不同，DH 密钥交换协议的主要目的是让两个通信方在不安全的信道上安全地协商出一个共享的密钥，而不是直接加密消息。
实际上，经过我们前面的非对称加密算法的学习，会发现加密的时候，如果选择直接加密消息，效率会非常低。例如，当明文过长时，RSA 算法要有足够大的素数才行。
所以我们通常会使用 DH 密钥交换协议来协商出一个共享的密钥，然后使用对称加密算法（如 AES）来加密实际的消息，这样既保证了安全性，又提高了效率。
DH 密钥交换协议过程 😛
由于经典的 DH 密钥交换协议就是基于离散对数难题的，我们这里就不再赘述它的数学原理了。
首先通信双方先共享两个公共参数，模数 $p$ 和生成元 $g$。
Alice 本地随机生成一个私钥 $a$，并计算 $A ≡ g^a \mod p$，将 $A$ 发送给Bob。
Bob 收到 $A$ 后，本地随机生成一个私钥 $b$，并计算 $B ≡ g^b \mod p$，将 $B$ 发送给 Alice。
同时 Bob 计算共享密钥 $K ≡ A^b ≡ g^{ab} \mod p$。
Alice 收到 $B$ 后计算共享密钥 $K ≡ B^a ≡ g^{ab} \mod p$。
最终 Alice 和 Bob 都得到了相同的共享密钥 $K$。以这个 key 作为对称加密算法的密钥，进行后续的通信加密。
DH 密钥交换协议实现 🥰
下面是一个简单的 DH 密钥交换协议的 Python 实现示例：
from sage.all import random_prime, power_mod, randint
# 1. 生成公共参数
bits = 256 # 设置好的位数，生成足够大的素数
upper = pow(2,bits) # 上界
lower = pow(2,bits - 1) # 下界
p = random_prime(upper, lbound = lower) # 生成一个大素数作为模数
g = primitive_root(p) # g 是 p 的原根
# 2. Alice 生成私钥和公钥
a = randint(1, p-1) # Alice 随机生成一个私钥
A = power_mod(g, a, p) # Alice 计算公钥 A = g^a mod p
# 3. Bob 生成私钥和公钥
b = randint(1, p-1) # Bob 随机生成一个私钥
B = power_mod(g, b, p) # Bob 计算公钥 B = g^b mod p
# 4. Alice 和 Bob 计算共享密钥
K_Alice = power_mod(B, a, p) # Alice 计算共享密钥 K = B^a mod p
K_Bob = power_mod(A, b, p) # Bob 计算共享密钥 K = A^b mod p
ECDH 密钥交换协议过程 😋
ECDH（Elliptic Curve Diffie-Hellman）是 DH 密钥交换协议的一个变种，它使用椭圆曲线上的点运算来实现密钥交换。相比于传统的 DH 协议，ECDH 在相同安全级别下可以使用更短的密钥长度，从而提高效率。
ECDH 的过程与 DH 类似，首先通信双方共享一个椭圆曲线参数和一个基点 $G$。
Alice 本地随机生成一个私钥 $a$，并计算公钥 $A = aG$，将 $A$ 发送给 Bob。
Bob 收到 $A$ 后，本地随机生成一个私钥 $b$，并计算公钥 $B = bG$，将 $B$ 发送给 Alice。
同时 Bob 计算共享密钥 $K = bA = b(aG) = abG$。
Alice 收到 $B$ 后计算共享密钥 $K = aB = a(bG) = abG$。
最终 Alice 和 Bob 都得到了相同的共享密钥 $K$，以这个 key 作为对称加密算法的密钥，进行后续的通信加密。
ECDH 密钥交换协议实现 😇
下面是一个简单的 ECDH 密钥交换协议的 Python 实现示例：
from sage.all import EllipticCurve, GF, randint, random_prime
# 1. 初始化 ECC 参数
bits = 160
p = random_prime(2^bits, lbound=2^(bits-1))
while True:
a = randint(1, p-1)
b = randint(1, p-1)
if (4*a**3 + 27*b**2) % p != 0:
break
E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0] # 基点
n = G.order() # 基点的阶
# 2. Alice 生成私钥和公钥
a_private = randint(1, n-1) # Alice 随机生成一个私钥
A_public = a_private * G # Alice 计算公钥 A = aG
# 3. Bob 生成私钥和公钥
b_private = randint(1, n-1) # Bob 随机生成一个私钥
B_public = b_private * G # Bob 计算公钥 B = bG
# 4. Alice 和 Bob 计算共享密钥
K_Alice = a_private * B_public # Alice 计算共享密钥 K = aB = a(bG) = abG
K_Bob = b_private * A_public # Bob 计算共享密钥 K = bA = b(aG) = abG
上一章：加解密模式分析 - 背包加密算法 👈
下一章：加解密模式分析 - OTP 与 PRNG 👈
回到开始：关于我 👈
