多组 RSA 公钥共用私钥指数 d:LLL 共私钥指数攻击恢复 d 并分解多素数模数
crypto/rsa · verified
一句话结论
当多组 RSA 公钥 (N_i, e_i) 由不同模数但同一个较小私钥指数 d 生成时,有 e_i·d = 1 + k_i·φ(N_i);对 r 素数模数有 φ(N_i)=N_i-s_i、s_i≈N_i^{1-1/r},把 dM 与各 1-k_i·s_i 组成同一个格中的短向量,LLL 约减后即可恢复 d,再用 k_i=e_i·d-1(λ(N_i) 的倍数)做 Miller 型分解拆开每个模数,最终解密所有密文。
原理
- RSA 关键等式:对每个实例
e_i·d = 1 + k_i·φ(N_i),k_i为正整数。所有实例共享同一个d,而e_i各不相同。 - 多素数模数
N_i = ∏ p_j(r 个 512-bit 素数)时,φ(N_i) = ∏(p_j-1) = N_i - s_i,其中s_i是所有一阶项之和(p_1+p_2+…+p_r - 1量级),约为N_i^{1-1/r}。r=3 时s_i ≈ N_i^{2/3},远小于N_i。 - 改写等式:
e_i·d - k_i·N_i = 1 - k_i·s_i。右端1-k_i·s_i与d、s_i同阶,是一个“小量”;这就是格攻击的入口。 - 构造 (t+1) 维格(t 组公钥):前 t 行只有对角元
N_i,最后一行是(e_1, e_2, …, e_t, -M)。取整数向量(k_1, …, k_t, d)右乘该基,得到(k_1N_1 + d·e_1, …, k_tN_t + d·e_t, -dM) = (1-k_1s_1, …, 1-k_ts_t, -dM)。 - 缩放量
M取与N^{1-1/r}同量级(多素数 r=3 时约N^{2/3},实践中取几何平均模数的 2/3 次幂再乘若干小倍数尝试),使前 t 个“小量”和最后一个dM的长度可比;该向量显著短于格中随机向量,LLL 能将其找出。 - 从短向量最后一维取
d = |v_last| / M(符号/倍数偏差需枚举校验);用pow(pow(m,e_i,N_i), d, N_i) == m对随机 m 验证。 - 已知
d后,k_i = e_i·d - 1是λ(N_i)(因而也是φ(N_i)相关量)的倍数。对任意底数a,a^{k_i} ≡ 1 (mod N_i)对所有素数因子成立;把k_i=2^s·u后用 Miller-Rabin 式的平方链gcd(a^{2^j·u}-1, N_i)可概率性拆出因子,多素数模数则递归拆分。 - 为什么成立:复用同一
d让多个独立模数之间产生了共同的短向量结构;模数越多、维数越高,可容忍的d上界越高,接近N^{1/2}。
触发条件
- 多组 RSA 公钥
(N_i, e_i)共享同一个私钥指数d(密钥生成脚本复用d,或“同一口令派生 d”的实现缺陷)。 d相对模数较小(多模数下通常要求d明显小于N,r=3、t=5 的实例中 425-bitd配 1536-bitN即可)。- 攻击者已知全部
N_i、e_i以及至少一个待解密密文。 - 能运行 LLL(fpylll 或 Sage);模数规模相近时格平衡最好。
- 模数为多素数(r≥3)时
s_i更小,攻击条件更宽松,但分解步骤需支持多因子。
利用步骤
- 收集共享
d的多组(N_i, e_i);计算模数几何平均值Nbar,取M0 = Nbar**(1-1/r)(r=3 时Nbar**(2/3))。 - 对
M = M0 × {1,2,3,4,6,8,…}逐个构造 (t+1) 维基:前 t 行第 i 行第 i 列为N_i;最后一行前 t 列为e_i、最后一列为-M。 - 对基做 LLL,按“前 t 维无穷范数”排序候选行;取最后一维能被
M整除的行,令d = |v_last|/M,用(e_i·d-1)的奇偶/可解性做粗筛,再用pow(pow(m,e_i,N_i),d,N_i)==m验证。 - 对每个模数计算
k_i = e_i·d - 1,按k_i = 2^s·u分解,随机取底数a走平方链并用gcd拆因子;未拆开时用 Pollard Rho 兜底,递归直到全部因子为素数。 - 若题目用素数之和等派生量加密(如
sha3_512(str(sum(primes)))[:16]作 AES 密钥),按同一派生规则恢复密钥并解密密文。 - 若 LLL 未直接命中,扩大
M的倍数搜索范围或增加模数数量;仍失败则说明d超出该维数的可恢复界。
PoC
# fpylll 版本:t 组 (N_i, e_i) 共享同一个 d;r=3 多素数模数
from fpylll import IntegerMatrix, LLL
from math import gcd, prod
import random
def recover_d(ns, es, r=3, multipliers=(1,2,3,4,6,8,12,16,24,32)):
t = len(ns)
Nbar = prod(ns) ** (1.0 / t)
M0 = int(Nbar ** (1 - 1.0 / r)) # r=3 时约为 N^(2/3)
for mul in multipliers:
M = M0 * mul
B = IntegerMatrix(t + 1, t + 1)
for i in range(t):
B[i, i] = ns[i]
for j in range(t):
B[t, j] = es[j]
B[t, t] = -M
LLL.reduction(B)
rows = [[int(B[i, j]) for j in range(t + 1)] for i in range(t + 1)]
rows.sort(key=lambda v: max(abs(x) for x in v[:-1]))
for v in rows[:6]:
if v[-1] % M:
continue
d = abs(v[-1]) // M
if d and all(pow(pow(2, es[i], ns[i]), d, ns[i]) == 2 for i in range(t)):
return d
raise RuntimeError("LLL failed; enlarge M multiplier range")
def factor_with_k(N, k, trials=64):
# k 是 lambda(N) 的倍数;Miller 型平方链分解(适用于多素数 N)
s = 0
while k % 2 == 0:
k //= 2; s += 1
def split(n):
for _ in range(trials):
a = random.randrange(2, n - 1)
x = pow(a, k, n)
if x in (1, n - 1):
continue
for _ in range(s):
y = pow(x, 2, n)
if y == 1:
g = gcd(x - 1, n)
if 1 < g < n:
return g, n // g
break
if y == n - 1:
break
x = y
return None
out, stack = [], [N]
while stack:
cur = stack.pop()
if is_probable_prime(cur):
out.append(cur); continue
part = split(cur)
if part:
stack.extend(part)
else:
g = pollard_rho(cur)
stack.extend([g, cur // g])
return sorted(out)
d = recover_d(ns, es)
all_primes = [factor_with_k(N, e * d - 1) for N, e in zip(ns, es)]
# 之后按题目的密钥派生规则(如 sha3_512(str(sum(所有素数))))解密密文
上述 recover_d/factor_with_k 为核心逻辑;is_probable_prime 与 pollard_rho 为标准辅助函数,按需补全。
变体与关联
- 变体:所有公钥共用同一个
e且模数不同、共享d时属于 Dual RSA 的格构造(第一行(A,e,…,e)),本卡的基是它的转置形式,对应不同的e_i。 - 变体:模数为两个素数时
s_i=p_i+q_i,φ=N-s,同样代入;r 越大s相对模数越小,短向量越明显。 - 变体:
d略超界时,把d拆成已知高位与未知低位,在格中加入e_i·d_hi项并对低位小范围枚举。 - 关联:[[crypto-rsa-dual-rsa-lattice-small-d]](同
e多模数 Dual RSA)、[[crypto-rsa-wiener-small-private-exponent-large-e]](单模数小 d)、[[crypto-rsa-boneh-durfee-small-private-exponent]](单模数 Boneh-Durfee)、[[crypto-rsa-partial-e-coppersmith-hgs-multi-key-small-d]](同模数多密钥 HGS)。
检测与防御
- 防御:每次密钥生成使用独立随机私钥指数
d,绝不在多个模数间复用;使用标准库生成密钥并校验d的位长与φ的关系。 - 防御:私钥指数必须足够大(通常与模数同阶),避免为了性能使用固定的较小
d;多素数 RSA 需额外校验各素数独立随机。 - 检测:审计多个公钥是否共享相同
d(可用pow(pow(2,e_i,N_i),d,N_i)对已知/疑似d交叉验证);检查e_i是否由同一d派生、d位长是否异常小。 - 响应:确认
d复用或泄露后,视为所有相关模数全部失陷,立即轮换全部密钥并评估历史密文。