♧ Godown 安全知识树

多底数幂 GCD 消元恢复模数 + discrete_log_lambda 小范围离散对数

ctf/crypto · verified

一句话结论

当题目给出同一未知指数 m 在多个小底数下的幂 cs=[2^m, 3^m, 4^m, 5^m, 6^m] mod n 而模数 n 未知时,利用底数间的乘法关系构造两条 n 的倍数(2^{2m}-4^m 与 2^m·3^m-6^m),取 gcd 即可恢复 n;随后用 discrete_log_lambda 在已知的小范围(如 m 为 47 位、约 10^14)内以 O(sqrt(ub-lb)) 解出 m。

原理

  • 题目结构:m 是 47 位明文(pow(i, m, n),i ∈ {2,3,4,5,6}),n = p*q(512+512 位)未知。c_0=2^m、c_1=3^m、c_2=4^m、c_4=6^m。
  • 构造 n 的倍数:c_0^2 - c_2 = 2^{2m} - 4^m ≡ 0 (mod n);c_0 * c_1 - c_4 = 2^m·3^m - 6^m ≡ 0 (mod n)。两者都是 n 的倍数,gcd(c_0^2-c_2, c_0·c_1-c_4) 得到 n(实际可能带小因子,如 //2 去掉公因子)。
  • 恢复 n 后变小范围 DLP:n 为 1024 位,直接 discrete_log 不可解;但已知 m 只有 47 位(≈10^14),且题目/代码泄露了范围,可用 Pollard Lambda(discrete_log_lambda,区间版 Pollard rho)在 [lb, ub] 内求解。
  • Pollard Lambda 复杂度:时间 O(sqrt(ub-lb))、空间 O(log(ub-lb));2^46 ≈ 10^13、2^48 ≈ 10^15,对 10^14 级区间约 10^7 步,可在 CTF 时长内完成。区间给错(如 10^309~10^310)会超范围报错/永远跑不完。
  • 为什么成立:指数相同、底数存在乘除关系时,任意两条幂之间的多项式关系都携带 n 的倍数信息;gcd 把未知模数“消”出来。之后问题从“大素数模下的 DLP”降级为“已知区间的小 DLP”。

触发条件

  • 同一未知指数在多个小底数下的幂可获取,底数之间存在乘法关系(如 4=2²、6=2·3)。
  • 模数 n 未知但可从幂关系恢复(至少两条独立的 n 的倍数)。
  • m 的可搜索范围已知且相对小(如 47~50 位,sqrt 后为 10^7 级)。
  • 可调用 Sage 的 discrete_log_lambda(或自行实现区间 Pollard rho)。

利用步骤

  1. 收集 cs_i = i^m mod n,确认底数集合含乘法关系(2、3、4、6 足以构造)。
  2. 计算 g1 = c0^2 - c2、g2 = c0*c1 - c4,n = gcd(g1, g2);若 gcd 带小因子(如 2),按题面试除。
  3. 用恢复的 n 构造 Mod(c0, n) 与 Mod(2, n),在题目给定的区间 (lb, ub) 上调用 discrete_log_lambda。
  4. 得到 m 后转回字节/按题目规则求 flag。
  5. 若区间未知,先用位数估计(47 位 → 2^46~2^48)再逐步扩大;不要给超大区间。

PoC

from Crypto.Util.number import *
from gmpy2 import gcd
from sage.all import *

out = [183098212086317720236828757315510192339273033804875740822801041376722387458993552796227899411901966324318366514880536763913315608412750265815750386810801443666072579873995967676472994916617708760086271155827496223499121301339946900578686321571238854410077055150282805741312173826325669295346629270100887114, 57033027040944100515577298747833062983449034346155581535109171399667991971614122726451624246276583123688811765412755210627513537740891720491136798691017567675611749056264437247135506921747135448387155606513983563110678466501221603978172670533058510913876368172674768929417846635764813733749021238273031358064, 44177513422937659688192503808032734159830361147993789424022745838993946766432456884886189398779755202878679629523667923807343226973440318127947558457476925179848208108399587026072741947465486816791306581859876197942191253278120326733144030253277598039138046967591357892542649422324554104602547660747339872074, 12631302718057472129138289484187738038805661685759196779990368768599115569927115234126312113575785471158626604808250556471019475882601443785660157133230999298014824293609691681149195181799904358979944719852988436666306120350671288382565369084160416022015445829639878167524217607450918100132212115997395372780, 42899381454706854217031716361682990989382003331688973566655317536112884234898037025883907894505663567670829738793956574655657437562098921910867502135260835097785409348930680677890714703165271668372795217905436049326872168290466249129739381681341323649536725632009485619857375114283009023943744880775769510652]

n = gcd(out[0]*out[1] - out[4], out[0]**2 - out[2]) // 2
x = discrete_log_lambda(mod(out[0], n), mod(2, n), (ZZ(10**14), ZZ(10**15)))
print(long_to_bytes(x))

变体与关联

  • 变体:只要底数有乘除关系就能构造(如 5^m · 3^m - 15^m、2^{2m}-4^m);幂关系不一定是平方,任意线性组合后同为 n 的倍数即可。
  • 变体:若 m 范围未知,先用 m 的位数/明文格式约束估计区间;也可对多个区间分段执行 lambda。
  • 变体:n 已知且 m 范围小(如 4~6 位)时同样用 discrete_log_lambda;无范围时退回 BSGS/Pohlig-Hellman。
  • 关联:[[ctf-crypto-bsgs-exbsgs-discrete-log-sqrt-n]](无区间/大阶 DLP)、[[ctf-crypto-pohlig-hellman-smooth-order-prime-dlp]](光滑阶 DLP)、[[ctf-crypto-small-discrete-log-crt-channel-selection]](小模数 DL + CRT)。
  • 边界:底数之间不存在乘法关系、m 范围过大或被隐藏、n 为素数且底数无关系时不成立;区间给错(过宽)会让 lambda 超范围/超时。

检测与防御

  • CTF 识别:多个小底数的同指数幂 + 模数未知 → 先用 gcd 构造关系求 n;已知指数范围较小 → discrete_log_lambda。
  • 密码设计:不要复用同一秘密指数生成多个可关联的幂;模数保密不构成安全边界;指数空间应足够大、避免可搜索区间。
  • 实现:discrete_log_lambda 的区间必须包含真实值且宽度可控,否则会报错或指数级变慢。