已知 G 与 2G 反解曲线参数 a(a 即 flag):倍点公式消去 y 得 a 的二次方程求根
crypto/ecc · verified
一句话结论
当题目给出短 Weierstrass 曲线 E: y²=x³+ax+b (mod p) 的 p、b 以及点 G 与 2G 的 x 坐标、而把曲线参数 a 当作 flag(a = bytes_to_long(flag))时,把倍点公式的斜率 λ=(3x₁²+a)/(2y₁) 代入 x₂=λ²−2x₁,并用曲线方程消去 y₁,可得到只含 a 的二次方程 4(x₂+2x₁)(x₁³+a·x₁+b) ≡ (3x₁²+a)² (mod p),在 GF(p) 上求根再 long_to_bytes 即得 flag。
原理
- 椭圆曲线点加/倍点公式(短 Weierstrass):对
P=(x₁,y₁),2P=(x₂,y₂)满足λ=(3x₁²+a)/(2y₁)、x₂=λ²−2x₁(模 p)。 - 题目已知
x₁、x₂、p、b,未知y₁与a。把x₂=λ²−2x₁改写为λ² = x₂+2x₁,两边乘(2y₁)²得4(x₂+2x₁)y₁² = (3x₁²+a)²。 - 再用曲线方程
y₁² = x₁³+a·x₁+b (mod p)消去y₁,得到仅含a的方程:4(x₂+2x₁)(x₁³+a·x₁+b) − (3x₁²+a)² ≡ 0 (mod p),展开是关于a的二次多项式。 - 在
GF(p)上求该二次方程的两个根;a作为 flag 字节串数值通常远小于p且可打印,错误的根一般不可 UTF-8 解码或不符合 flag 格式,据此筛选。 - 为什么可行:倍点关系把
G与2G的 x 坐标绑定到同一a,而曲线方程提供了消去未知 y 的约束;两个方程两个未知量(a、y₁)被化简为单变量多项式,无需解离散对数。
触发条件
- 题目给出
p、b(或等价曲线常量)与同一条曲线上G、2G的 x 坐标。 - 曲线为短 Weierstrass 形式,
a是待求量(可能直接编码 flag)。 - 模数 p 为素数,可在
GF(p)上做多项式求根。 - 有 SageMath 或能解模二次方程的工具。
利用步骤
- 确认
x₂对应的点确实是2G(题面/代码中有G=2*G或x2来自倍点)。 - 在 Sage 中定义
PR.<a> = PolynomialRing(Zmod(p)),构造f = 4*(x2+2*x1)*(x1^3+a*x1+b) - (3*x1^2+a)^2。 roots = f.roots()求根;对每个根r做long_to_bytes(int(r)),筛出可读明文/flag 格式。- 若根不唯一,用
y₁² = x₁³+a·x₁+b验证二次剩余或带回倍点公式复核2G一致。 - 输出 flag。
PoC
# SageMath
from Crypto.Util.number import long_to_bytes
p = 2978504498661002629091299071582436290465904673149953768927904567383228838983804727503168770704927560352042485566736762649409218645007506958368851729754839447148084715613471942096737
b = 203155971939366413053854572390533580854014345966175709774130058801484693709794880904842038444407635302410301870035839686400041986234396869946957773156780151597585571207840328547492
x1 = 2961746450301081157772024536903602376932457486781631924575753810982866784201238112170620297100938460251128698788082874030972104190128685218417680444326891343632886092532386859114448
x2 = 890136530671131957244004062733232817452520380339736536303621498985673475366221669385748542093619285319261702354866398531524362067791067563428973366865229056520602220404939306258451
PR.<a> = PolynomialRing(Zmod(p))
f = 4 * (x2 + 2*x1) * (x1^3 + a*x1 + b) - (3*x1^2 + a)^2
for r, _ in f.roots():
print(long_to_bytes(int(r)))
输出可读 flag{...} 的根即答案。PoC 未在本机执行。
变体与关联
- 变体:若给的是
P、P+Q、2Q等线性组合而非G/2G,可改用点减半/四方程组合恢复(见关联卡)。 - 变体:曲线形式为
y²=x³+b(a=0)时无法用本法求 a,需从其他关系恢复。 - 关联:[[crypto-ecc-unknown-curve-point-halving-recover-flag]](未知 p/b + 点减半)、[[ctf-crypto-ecc-unknown-modulus-gcd-small-key-brute]](gcd 恢复模数)、[[crypto-ecc-recover-plaintext-from-ec-elgamal-known-k]](同篇第二题的 ElGamal 解密)。
检测与防御
- 此为 CTF/密码学分析场景,无传统服务端防御;出题侧若想避免被公式反解,需隐藏至少一个独立约束或使用一般曲线/大参数。
- 实战侧启示:不要把秘密直接编码为公开曲线的参数并与点一起发布;曲线参数与点样本都会泄露代数关系。
- 检测:题目数据同时包含
p、b、x(G)、x(2G)且缺少a时,优先尝试倍点公式消元。