奇异三次曲线(尖点)上的 ECDLP 退化:参数化把群运算化为有限域加法
crypto/ecc · verified
一句话结论
曲线 y^2 + c y = x^3 + b x^2 + d x + e 在参数满足 d = 3r^2、e + c^2/4 = -r^3(r = -b/3)时退化为 Y^2 = (x-r)^3 的尖点奇异曲线;用 u = (x-r)/Y(Y = y + c/2)参数化后,群运算变成有限域 F_p 上的普通加法,P = [m]G 可直接由 m = u(P) · u(G)^{-1} mod p 解出,无需任何离散对数算法。
原理
- 配方:令
Y = y + c/2,原方程变为Y^2 = x^3 + b x^2 + d x + (e + c^2/4)。 - 完全立方:取
r = -b/3。若题目参数满足d = 3r^2且e + c^2/4 = -r^3,右边就是x^3 - 3r x^2 + 3r^2 x - r^3 = (x-r)^3。 - 奇异性:曲线
Y^2 = (x-r)^3在(x,Y)=(r,0)处有尖点(cusp),判别式为 0,不是椭圆曲线;其群结构退化。 - 参数化:对非奇异点(
Y != 0)令u = (x-r)/Y。由Y^2 = (x-r)^3得x-r = u^{-2}、Y = u^{-3},即x = r + u^{-2}、y = u^{-3} - c/2。每个非奇异点由唯一的u表示。 - 群运算退化:把参数化代回题目实现的加法公式,可化简为
P(u1) + P(u2) = P(u1 + u2);标量乘法随之变成[m]P(u) = P(m u)。 - 解出标量:
P = [m]G在参数域中即u(P) = m · u(G) mod p,所以m = u(P) · u(G)^{-1} mod p;把m转回字节串即得消息/flag。 - 为什么成立:题目保留了椭圆曲线加法的外观,但曲线本身是奇异的;奇异曲线的非奇异点群同构于加法群(尖点)或乘法群(节点),离散对数不再是困难问题。
触发条件
- 目标使用自定义椭圆曲线,曲线方程为
y^2 + c y = x^3 + b x^2 + d x + e(a=0)或可配方成类似形式。 - 参数满足完全立方/完全平方条件,使判别式为 0(尖点或节点)。
- 攻击者拿到基点
G、公钥/输出点P与模数p,且点非奇异(Y != 0)。 - 曲线定义在素域
F_p上,2、3在p下可逆(用于配方)。
利用步骤
- 计算
r = -b/3 mod p,验证d == 3r^2、e + c^2/4 == -r^3,确认曲线是(x-r)^3型尖点曲线。 - 计算
Y_G = y_G + c/2、Y_P = y_P + c/2;若任一为 0,该点是奇异点,换点或特殊处理。 - 计算
u_G = (x_G - r) · Y_G^{-1} mod p、u_P = (x_P - r) · Y_P^{-1} mod p。 - 计算
m = u_P · u_G^{-1} mod p;把m按大端转字节得到明文。 - 用题目原始
mul(m, G) == P复核,确认参数化与实现一致。
PoC
p = ... # 题目模数
a, b, c, d, e = ... # 曲线参数
G = (xG, yG); P = (xP, yP)
inv = lambda x: pow(x, -1, p)
inv2, inv3, inv4 = inv(2), inv(3), inv(4)
r = (-b * inv3) % p
const = (e + c * c * inv4) % p
assert (-3 * r - b) % p == 0
assert (3 * r * r - d) % p == 0
assert ((-pow(r, 3, p)) - const) % p == 0
def u_map(pt):
x, y = pt
Y = (y + c * inv2) % p
return ((x - r) % p) * inv(Y) % p
m = u_map(P) * inv(u_map(G)) % p
flag = m.to_bytes((m.bit_length() + 7) // 8, "big")
print(flag)
# 例:polarisCTF ECC
# m = u(P)/u(G) mod p
# flag = b'xmctf{A_s1ngu14r_Curv3_15_n0t_s3cur3!}'
变体与关联
- 节点奇异曲线:
Y^2 = x^2(x-r)型节点曲线同构于乘法群F_p^*,离散对数退化为乘法群 DLP;可用类似参数化u = (Y + ...)/(x)处理。 - 其他退化:异常曲线(
#E(F_p)=p)可用 Smart 攻击,见 [[crypto-ecc-anomalous-curve-smart-attack]];小阶/光滑阶曲线可用 Pohlig-Hellman,见 [[crypto-ecc-ecdsa-smooth-order-pohlig-hellman]]。 - 关联:[[crypto-ecc-ecdlp-80bit-prime-order-pollard-rho]](正常曲线的通用 DLP)、[[crypto-ecc-ecdsa-nonce-reuse-private-key-recovery]](ECDSA nonce 复用)。
检测与防御
- 检测:曲线参数使判别式
4a^3 + 27b^2 = 0(或配方后右边为完全立方/平方);自定义曲线未做奇异性检查;公钥点可由简单参数化表示。 - 防御:使用标准曲线(secp256k1、P-256 等);实现前校验判别式非零、基点阶为大素数;不要自创曲线或自定义群运算。
- 加固:对曲线参数做完整性校验;使用成熟库的曲线验证函数;避免在自定义曲线上直接做 ECDH/ECDSA。