CTF3：FaultyCurve

一、题目描述题目提供了一个自定义椭圆曲线上的 ECDH椭圆曲线 Diffie-Hellman实现。服务器给出了曲线参数 p、a、基点 G 的 x 坐标 Gx以及公钥 Q flag * G 的 x 坐标 Qx但故意隐藏了曲线参数 b。关键线索来自 chall.py 中的一段注释# EllipticCurve(GF(p), [a,b]) in sage gives an error for some reason :sob:# Some error in /src/sage/schemes/elliptic_curves but im too nub to figure out why这段注释暗示了核心漏洞Sage 无法用这些参数构造椭圆曲线对象——因为这条曲线的判别式 Δ 0是一条奇异曲线Singular Curve二、核心漏洞分析——奇异曲线与群同构2.1 什么是奇异曲线对于 Weierstrass 形式的椭圆曲线 y² x³ ax b (mod p)判别式为Δ -16(4a³ 27b²)当 Δ ≠ 0 时曲线是非奇异的non-singular构成一个安全的椭圆曲线群其上的离散对数问题ECDLP在计算上不可行。当 Δ 0 时曲线是奇异的singular。奇异曲线上的群结构不再安全它同构于有限域的加法群或乘法群使得 ECDLP 变得容易求解。2.2 两种奇异曲线类型类型条件尖点型 (Cuspidal)二重根 → 同构于 GF(p) 的加法群 (GF(p), )结点型 (Nodal)不同切线 → 同构于 GF(p) 的乘法群 (GF(p)×, ×)对于加法群同构映射为 ψ(x,y) (x - x₀)/yflag ψ(Q) / ψ(G)简单除法。对于乘法群同构映射为 ψ(x,y) (y - m(x-x₀))/(y m(x-x₀))flag log_{ψ(G)}(ψ(Q))离散对数但 Sage 的 discrete_log 可秒解。本题为结点型Nodal需要使用乘法群映射。2.3 为什么不需要 b椭圆曲线点加法公式实际上不依赖参数 b加法只依赖 a 和点的坐标。因此即使题目隐藏了 b我们仍然可以恢复它1. 利用奇异条件 4a³ 27b² ≡ 0 (mod p) 解出 b²2. 利用 Gx 在曲线上即 Gx³ a·Gx b 必须是二次剩余确定 b 的正负号3. 求出奇异点 (x₀, 0)其中 3x₀² a ≡ 0 (mod p)4. 恢复 Gy 和 Qy 坐标5. 应用结点型同构映射在 GF(p)× 中求解离散对数三、攻击步骤步骤 1恢复隐藏的曲线参数 bfrom sage.all import *# 题目给出的参数p 3059506932006842768669313045979965122802573567548630439761719809964279577239571933a 2448848303492708630919982332575904911263442803797664768836842024937962142592572096Gx 3Qx 1461547606525901279892022258912247705593987307619875233742411837094451720970084133Fp GF(p)a Fp(a)Gx Fp(Gx)Qx Fp(Qx)# 利用奇异条件 4a³ 27b² 0inv27 Fp(27)^(-1)b_squared -4 * a^3 * inv27b1 b_squared.sqrt()b2 -b1# 利用 G 在曲线上验证 b 的正负b Nonefor candidate in [b1, b2]:rhs Gx^3 a*Gx candidateif rhs.is_square():b candidatebreakprint(f[] Recovered b {b})步骤 2找到奇异点 (x₀, 0)# 奇异点满足 3x₀² a 0inv3 Fp(3)^(-1)x0_squared -a * inv3x0_1 x0_squared.sqrt()x0_2 -x0_1print(f[] Singular points at x {x0_1}, {x0_2})步骤 3恢复 y 坐标# G 和 Q 的 y 坐标正负两种可能rhs_G Gx^3 a*Gx bGy_pos rhs_G.sqrt()Gy_neg -Gy_posrhs_Q Qx^3 a*Qx bQy_pos rhs_Q.sqrt()Qy_neg -Qy_pos步骤 4构造结点型同构映射在 GF(p)× 中求解 DLPflag Nonefor x0 in [x0_1, x0_2]:# 切线斜率 m √(3x₀)m_sq 3 * x0if not m_sq.is_square():continuem m_sq.sqrt()for slope in [m, -m]:for Gy in [Gy_pos, Gy_neg]:for Qy in [Qy_pos, Qy_neg]:# 同构映射: ψ(P) (y - m(x-x₀)) / (y m(x-x₀))num_G Gy - slope * (Gx - x0)den_G Gy slope * (Gx - x0)num_Q Qy - slope * (Qx - x0)den_Q Qy slope * (Qx - x0)if den_G 0 or den_Q 0:continuepsi_G num_G / den_G # ψ(G) ∈ GF(p)×psi_Q num_Q / den_Q # ψ(Q) ∈ GF(p)×# ψ(Q) ψ(G)^flag in GF(p)×try:flag_candidate discrete_log(psi_Q, psi_G)except (ValueError, ZeroDivisionError):continue# 转换为 bytesflag_bytes int(flag_candidate).to_bytes((int(flag_candidate).bit_length() 7) // 8, big)try:decoded flag_bytes.decode(ascii)if decoded.startswith(wwf{) or decoded.startswith(flag{):flag decodedprint(f\n[] FLAG: {decoded})breakexcept:passif flag:breakif flag:breakif flag:break四、攻击原理总结这道题展示了经典奇异曲线攻击的完整流程核心原理如下1. 判别式为零 → 奇异曲线当 4a³ 27b² 0 mod p 时曲线存在奇点其上的群结构退化与 GF(p) 的加法群或乘法群同构。2. 点加法不依赖 bWeierstrass 曲线的点加法公式只用到 a 和坐标因此即使题目隐藏了 b仍能正确计算群运算。3. 同构映射将 ECDLP 降级为普通 DLP通过 ψ(x,y) 将曲线点映射到 GF(p) 中的元素原本困难的椭圆曲线离散对数问题变成了有限域中的离散对数问题可在数秒内求解。4. 结点型 (Nodal) vs 尖点型 (Cuspidal)结点型曲线同构于乘法群需要调用 discrete_log尖点型同构于加法群仅需一次除法。正常 ECDH奇异曲线攻击ECDLP 在计算上不可行群同构后 DLP 可秒解需要 b 来验证曲线点从奇异条件 4a³27b²0 恢复 b点加法用到 a 和 b点加法只用到 a不依赖 b需要亚指数算法求解Sage discrete_log 数秒内求解五、解题结果Flagwwf{sup3rs1ngul4r_1s0m0rph15ms!}解题时间数秒主要在 SageMath 中完成离散对数计算必需工具SageMath提供 GF(p) 上的离散对数求解六、知识点总结1. 奇异曲线Singular Curve当判别式 Δ 0 时椭圆曲线退化群结构同构于加法群或乘法群ECDLP 不再安全。这是椭圆曲线密码学中最基本的陷阱之一。2. 参数隐藏无效即使题目隐藏了 b通过奇异条件和基点在曲线上的约束b 可以被唯一确定。参数隐藏不能代替密码学安全性。3. 群同构Group Isomorphism这是将困难问题降级为简单问题的核心数学工具。理解群同构对于分析非标准椭圆曲线至关重要。4. SageMath 错误即线索题目注释中Sage 报错是一个巧妙的提示——Sage 的 EllipticCurve 构造函数拒绝构造奇异曲线这本身就是漏洞信号。5. 现实世界对应在 TLS/SSH 等协议中如果实现不验证对方提供的曲线参数攻击者可能诱导协商到一条弱曲线如奇异曲线、异常曲线等上从而破解通信。6. 点验证的重要性椭圆曲线密码实现必须验证所有输入点和曲线参数的有效性包括判别式非零、点在曲线上、点在正确的子群中。