BSGS/EXBSGS 离散对数求解:把 x=kp−q 拆成大小步用哈希表在 O(√n) 内解 a^x≡c (mod n),gcd(a,n)≠1 时先约简
ctf/crypto · verified
一句话结论
求解 a^x ≡ c (mod n)(gcd(a,n)=1)时,把指数拆成 x = kp − q,先枚举并缓存"小步" a^q·c,再枚举"大步" (a^k)^p 查表碰撞,就能在 O(√n) 时间与空间内求出 x(取 k=⌈√n⌉);当 gcd(a,n)≠1 时,先用 EXBSGS 反复除以 gcd 把方程约简成互质形式再套 BSGS。
原理
- 方程:
a^x ≡ c (mod n),gcd(a,n)=1保证a在模n下可逆。令x = kp − q,其中0 ≤ q < k、0 < p ≤ ⌈n/k⌉,则x能覆盖[0, n)的全部候选。 - 等式变形:
a^{kp−q} ≡ c两边乘a^q得a^{kp} ≡ a^q·c (mod n)——左边只依赖大步计数p,右边只依赖小步计数q,把"求一个未知指数"变成"两个可枚举序列找相等项"。 - 小步阶段:对
q = 0..k−1计算a^q·c mod n,存入哈希表(键为结果,值为q)。 - 大步阶段:预计算
a^k mod n,对p = 1..⌈n/k⌉计算(a^k)^p mod n,在表中查找;命中则x = kp − q。 - 复杂度与 k 的取值:小步
O(k)次计算与存储、大步最多O(n/k)次计算与查找,总量O(k + n/k);由均值不等式在k = √n时取最小,总复杂度O(√n)(空间也是O(√n))。 - 为什么比穷举强:穷举是
O(n);BSGS 是时间-空间的折中(meet-in-the-middle),把n很大但√n可承受的场景(如n < 2^80)变成可解。 - EXBSGS(
gcd(a,n)≠1):设g = gcd(a,n)。若g ∤ c则无解;否则由a^x ≡ c (mod n)可推出(a/g)·a^{x−1} ≡ c/g (mod n/g),继续对新模数求gcd并重复,直到gcd(a', n') = 1,记录除去的次数x0与累积因子;把约简后的方程用 BSGS 求出y,最终x = y + x0。 - 解的正确性校验:BSGS 可能返回非最小解(同一同余类内可有多个解,尤其 EXBSGS 约简后),得到候选后务必用
pow(a, x, n) == c % n回代验证。
触发条件
- 已知
a、c、模数n(或群阶),需要求指数x。 - 解空间
n使√n的计算与存储在可接受范围(CTF 中常见n ≤ 2^80,视算力而定)。 a与n互质;不互质时可用 EXBSGS 约简(约简后仍要满足 BSGS 可行性)。- 不需要利用模数的结构(对比 Pohlig-Hellman 需要阶的因子全部小)。
利用步骤
- 从题目/协议中确定方程
a^x ≡ c (mod n)与各参数;计算g = gcd(a,n)。 - 若
g ≠ 1:按 EXBSGS 循环——若g ∤ c判无解;否则c ← c/g、n ← n/g、累计x0与因子d ← d·g,直到gcd(a,n)=1;再用累积因子把c修正为c·(a^{x0}/d)^{-1} mod n。 - 取
k = ⌈√n⌉,枚举q = 0..k−1建a^q·c mod n → q哈希表。 - 枚举
p = 1..⌈n/k⌉,计算(a^k)^p mod n查表;命中得x = kp − q(EXBSGS 再加x0)。 - 回代验证
pow(a, x, n) == c % n;不成立时检查约简步骤或扩大p范围(k的取整、p的上界需覆盖n)。
PoC
import math
def bsgs(a, c, n):
assert math.gcd(a, n) == 1, "a and n must be coprime"
k = int(math.ceil(math.sqrt(n)))
table = {}
rv = c % n
for q in range(k): # 小步:a^q * c
table.setdefault(rv, q) # 保留最小 q
rv = (rv * a) % n
ak = pow(a, k, n)
left = 1
for p in range(1, k + 2): # 大步:(a^k)^p
left = (left * ak) % n
if left in table:
x = p * k - table[left]
if pow(a, x, n) == c % n: # 回代校验
return x
return None
print(bsgs(17, 5, 23)) # 19:17^19 mod 23 == 5
def exbsgs(a, c, n):
x0, d = 0, 1
g = math.gcd(a, n)
while g != 1:
if c % g != 0:
return None # 无解
x0 += 1
c //= g
n //= g
d *= g
g = math.gcd(a, n)
# a^{x-x0} ≡ (a^{x0}/d)^{-1} * (c/d) (mod n/d)
coef = pow((pow(a, x0, n) * pow(d, -1, n)) % n, -1, n)
c2 = c * coef % n
y = bsgs(a, c2, n)
return None if y is None else y + x0
x = exbsgs(6, 42, 58)
print(x, pow(6, x, 58)) # 3 42:6^3 mod 58 == 42
注意:不同实现对 p/q 的起始值、k 取整与 EXBSGS 因子修正的处理不同,可能返回同余类里的另一个解;只要回代成立即可作为答案,勿盲目相信脚本注释中的输出。
变体与关联
- ECDLP 上的 BSGS:把群运算换成椭圆曲线点加/标量乘即可,见 [[crypto-ecc-invalid-point-secp256k1-bsgs]];同类密钥小空间场景见 [[crypto-protocol-dh-private-key-partial-bits-mitm-table]](中间相遇建表)。
- 阶光滑时更优:已知群阶且因子都小时用 Pohlig-Hellman 逐因子求解,再 CRT 合并,见 [[crypto-ecc-ecdsa-smooth-order-pohlig-hellman]]、[[ctf-crypto-matrix-group-dlp-determinant-reduce-pohlig-hellman]]。
- 省内存变体:Pollard's rho / kangaroo 用
O(1)空间求O(√n)时间,见 [[crypto-ecc-ecdlp-80bit-prime-order-pollard-rho]]。 - 边界:
n达到密码学规模(大素数群的阶含大素因子)时√n不可行,BSGS 只能用于 CTF 的小空间或参数缺陷场景;EXBSGS 只能处理整除关系,不能突破大群。
检测与防御
- 设计侧(防御 DLP 被 BSGS 打穿):使用阶含 ≥256 位大素因子的群(大素数阶子群、安全素数);避免把私钥/指数限制在小范围或让指数空间暴露;校验生成元阶,避免小子群。
- 审题/利用侧(CTF):看到"指数在小范围""模数不大(如 80 位以内)""可精确构造
a^x"时应优先尝试 BSGS/EXBSGS;先判gcd(a,n)选择 BSGS 还是 EXBSGS,解出后必须回代验证。 - 检测线索:CTF/演练环境之外,进程在本地做大量模幂与哈希表建表(
√n级内存与 CPU)可作为破解 DLP 的行为特征;对实际系统而言,只要群参数合规,BSGS 不构成威胁。