RSA 素数 p-1 光滑:Pollard p-1 在 B=100000 内用 gcd(2^L-1,N) 取因子
crypto/rsa · verified
一句话结论
若 RSA 的某个素数 p 满足 p-1 是 B-光滑的(所有素因子都不超过 B),取 L 为 1..B 的最小公倍数,则 2^L ≡ 1 (mod p),gcd(2^L-1, N) 直接给出 p;本题 B=100000 时枚举到素数 15767 即取出 512 位因子。
原理
- Pollard p-1 利用费马小定理:若
p-1 | L,则对任意与 p 互素的 a 有a^L ≡ 1 (mod p),即p | a^L-1。 - 取
L = lcm(1,2,...,B)(实现上等价于把所有不超过 B 的素数幂乘起来),只要 p-1 的所有素因子都不超过 B(B-光滑),就有p-1 | L。 - 令
a=2,计算a^L mod N;由于N=pq,gcd(a^L-1, N)会包含 p(可能还包含 q,若 q-1 也光滑)。若结果落在 (1,N) 即得到非平凡因子。 - 实际实现不必一次算完 L:从小到大枚举素数 p_i,把 a 反复自乘到
p_i^k ≤ B的最大幂,每步后检查gcd(a-1,N);一旦 p-1 的所有因子都被覆盖,gcd 就会命中。 - 安全性前提是 p-1 有大素因子,使 B 需要大到计算不可行。本题 p-1 完全 B-光滑,B=100000 即可;原文在枚举到素数 15767 时取出 512 bit 因子,说明 p-1 的最大素因子不超过该量级。
触发条件
- RSA 素数生成时只保证 p 是素数,未检查 p-1 是否有大素因子(非 safe prime)。
- p-1 的最大素因子小于攻击者可承受的 B(本题 100000)。
- 攻击者能拿到 N;e、c 正常公开。
- 有足够的计算资源做 B 次模幂/素数枚举(本题规模很小)。
利用步骤
- 对 N 运行 Pollard p-1,B 从较小值(如 10^4、10^5)开始;每步枚举素数幂并更新
a,检查gcd(a-1,N)。 - 命中非平凡因子 g 后,令 p=g、q=N//g,验证 p*q==N 且均为素数。
- 计算
phi=(p-1)(q-1)、d=e^{-1} mod phi,解密密文。 - 若小 B 失败,增大 B 或改用 Pollard rho/ECM;对每个新连接重新读取 N/e/c,不能硬编码某次参数。
PoC
import math
def primes_upto(n):
sieve = bytearray(b"\x01") * (n + 1)
sieve[:2] = b"\x00\x00"
for i in range(2, int(n ** 0.5) + 1):
if sieve[i]:
sieve[i*i::i] = b"\x00" * len(sieve[i*i::i])
return [i for i in range(n + 1) if sieve[i]]
def pollard_pm1(n, bound=100000):
a = 2
for p in primes_upto(bound):
pk = p
while pk * p <= bound:
pk *= p
a = pow(a, pk, n)
g = math.gcd(a - 1, n)
if 1 < g < n:
return g
return None
g = pollard_pm1(N, 100000)
p, q = g, N // g
phi = (p - 1) * (q - 1)
m = pow(c, pow(e, -1, phi), N)
print(m.to_bytes((m.bit_length() + 7) // 8, "big"))
# 服务端每次连接重新生成密钥时,从 socket 实时解析 N/e/c
N, e, c = parse_rsa_params(recv_until(b"c = "))
变体与关联
- 变体:p+1 光滑可用 Williams p+1;p-1 有大素因子但整体较小可用 ECM;两个素数共享部分比特可用 Coppersmith。
- 变体:B 的选择可自适应(先 10^4,再 10^5、10^6),或对每个素数幂检查 gcd 以尽早命中。
- 关联:[[crypto-rsa-pell-equation-prime-generation]](生成规律导致弱素数)、[[crypto-rsa-multiprime-partial-key-coppersmith]](部分密钥泄露)。
- 边界:p-1 含大素因子时 Pollard p-1 失效;B 过大计算量爆炸;N 位数过大时模幂仍可行但素数枚举成为瓶颈。
检测与防御
- 检测:密钥生成代码是否只调用
next_prime/generate_prime而未检查 p-1 的因子;对公钥做 p-1 光滑性预检(小 B 试除);监控异常短的密钥生成时间。 - 修复:使用安全素数(p=2q+1,q 为素数)或确保 p-1 含足够大的素因子;使用成熟库生成 RSA 密钥;密钥生成后做自检。
- 加固:定期轮换密钥;对高价值密钥使用 HSM/安全随机源;避免自写素数生成器;对导出公钥做弱密钥扫描。