椭圆曲线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 点加法
椭圆曲线上的点加法运算遵循以下规则：
- 单位元：P + ∞ = P
- 逆元：P + (-P) = ∞
- 点加倍：P + P = 2P
- 不同点相加：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 协议步骤
- 双方约定使用相同的椭圆曲线参数和基点G
- Alice生成私钥a，计算公钥A = a*G
- Bob生成私钥b，计算公钥B = b*G
- Alice计算共享密钥S = a*B
- Bob计算共享密钥S = b*A
- 由于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()