光滑阶素数域离散对数:Pohlig-Hellman 逐因子子群求解 + CRT 合并(DH 私钥恢复)
ctf/crypto · verified
一句话结论
素数域上求解 y = g^x (mod p) 时,只要 p-1 的素因子都较小(光滑阶)或部分光滑,就可以用 Pohlig-Hellman:对每个小因子 q_i 把 g、y 分别升到 (p-1)/q_i 次幂,把问题约化到 q_i 阶子群内求 x mod q_i,再用 CRT 合并;合并结果若位数不足,则在 x 的已知位数范围内按模数递增搜索验证。Sage 的 discrete_log() 在光滑阶时会自动完成换域,可直接解出 DH 私钥。
原理
- DLP 与阶:
y = g^x (mod p);x的范围由g的阶(通常为p-1,g是原根时)决定。若g不是原根,discrete_log需在其阶的子群内求解。 - 光滑阶约化:设
p-1 = p_1^{k_1} p_2^{k_2} ... p_m^{k_m}。对每个质因子p_i,把方程两边升到(p-1)/p_i^r次方:(g^x)^{(p-1)/p_i^r} ≡ y^{(p-1)/p_i^r} (mod p)。 此时左边只与x mod p_i^r有关(因为g的p-1次方为 1,指数按模p_i^r坍缩),问题变成在p_i^r阶子群求离散对数。 - 逐位求系数(Pohlig-Hellman 完整版):对
p_i^{k_i}部分,把x写成p_i进制x = a_0 + a_1 p_i + ... + a_{k_i-1} p_i^{k_i-1} (mod p_i^{k_i}),从r=1开始,每次把方程升到(p-1)/p_i^r次方,除第一项外其余项因欧拉定理全部为 1,从而只需暴力枚举a_{r-1} ∈ [0, p_i-1](复杂度O(p_i)),再进入下一轮;全部系数求出后组合得到x mod p_i^{k_i}。 - CRT 合并:各
p_i^{k_i}两两互素,x mod ∏ p_i^{k_i}由 CRT 唯一确定;若p-1全部光滑,乘积即p-1,x唯一确定。 - 部分光滑时的搜索:若只分解出部分小因子(例如 1024 位素数只拿到 5~6 个小因子),CRT 得到的
x只是模M=∏q_i下的一个值、位数不够;在攻击者已知x的位数上限(如 128 位)时,从x开始按M递增(x + kM)逐个验证pow(g, x+kM, p)==y,只要x < 2^128且M足够大,搜索次数可接受。 - Sage 的便利:
discrete_log(Mod(y,p), Mod(g,p))内部识别阶的分解,自动换域到各p_i^r再 CRT;因此光滑阶题目一行即可解出。但 1024 位素数中只要存在一个超大素因子(如p-1里 300+ 位的因子),该子群无法解,discrete_log会卡住/失败,此时必须手动只取小因子集合,再配合位数搜索。 - DH 场景:已知
A=g^a、B=g^b、p、g,分别解出a、b后k=g^{ab} mod p即共享密钥(或直接k=B^a=A^b)。
触发条件
- 素数
p使p-1光滑或部分光滑(小素因子乘积足够覆盖x的可能范围)。 g为原根或已知阶为光滑数;y位于对应子群。- 若只部分光滑:已知
x的位数范围且不大(相对小因子乘积)。 - CTF 场景常见于自定义 DH、
pow(m, secret, n)、c = m^flag mod n等。
利用步骤
- 分解
n-1(或p-1):factor(n-1),筛出所有小素因子q_i,剔除无法求解的大因子。 - 对每个
q_i:计算h_i = pow(y, (n-1)//q_i, n)、g_i = pow(g, (n-1)//q_i, n),调用discrete_log(Mod(h_i,n), Mod(g_i,n))得到x mod q_i(Sage 自动换域到q_i)。 - 用 CRT 合并所有小因子余数,得到
x0与模数M=∏q_i。 - 若
M不足以确定x:在已知位数上限内从x0开始按M递增,验证pow(g, x, n) == y,命中即x。 - DH/公钥场景:分别解出两个私钥后计算共享密钥/明文。
PoC
from Crypto.Util.number import long_to_bytes
from sage.all import *
n = 89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119974022969989259739901207135911877936187
m = 211060723077960779250044744266141176829
c = 32977205552939587326066964781587345932834856116807593874246357335611184723568494377764636367075033866504466671442418777279691941123340914970584204650416137940499348297233941269700668358058974528742129237158207741614517093787264725738282484698794547919205696467463725584733972956537910246421504887816202122161
def partial_dlog(h, g, N, p, qi):
Zp = Zmod(p)
return int(discrete_log(Zp(pow(h, N // qi, p)), Zp(pow(g, N // qi, p))))
fac = [659, 144811523, 158091863, 167642023, 194814973]
res = [partial_dlog(c, m, n - 1, n, qi) for qi in fac]
x = crt(res, fac)
M = prod(fac)
while int(x).bit_length() <= 128: # 已知明文/私钥位数上限
if int(pow(m, x, n)) == c:
print('x =', x); break
x += M
变体与关联
- 变体:
p-1完全光滑时 CRT 直接得到唯一x,无需搜索(discrete_log一步到位)。 - 变体:
p-1有中等大小因子(约 2^30~2^40)时,子群内离散对数用 BSGS/Pollard rho 而不是暴力。 - 变体:DH 直接用
k = pow(B, a, p)(或pow(A, b, p)),只需要解一个私钥。 - 关联:[[ctf-crypto-bsgs-exbsgs-discrete-log-sqrt-n]](非光滑/大阶离散对数)、[[ctf-crypto-multibase-power-gcd-modulus-lambda-dlp]](小范围 DLP 与模数恢复)、[[crypto-ecc-ecdsa-smooth-order-pohlig-hellman]](ECC 上的同类光滑阶攻击)。
- 边界:
p-1含超大素因子且无法规避时 Pohlig-Hellman 不可行;g的阶未知/非光滑时换域不成立;位数搜索范围过大(如未给位数上限)也不可行。
检测与防御
- CTF 识别:题目给出
p、g、y(或 DH 的 A/B)且p-1可分解为小因子时,优先 Pohlig-Hellman + CRT;1024 位素数只分解出少量小因子时叠加位数搜索。 - 密码设计:素数
p应取安全素数((p-1)/2也为素数)或至少含一个足够大的素因子,使p-1不光滑;DH 参数使用标准组。 - 实现:Sage
discrete_log在光滑阶时自动 Pohlig-Hellman,但对含大因子的p-1会长时间卡住,需先评估因子分布再手动选择子群。