RSA 共模攻击

前置条件

有两把 “公钥”：(n, e1) 和 (n, e2)

注意：n 完全相同，但 e1 与 e2 不同且互质

同一份明文 m，分别用这两把公钥加密，生成了两个密文：

  • c1 = m^e1 mod n

  • c2 = m^e2 mod n

如果只知道 c1, c2, e1, e2, n，没有私钥也能算出 m

贝祖等式

共模攻击完全建立在贝祖等式上

如果两个整数 e1 和 e2 互质，那么存在整数 s 和 t 使得：

1
e1 * s + e2 * t = 1

在 Python 里我们可以直接用 gmpy2.gcdext(e1, e2)，它会返回 (g, s, t)，其中 g=1（因为互质）

攻击思路

如果 e1*s + e2*t = 1 成立，我们构造这样一个组合：

1
2
3
4
c1^s * c2^t  ≡ (m^e1)^s * (m^e2)^t
             ≡ m^(e1*s + e2*t)
             ≡ m^1
             ≡ m (mod n)

也就是说，c1^s1 · c2^s2 mod n 直接就等于我们想要的明文 m

难点——负指数

但是 s 和 t 中一定有一个是负数（因为 e1 和 e2 都是正数，但它们的线性组合要等于 1，只能一个正一个负）

在普通数学中，c1^s1 如果指数是负数，比如 c1^{-3}，就是 1 / (c1^3)

但在模 n 的世界里，没有直接的小数除法，我们用乘法逆元（也叫模逆元）来取代除法

模逆元

举个例子，在模 n 下，a 的逆元是 a^{-1} ，它满足：：

1
a × a^{-1} ≡ 1 (mod n)

例如，n = 7，a = 3：

1
3 × 5 = 15 ≡ 1 (mod 7)

所以 3 的逆元是 5

有了逆元之后，我们就可以定义 “负指数” 了

c1^{-k} 就定义为 (c1^{-1})^k（k 是正数）

也就是先求 c1 的逆元，再把它取 k 次方

解法

设我们算出 s1 < 0, s2 > 0：

    1. 对 s1 取相反数：s1' = -s1
    1. 计算 c1 在模 n 下的乘法逆元 inv_c1，满足 c1 * inv_c1 ≡ 1 (mod n)

经过这一步，原来 c1^s1（带负指数）就等价于 inv_c1 ^ (s1')

步骤图

1
2
3
4
5
6
7
8
9
10
① 提取 n, e1, e2, c1, c2
        ↓
② 扩展欧几里得 → g, s1, s2   (g=1)
        ↓
③ 如果 s1<0：s1 = -s1；c1 = c1的逆元 mod n
  如果 s2<0：s2 = -s2；c2 = c2的逆元 mod n
        ↓
④ m = (c1^s1 mod n) * (c2^s2 mod n)  mod n
        ↓
⑤ 整数 m 转字符串 → flag