多底数幂 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)。
利用步骤
- 收集
cs_i = i^m mod n,确认底数集合含乘法关系(2、3、4、6 足以构造)。 - 计算
g1 = c0^2 - c2、g2 = c0*c1 - c4,n = gcd(g1, g2);若 gcd 带小因子(如 2),按题面试除。 - 用恢复的
n构造Mod(c0, n)与Mod(2, n),在题目给定的区间(lb, ub)上调用discrete_log_lambda。 - 得到
m后转回字节/按题目规则求 flag。 - 若区间未知,先用位数估计(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的区间必须包含真实值且宽度可控,否则会报错或指数级变慢。