Twisted Hessian 曲线已知点反解参数 d:双有理映射到 Weierstrass 后用 Pohlig–Hellman 求 DLP
crypto/ecc · verified
一句话结论
题目给出 Twisted Hessian 曲线 a·x³ + y³ + 1 = d·x·y 上的若干点而不直接给参数 d 时,可由已知点反解 d = (a·x³ + y³ + 1)/(x·y);再用双有理变换把曲线和点映射到 Weierstrass 形式,对光滑的曲线阶做 Pohlig–Hellman 分解 ECDLP,最后用 CRT 合并各素因子子群的离散对数即可恢复私钥/明文。
原理
- 曲线模型与参数恢复:Twisted Hessian 曲线的射影方程为
a·X³ + Y³ + Z³ = d·X·Y·Z;取仿射坐标Z=1得a·x³ + y³ + 1 = d·x·y。只要知道曲线上一个非退化点(x1,y1)和系数a,就能直接解出d = (a·x1³ + y1³ + 1) · (x1·y1)⁻¹ mod p;不需要暴力搜索。 - 双有理等价:Hessian 曲线与 Weierstrass 曲线
v² + a1·u·v + a3·v = u³ + a2·u² + a4·u + a6之间存在双有理映射。将d代入固定公式得到a1,a2,a3,a4,a6,再把已知点按u = f(x,y)、v = g(x,y)映射过去,得到 Weierstrass 模型上的基点G和目标点Q。双有理映射在除有限个例外点外保持群运算,因此原曲线上的 DLP 等价于 Weierstrass 曲线上的 DLP。 - Pohlig–Hellman:若
#E(F_p) = ∏ q_i^{e_i}的素因子都不大(光滑阶),对每个q_i^{e_i}计算t = n / q_i^{e_i},把G、Q分别乘以t投影到该素因子子群,用discrete_log/BSGS 求出私钥模q_i^{e_i}的余数,最后 CRT 合并得到完整私钥。 - 为什么成立:参数 d 由公开点唯一确定;曲线模型变换保持群结构;阶光滑时 ECDLP 的复杂度从
O(√n)降为各小素因子子问题之和。三者叠加使原本“不可解”的曲线 DLP 变成可计算问题。
触发条件
- 题目给出 Hessian/Edwards/Montgomery 等非 Weierstrass 曲线模型上的点,参数(如
d)未直接给出,但可由已知点方程反解。 - 曲线阶
#E(F_p)可计算且分解后各素因子足够小,discrete_log/BSGS 可在可接受时间内求解。 - 攻击者能使用 SageMath(
EllipticCurve、factor、discrete_log、crt)或等价的 ECC 库。 - 私钥/标量就是最终目标(共享密钥、AES key 派生输入等)。
利用步骤
- 写出曲线方程,代入已知点反解缺失参数。以
a=2的 Twisted Hessian 为例:d = (2*x1**3 + y1**3 + 1) * inverse(x1*y1, p) % p。 - 按该模型的固定双有理变换公式计算 Weierstrass 系数
a1,a2,a3,a4,a6,并映射基点G与目标点Q;检查映射后的点确实满足 Weierstrass 方程。 E = EllipticCurve(GF(p), [a1,a2,a3,a4,a6]),计算n = E.order(),分解n;筛选出可用discrete_log处理的素因子(大因子需 BSGS/题目提示/私钥范围)。- 对每个素因子幂
mod = q**e:t = n // mod,dlog = discrete_log(t*Q, t*G, operation='+'),记录(dlog, mod)。 x = crt(remainders, moduli);若私钥还有未处理的大因子导致多解,结合题目给定范围或额外校验(哈希、AES 明文格式)筛选x + k·L。long_to_bytes(int(x))或按题目要求转成 AES key/共享密钥,完成后续解密。
PoC
# SageMath;参数与点取自题目,映射公式按所选 Hessian 模型固定
p = 10297529403524403127640670200603184608844065065952536889
a = 2
x1, y1 = 8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464
x2, y2 = 6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797
d = (a*x1**3 + y1**3 + 1) * inverse_mod(x1*y1, p) % p
D = a - d**3 / 27
a1 = -3 * (d/3) / D
a2 = -9 * (d/3)**2 / D**2
a3 = -9 / D**2
a4 = -27 * (d/3) / D**3
a6 = -27 / D**4
E = EllipticCurve(GF(p), [a1, a2, a3, a4, a6])
def phi(x, y):
den = d*x/3 + y + 1
u = (-3 / D) * x / den
v = (-9 / D**2) * (-y) / den
return E(u, v)
G, Q = phi(x1, y1), phi(x2, y2)
n = E.order()
moduli, residues = [], []
for q, e in factor(n):
if q > 2**40: # 大因子按题目提示/BSGS 处理,或先跳过
continue
mod = q**e
t = n // mod
residues.append(discrete_log(t*Q, t*G, operation='+'))
moduli.append(mod)
x = crt(residues, moduli)
print(x)
print(bytes.fromhex(hex(int(x))[2:].zfill(2)))
# 该题最终解出的字节串示例:b'e@sy_cuRvL_c0o!'
# 说明:文章脚本中存在位运算/切片转录问题,以上为按 Pohlig-Hellman 标准流程重写的骨架;
# 若存在未处理的大素因子,需要结合题目私钥范围或额外校验枚举 x + k*L。
变体与关联
- 曲线模型变体:Twisted Edwards、Montgomery、Hessian 曲线都有到 Weierstrass 的双有理映射;先找对应公式,再套 PH。
- 参数未知变体:若
a、d都未知,可用多个已知点联立方程(或采样点拟合射影三次曲线)恢复参数,再映射。 - 阶不光滑变体:最大素因子过大时,Pohlig–Hellman 只能求出部分余数;若私钥有范围/低位泄露,用 BSGS/格方法补全;否则需换攻击面。
- 关联卡片:[[crypto-ecc-ecdsa-smooth-order-pohlig-hellman]](光滑阶 PH 基础)、[[crypto-ecc-unknown-curve-projective-cubic-fit-weierstrass-dlp]](未知曲线拟合 + Weierstrass 化)、[[crypto-ecc-twisted-edwards-map-multiplicative-group-dlp]](Edwards 曲线映射到乘法群)、[[crypto-ecc-invalid-point-secp256k1-bsgs]](小范围 ECDLP 的 BSGS)。
- 边界:曲线阶含超大素因子、映射退化点(分母为 0)、或题目未给足够点恢复参数时,本链不成立或只能部分恢复。
检测与防御
- CTF/设计视角:不要使用光滑阶曲线;选择阶含大素因子的标准曲线(如 secp256k1/P-256),并公开参数而不是让攻击者反解。
- 实现视角:曲线参数应由可信标准给出;自定义曲线需验证阶的素因子、嵌入度、异常点(supersingular/anomalous)等安全性质。
- 检测信号:题目给出非 Weierstrass 模型上的点且参数缺失;曲线阶可分解为大量小素数;出现
discrete_log、crt、factor(E.order())等解题特征。 - 取证/审计:遇到自定义 ECC 协议,先恢复曲线参数与群阶,再检查阶是否光滑、是否存在小主子群;不要只验证点是否在曲线上。