RSA p+1 光滑:Williams p+1 用 Lucas 序列分解 p+1 光滑素数
crypto/rsa · verified
一句话结论
当 RSA 的素数满足 p + 1 光滑(例如 p = 2 * 从固定集合中抽 10 个素数之积 - 1)时,Pollard p-1 会失败,但 Williams p+1 可以用 Lucas 序列 V_M(P, 1) mod N 计算 gcd(V_M - 2, N) 直接分解 N;案例中 M = 2 * 所有候选素数之积,P 从 3 试到 5 即拿到因子。
原理
- Pollard p-1 依赖
p - 1光滑:若p-1 | M,则a^M ≡ 1 (mod p),gcd(a^M - 1, N)得到 p。 - Williams p+1 依赖
p + 1光滑:在二次扩域上使用 Lucas 序列V_k(P, 1),当p + 1 | M时V_M(P, 1) ≡ 2 (mod p),因此gcd(V_M(P,1) - 2, N)得到 p。 - 案例生成逻辑:
p = 2 * prod(sample(sops, k)) - 1,其中sops是 10000 个 50 位素数的排序列表,k=10。因此p + 1 = 2 * 10 个素数之积,一定整除M = 2 * prod(所有 sops)。 - 由于
p - 1没有同样的小素数结构,Pollard p-1 会失败;这正是题目把光滑性放在p+1的原因。 - 计算
V_M(P,1) mod N可用快速 Lucas 序列算法(gmpy2.lucasv_mod),复杂度与模幂相当,不需要展开巨大的 M。
触发条件
- RSA 模数
N = p*q,其中至少一个素数的p + 1是 B-smooth,且 B 在可接受范围内。 - 已知或可构造一个被
p + 1整除的光滑数M(案例直接给出所有候选素数乘积)。 p - 1不光滑,Pollard p-1 无效。- 有
gmpy2/PARI 等支持 Lucas 序列或大数运算的库。
利用步骤
- 从题目附件/生成脚本中提取候选素数集合
sops与参数k,计算M = 2 * prod(sops)(或只取必要的素数子集)。 - 对
P = 3, 4, 5, ...计算V = lucasv_mod(P, 1, M, N)。 - 计算
g = gcd(V - 2, N);若1 < g < N,则g就是p。 - 若所有 P 都失败,检查
M是否漏乘、是否应对p-1改用 Pollard p-1、或扩大候选素数集合。 - 得到
p后计算q = N // p、phi = (p-1)(q-1)、d = e^{-1} mod phi,解密m = c^d mod N。 - 用
long_to_bytes还原明文并校验格式。
PoC
import gmpy2
from Crypto.Util.number import long_to_bytes
ns = {}
exec(open("out.py", "r", encoding="utf-8").read(), ns)
sops, N, c, e = ns["sops"], ns["N"], ns["c"], 65537
M = 2
for r in sops:
M *= r
Nmp, Mmp = gmpy2.mpz(N), gmpy2.mpz(M)
p = None
for P in range(3, 5000):
V = gmpy2.lucasv_mod(P, 1, Mmp, Nmp)
g = int(gmpy2.gcd(V - 2, Nmp))
if 1 < g < N:
p = g
print("found P =", P)
break
assert p is not None
q = N // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, N)
print(long_to_bytes(m).decode())
案例输出:found P = 5,明文为 NepCTF{5m0o7h_m4k3s_w1lliam_gr34t}。
变体与关联
- 变体:只已知
p+1的部分因子时,可用分段/逐步的 Williams p+1,或结合 Pollard rho/ECM。 - 变体:
p-1与p+1都部分光滑时,可先后尝试 Pollard p-1、Williams p+1、ECM。 - 变体:
p+1光滑但M过大时,可只取小于某个界的素数构造M,多次尝试不同上界。 - 关联:[[crypto-rsa-pollard-pminus1-smooth-prime]](p-1 光滑对照)、[[crypto-rsa-nested-smooth-prime-p1-known-factor]](已知因子加速)、[[crypto-rsa-fermat-close-prime-factorization]](近邻素数)。
检测与防御
- 防御:RSA 素数应使用密码学安全随机数生成,确保
p-1与p+1都含有足够大的素因子;优先使用标准库生成的 2048 位以上密钥。 - 防御:避免用“从固定小素数集合抽样相乘 ±1”的方式构造素数;这类结构会被 p-1/p+1 分解直接命中。
- 检测:密钥生成脚本中出现
prod(sample(primes)) ± 1、固定素数表、getPrime(50)等模式;对 N 做 p-1/p+1 光滑性预检。 - 响应:发现弱素数后立即更换密钥对,撤销相关证书/会话,审计历史密文是否可被解密。