Dual RSA 共模多模数:构造格同时求解小私钥 d 与各模数 φ
crypto/rsa · verified
一句话结论
Dual RSA 用同一对 (e,d) 对应多个模数 N_i(e·d ≡ 1 mod φ(N_i))。当 d < N^{1/3} 时,可构造格 L=[[A,e,…,e],[0,-N_1,0,…],…],使 (d,k_1,…) 乘格基得到短向量 (A·d, 1-k_1·s_1, …)(s_i=p_i+q_i-1),LLL 约减后即可恢复 d,进而解密所有模数下的密文。
原理
- 同一私钥指数
d用于多个模数:e·d ≡ 1 (mod φ(N_i)),因此存在整数k_i使e·d = 1 + k_i·φ(N_i)。 - 写
φ(N_i) = N_i - s_i,其中s_i = p_i + q_i - 1 ≈ √N_i。于是e·d - k_i·N_i + k_i·s_i = 1,即e·d - k_i·N_i = 1 - k_i·s_i。 - 构造格(两个模数为例):
L = [[A, e, e], [0, -N_1, 0], [0, 0, -N_2]]。 取整数向量(d, k_1, k_2)右乘L,得到(A·d, e·d - k_1·N_1, e·d - k_2·N_2) = (A·d, 1 - k_1·s_1, 1 - k_2·s_2)。 - 选择
A ≈ e/√N(N为单个模数量级),使A·d与k_i·s_i量级平衡。由于k_i ≈ d、s_i ≈ √N,短向量长度约为d·√N;格行列式约为A·∏N_i,LLL 可找到该短向量的条件约为d < N^{1/3}。 - 从约减后的短向量中取出第一分量
A·d,除以A即得d;用pow(pow(m,e,N_i),d,N_i)==m对随机m校验,或直接解密目标密文。 - 模数越多,格维数越高,可容忍的
d上界越接近N^{1/2};当d临近边界时,可用“已知部分 d 高位”的扩展格做小范围爆破(原文图示的第二组矩阵)。
触发条件
- 多个 RSA 模数
N_i共用同一e与同一d(Dual RSA 或多密钥复用私钥)。 d较小,约小于N^{1/3}(两个模数时;更多模数可放宽)。- 攻击者已知各
N_i、e,以及至少一个模数下的密文。 - 能运行 LLL/BKZ;
N_i规模相近时格平衡最好。
利用步骤
- 收集共用
(e,d)的多个模数N_1…N_l,确认e相同且私钥复用。 - 取
A ≈ e / sqrt(N_1)(或各模数的几何平均),构造格: - 第一行(A, e, e, …, e); - 第i+1行第i+1列为-N_i,其余为 0。 - 对格基做 LLL,在约减基中寻找第一分量能被
A整除、且其余分量形如1 - k_i·s_i的短向量。 - 由第一分量求
d = |v_0| / A;用随机m验证pow(pow(m,e,N_i),d,N_i)==m对所有i成立。 - 用
d解密目标密文;若d略大于界,改用部分d高位的扩展格或对低位小范围爆破。
PoC
# Sage 伪代码:两个模数的 Dual RSA 格
N1, N2, e = ...
A = round(e / sqrt(N1)) # 平衡系数
L = Matrix(ZZ, [
[A, e, e],
[0, -N1, 0],
[0, 0, -N2],
])
B = L.LLL()
for row in B:
if row[0] != 0 and abs(row[0]) % A == 0:
d = abs(row[0]) // A
if all(pow(pow(2, e, Ni), d, Ni) == 2 for Ni in (N1, N2)):
print("d =", d)
break
原文只给出格构造图与
d < N^{1/3}的条件,未提供完整可运行 PoC;上式是按其矩阵补全的最小验证框架,实际参数需按模数规模调整。
变体与关联
- 变体:
l个模数时格为(l+1)维,第一行(A,e,…,e),其余为-N_i对角;模数越多,d的上界越高。 - 变体:
d临近边界时,把d拆成已知高位d_h与未知低位d_s,在格中加入ed_h项并小范围爆破d_s。 - 变体:若只是同一明文在多个模数下加密(共模广播),不需要私钥,直接用 CRT/共模攻击。
- 关联:[[crypto-rsa-boneh-durfee-small-private-exponent]](单模数小 d)、[[crypto-rsa-partial-e-coppersmith-hgs-multi-key-small-d]](多密钥 HGS)、[[crypto-rsa-common-modulus]](同模数共模攻击)。
检测与防御
- 防御:每个密钥使用独立模数与独立私钥指数,绝不复用
(e,d)。 - 防御:
d必须足够大(至少n^0.5量级);使用标准库生成密钥并做参数自检。 - 检测:审计多个公钥是否共享相同
e/相同模数结构,检查私钥d的位长是否异常小;CTF 中看到“同一 d 加密多个 N”即可按本卡尝试。 - 响应:确认私钥复用或小
d后,视为所有相关模数失陷,立即轮换全部密钥并审计历史密文。