在密码学入门中椭圆曲线密码ECC以其更短的密钥长度和更高的安全性备受青睐。而椭圆曲线 Diffie-HellmanECDH则是 ECC 最经典的应用之一它允许双方在不安全的信道上协商出一个共享秘密。最近在解决 CryptoHack 的一道题目时我完整地走了一遍 ECDH 的计算流程今天就把解题思路和代码实现分享出来。一、背景知识1. 椭圆曲线与 ECDLP我们定义有限域 FpFp​ 上的椭圆曲线E:y2x3axb(modp)E:y2x3axb(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​[nA​nB​]G[nB​]QA​所以双方得到了相同的共享秘密 SS。二、题目分析题目给出了具体的曲线参数E:y2x3497x1768(mod9739)E:y2x3497x1768(mod9739)基点为G(1804,5368)G(1804,5368)Alice 的公钥为QA(815,3190)QA​(815,3190)Bob 的私钥为nB1829nB​1829我们的任务计算共享秘密 S[nB]QAS[nB​]QA​然后取 SS 的 x 坐标整数对其十进制字符串表示计算 SHA-1 哈希将十六进制摘要作为最终的 flag。注意题目特意选用了很小的素数 p9739p9739目的是让计算过程可以在可接受的时间内手工或脚本完成而真实场景中 p 至少是 256 位。三、解题步骤1. 实现椭圆曲线上的点运算我们需要在模 pp 下完成点加两个不同点相加倍点点与自身相加标量乘法利用二进制展开法通过倍点与加法实现2. 计算标量乘法利用二进制展开法将 nB1829nB​1829 写成二进制182910245122563241182910245122563241即二进制为11100100101。我们依次计算 QA,2QA,4QA,…,1024QAQA​,2QA​,4QA​,…,1024QA​然后根据二进制位选择相加最终得到 S1829⋅QAS1829⋅QA​。3. 计算 SHA-1取得 SS 的 x 坐标整数值转换为字符串例如str(x)然后计算pythonhashlib.sha1(str(x).encode()).hexdigest()得到的十六进制串即为 flag。四、Python 实现下面是完整的实现代码注释详细可直接运行。pythonimport 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 有更直观的认识。