♧ Godown 安全知识树

光滑阶素数域离散对数: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 等。

利用步骤

  1. 分解 n-1(或 p-1):factor(n-1),筛出所有小素因子 q_i,剔除无法求解的大因子。
  2. 对每个 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)。
  3. 用 CRT 合并所有小因子余数,得到 x0 与模数 M=∏q_i。
  4. 若 M 不足以确定 x:在已知位数上限内从 x0 开始按 M 递增,验证 pow(g, x, n) == y,命中即 x。
  5. 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 会长时间卡住,需先评估因子分布再手动选择子群。