椭圆曲线 Diffie-Hellman 密钥交换解题思路
在密码学入门中，椭圆曲线密码（ECC）以其更短的密钥长度和更高的安全性备受青睐。而椭圆曲线 Diffie-Hellman（ECDH）则是 ECC 最经典的应用之一，它允许双方在不安全的信道上协商出一个共享秘密。最近在解决 CryptoHack 的一道题目时，我完整地走了一遍 ECDH 的计算流程，今天就把解题思路和代码实现分享出来。
一、背景知识
1. 椭圆曲线与 ECDLP
我们定义有限域 FpFp 上的椭圆曲线：
E:y2=x3+ax+b(modp)E:y2=x3+ax+b(modp)
椭圆曲线上的点构成一个加法群，其中“加法”定义为几何中的点加运算。给定一个基点 GG，标量乘法 [n]G[n]G 表示将 GG 自加 nn 次。
椭圆曲线离散对数问题（ECDLP）就是：已知 GG 和 Q=[n]GQ=[n]G，求 nn。在安全的曲线上，这个问题目前没有亚指数时间的解法，因此被广泛应用于密码学。
2. ECDH 密钥交换流程
双方选定一条曲线 EE、一个大素数 pp 和一个基点 GG（阶为 qq）。
Alice 生成私钥 nAnA，计算公钥 QA=[nA]GQA=[nA]G，将 QAQA 发送给 Bob。
Bob 生成私钥 nBnB，计算公钥 QB=[nB]GQB=[nB]G，将 QBQB 发送给 Alice。
Alice 计算 S=[nA]QBS=[nA]QB，Bob 计算 S=[nB]QAS=[nB]QA。
因为标量乘法的结合性，[nA]QB=[nAnB]G=[nB]QA[nA]QB=[nAnB]G=[nB]QA，所以双方得到了相同的共享秘密 SS。
二、题目分析
题目给出了具体的曲线参数：
E:y2=x3+497x+1768(mod9739)E:y2=x3+497x+1768(mod9739)
基点为：
G=(1804,5368)G=(1804,5368)
Alice 的公钥为：
QA=(815,3190)QA=(815,3190)
Bob 的私钥为：
nB=1829nB=1829
我们的任务：计算共享秘密 S=[nB]QAS=[nB]QA，然后取 SS 的 x 坐标（整数），对其十进制字符串表示计算 SHA-1 哈希，将十六进制摘要作为最终的 flag。
注意：题目特意选用了很小的素数 p=9739p=9739，目的是让计算过程可以在可接受的时间内手工或脚本完成，而真实场景中 p 至少是 256 位。
三、解题步骤
1. 实现椭圆曲线上的点运算
我们需要在模 pp 下完成：
点加（两个不同点相加）
倍点（点与自身相加）
标量乘法（利用二进制展开法，通过倍点与加法实现）
2. 计算标量乘法
利用二进制展开法，将 nB=1829nB=1829 写成二进制：
1829=1024+512+256+32+4+11829=1024+512+256+32+4+1
即二进制为11100100101。我们依次计算 QA,2QA,4QA,…,1024QAQA,2QA,4QA,…,1024QA，然后根据二进制位选择相加，最终得到 S=1829⋅QAS=1829⋅QA。
3. 计算 SHA-1
取得 SS 的 x 坐标（整数值），转换为字符串（例如str(x)），然后计算：
python
hashlib.sha1(str(x).encode()).hexdigest()
得到的十六进制串即为 flag。
四、Python 实现
下面是完整的实现代码，注释详细，可直接运行。
python
import hashlib # 曲线参数 p = 9739 a = 497 b = 1768 def mod_inv(x): """模 p 下的逆元 (Python 3.8+ 支持 pow(x, -1, p))""" return pow(x, -1, p) def point_add(P, Q): """ 椭圆曲线上的点加法 (仿射坐标) P, Q 均为元组 (x, y) 或 None (表示无穷远点) """ if P is None: return Q if Q is None: return P x1, y1 = P x2, y2 = Q # 处理 P 和 Q 关于 x 轴对称的情况 (P + Q = O) if x1 == x2 and (y1 + y2) % p == 0: return None # 计算斜率 m if P == Q: # 倍点公式 m = (3 * x1 * x1 + a) * mod_inv(2 * y1) % p else: # 不同点相加 m = (y2 - y1) * mod_inv(x2 - x1) % p # 计算新点坐标 x3 = (m * m - x1 - x2) % p y3 = (m * (x1 - x3) - y1) % p return (x3, y3) def scalar_mul(k, P): """ 标量乘法: 计算 k * P (使用二进制展开法) """ R = None # 初始化为无穷远点 base = P while k: if k & 1: R = point_add(R, base) base = point_add(base, base) k >>= 1 return R # 已知参数 G = (1804, 5368) # 基点 Q_A = (815, 3190) # Alice 的公钥 n_B = 1829 # Bob 的私钥 # 计算共享秘密 S = n_B * Q_A S = scalar_mul(n_B, Q_A) # 取 x 坐标 shared_x = S[0] # 计算 SHA-1 并输出十六进制 flag = hashlib.sha1(str(shared_x).encode()).hexdigest() print("共享秘密的 x 坐标:", shared_x) print("FLAG:", flag)运行上述代码，即可得到最终的 flag。
（由于我无法在此处运行，请读者自行验证，输出结果即为题目所求。）
五、验证与思考
验证点是否在曲线上：可以检查 GG 和 QAQA 是否满足曲线方程，确保题目数据正确。
为什么不用解 ECDLP：我们不需要求 Alice 的私钥，因为 Bob 直接用自己的私钥乘以 Alice 的公钥即可得到共享秘密，这正是 ECDH 的设计巧妙之处。
安全性反思：本题目中 pp 很小，实际上完全不安全，但为了教学目的，它让我们能够亲手实现所有底层运算，从而对 ECC 有更直观的认识。