♧ Godown 安全知识树

80 位素数阶椭圆曲线离散对数:Pollard rho 并行求解 ECDLP

crypto/ecc · verified

一句话结论

当椭圆曲线的群阶 n 只有 80 位且为素数时,ECDLP 的复杂度是 O(sqrt(n))≈2^40 次群运算;用 Pollard rho(Sage 的 discrete_log_rho)并行搜索即可在数小时到数天内恢复私钥 a,而不是枚举全部 2^80 个标量。

原理

  • ECDLP:给定曲线上的 G 和 Q=aG,求标量 a。通用算法(Pollard rho、BSGS)的复杂度约为 sqrt(n);本题 n 为 80 位,约 2^40 步,现代多核 CPU 可以承受。
  • 题目排除了捷径:曲线是素域 GF(p) 上的非奇异曲线(4A^3+27B^2≠0);n 为素数且 n≠p、n≠p+1。n=p 对应 anomalous curve(Smart 攻击);n≠p 且 n 为素数排除了 Pohlig-Hellman 的小因子分解;n≠p+1 与阶的选取用于避开 MOV/embedding degree 小的情形。因此预期是通用 sqrt(n) 攻击。
  • 为什么用 Pollard rho 而不是 BSGS:BSGS 需要 O(sqrt(n)) 的内存(约 2^40 项,不可行);Pollard rho 只需常数内存,且同一条随机游走可以拆成多段并行(不同起点/不同函数),总期望步数仍约 sqrt(πn/2)。
  • 模约减优化:p 是接近 2^80 的伪梅森素数,x mod p 可以用少量整数乘法和折叠完成;这加快每次群运算,但不改变 O(sqrt(n)) 的复杂度。
  • 可行性边界:单进程通常要几小时到一两天;多进程/多机并行可线性缩短。若 n 是 100 位以上,2^50 步就接近不可行;若 n 有小因子,Pohlig-Hellman 会更快。

触发条件

  • 曲线群阶 n 不够大(本题 80 位),或私钥空间可枚举。
  • n 为素数/无小因子,排除 Pohlig-Hellman;曲线非 anomalous(n≠p)且 embedding degree 不小(排除 MOV)。
  • 已知曲线参数 p/A/B、生成元 G、公钥 Q,且 Q=aG 的 a 是目标(如 flag 的十六进制串)。
  • 有 Sage 或等价 ECC 库,能运行 Pollard rho 并进行多进程/多机并行。
  • 目标环境的群运算速度允许 2^40 量级操作(可用小规模曲线先估速)。

利用步骤

  1. 用 Sage 定义 E = EllipticCurve(GF(p), [A, B]),确认 E.order() == n,检查 n.is_prime()、n != p、n != p+1。
  2. 定义 G = E(Gx, Gy)、Q = E(Qx, Qy),确认 G 的阶为 n(n*G == E(0))。
  3. 调用 discrete_log_rho(Q, G, ord=n, operation='+');也可用 discrete_log(Q, G, ord=n, operation='+') 让 Sage 自动选择算法。
  4. 单进程耗时较长;把随机游走按起点/步进拆分到多进程(或使用 Sage 的并行接口),汇总碰撞结果。
  5. 得到 a 后按题目编码转回字节(本题 a = int(flag[5:-1], 16)),验证 a*G == Q,再按 0xGame{...} 包裹提交。

PoC

p = 1208925819614629174270411
A = 183150304136760995950581
B = 794569627338707454052582
n = 1208925819612932406971299
Gx, Gy = 181528231928396052728802, 1540136182689226613050
Qx, Qy = 339758143822552101710854, 503250777866725616991088

E = EllipticCurve(GF(p), [A, B])
G = E(Gx, Gy)
Q = E(Qx, Qy)
assert n * G == E(0)
a = discrete_log_rho(Q, G, ord=n, operation='+')
print(a)
print(hex(a))
assert a * G == Q

本题解出的 a 对应 0xGame{c9d1bdbf5b83a0742072}。

变体与关联

  • 变体(n 光滑):若 n 有小因子,先用 Pohlig-Hellman 分解到子群,再对每个素因子子群做 Pollard rho/BSGS。
  • 变体(anomalous):若 #E(Fp)=p,用 Smart 攻击(p-adic 椭圆对数)在多项式时间求解。
  • 变体(MOV):若 embedding degree 小,把 ECDLP 映射到 GF(p^k) 的有限域离散对数,再用 index calculus。
  • 变体(实现):并行 Pollard rho 可按随机游走分段;也可用 GPU/多机。BSGS 只适合内存充足的中小群。
  • 关联卡片:[[crypto-rsa-pollard-pminus1-smooth-prime]](Pollard 类算法的另一应用)、[[crypto-rsa-fermat-close-prime-factorization]](数论分解);本卡是 ECC 域的通用离散对数攻击。
  • 边界:n 超过约 100 位、或曲线参数经过加固(大阶素数、非 anomalous、embedding degree 大)时,Pollard rho 不可行;实现错误(如 Sage 版本/operation 参数)会得到错误结果,需用 a*G==Q 校验。

检测与防御

  • 曲线选择:使用至少 256 位群阶的标准曲线(如 P-256、Curve25519);不要自定义 80 位小曲线或短阶曲线。
  • 参数校验:部署前检查 n 的位长、素性、n≠p、embedding degree、是否 anomalous;使用标准曲线库并验证生成元阶。
  • 密钥管理:私钥空间必须足够大;不要把 flag/秘密直接作为小整数私钥。
  • 检测:CTF/审计中看到 p、n 约 80 位、n 为素数且 n≠p,p+1 时,优先尝试 Pollard rho;生产环境监控异常的大量 EC 点乘/离散对数计算没有直接意义,重点在曲线参数合规。