椭圆曲线Diffie-Hellman密钥交换(ECDH)

椭圆曲线Diffie-Hellman密钥交换(ECDH)实现详解

概论参考：https://www.cnblogs.com/luminescence/p/18932875

1. 椭圆曲线基础

1.1 椭圆曲线方程

椭圆曲线由以下方程定义：

y² = x³ + ax + b (mod p)

其中：

• a和b是曲线参数
• p是一个大素数
• 所有运算都在模p下进行

1.2 椭圆曲线上的点

Point类表示椭圆曲线上的点：

class Point:def __init__(self, x: int = None, y: int = None):self.x = xself.y = ydef is_infinity(self) -> bool:return self.x is None and self.y is None

特殊点无穷远点表示群运算的单位元

2. 椭圆曲线运算

2.1 点加法

椭圆曲线上的点加法运算遵循以下规则：

1. 单位元：P + ∞ = P
2. 逆元：P + (-P) = ∞
3. 点加倍：P + P = 2P
4. 不同点相加：P + Q = R
   代码实现：

def add(self, p1: Point, p2: Point) -> Point:if p1.is_infinity():return p2if p2.is_infinity():return p1# P + (-P) = 无穷远点if p1.x == p2.x and p1.y != p2.y:return self.infinity# 点加倍 P + Pif p1 == p2:if p1.y == 0:return self.infinitynumerator = (3 * p1.x * p1.x + self.a) % self.pdenominator = (2 * p1.y) % self.plam = (numerator * self.mod_inverse(denominator, self.p)) % self.pelse:# P + Qnumerator = (p2.y - p1.y) % self.pdenominator = (p2.x - p1.x) % self.plam = (numerator * self.mod_inverse(denominator, self.p)) % self.px3 = (lam * lam - p1.x - p2.x) % self.py3 = (lam * (p1.x - x3) - p1.y) % self.preturn Point(x3, y3)

2.2 标量乘法

标量乘法k*P使用"双倍-加"算法实现：

def multiply(self, k: int, point: Point) -> Point:if k == 0:return self.infinityif k < 0:raise ValueError("k 必须为正整数")result = self.infinityaddend = pointwhile k:if k & 1:result = self.add(result, addend)addend = self.add(addend, addend)k >>= 1return result

3. ECDH密钥交换协议

3.1 协议步骤

1. 双方约定使用相同的椭圆曲线参数和基点G
2. Alice生成私钥a，计算公钥A = a*G
3. Bob生成私钥b，计算公钥B = b*G
4. Alice计算共享密钥S = a*B
5. Bob计算共享密钥S = b*A
6. 由于aB = a(bG) = b(aG) = bA，双方得到相同的共享密钥

3.2 实现

class ECDH:def __init__(self, curve: EllipticCurve, base_point: Point):self.curve = curveself.base_point = base_pointif not curve.is_on_curve(base_point):raise ValueError("基点不在曲线上")def generate_private_key(self, bits: int = 256) -> int:"""生成私钥"""return secrets.randbelow(2**bits - 1) + 1def compute_public_key(self, private_key: int) -> Point:"""计算公钥"""return self.curve.multiply(private_key, self.base_point)def compute_shared_secret(self, private_key: int, peer_public_key: Point) -> bytes:"""计算共享密钥"""shared_point = self.curve.multiply(private_key, peer_public_key)if shared_point.is_infinity():raise ValueError("共享密钥计算失败")shared_bytes = shared_point.x.to_bytes((shared_point.x.bit_length() + 7) // 8, 'big')return hashlib.sha256(shared_bytes).digest()