RSA 低指数广播攻击

攻击背景

当同一份明文消息 m 使用 相同的低加密指数 e（例如 e = 3 或 e = 5）

但不同的模数 N1, N2, ... , Nk 分别加密并发送给 k 个接收者时，攻击者如果能截获至少 e 个密文，就可以在不分解任何模数的情况下恢复出明文

该攻击属于 Hastad 广播攻击的一个特例（无随机填充时）

数学原理

以 e = 3 为例

加密过程

1
2
3
c1 = m^3 mod N1
c2 = m^3 mod N2
c3 = m^3 mod N3

因为 N1, N2, N3 两两互质，我们可以使用中国剩余定理（CRT） 求解同余方程组

1
2
3
x ≡ c1 (mod N1)
x ≡ c2 (mod N2)
x ≡ c3 (mod N3)

CRT 给出唯一解 x 在模 N1 * N2 * N3 下的值

由同余式可知

1
2
3
x ≡ m^3 (mod N1)
x ≡ m^3 (mod N2)
x ≡ m^3 (mod N3)

由于 m^3 同时满足这三个同余式，且解在 [0, N1*N2*N3) 内唯一，因此一定有

1
x = m^3   （在整数意义上，而非仅仅是模意义下）

因为 m < N_i 对 i=1,2,3 成立，所以 m^3 < N1 * N2 * N3

而 CRT 给出的解 x 满足 0 ≤ x < N1*N2*N3，所以 x 必然等于整数 m^3

最后，攻击者只需在整数上对 x 开立方根即可恢复明文

推广到任意 e

假设攻击者获得了 k 个密文，其中 k ≥ e，对应模数 N1, N2, ..., Nk（两两互质）

CRT 给出唯一解 x 满足

1
x ≡ m^e (mod N_i)   对所有 i = 1..k

因为 m < N_i，所以 m^e < N1 * N2 * ... * Nk（乘积至少包含 e 个因子，每个大于 m）

因此整数 x 恰好等于 m^e，直接开 e 次方根即得 m

实战案例

Quick Math（低指数广播攻击）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from math import prod, gcd

# 给定的 RSA 模数与密文（已知 e=3 的广播攻击场景）
n1 = 86812553978993
n2 = 81744303091421
n3 = 83695120256591

c1 = 8875674977048
c2 = 70744354709710
c3 = 29146719498409

ns = [n1, n2, n3]
cs = [c1, c2, c3]

# 检查模数两两互素，确保 CRT 可行
for i in range(len(ns)):
    for j in range(i):
        print(gcd(ns[i], ns[j]))  # 输出应为 1

# ---------- 中国剩余定理 (CRT) ----------
N = prod(ns)  # 所有模数的乘积
x = 0

for c, n in zip(cs, ns):
    Ni = N // n                # 除当前模数外的其他模数乘积
    inv = pow(Ni, -1, n)      # 计算 Ni 在模 n 下的逆元（Python 3.8+ 支持）
    x += c * Ni * inv          # 累加加权值

x %= N  # 得到 x ≡ m^3 (mod N) 的最小非负解，且因为 m^3 < N，整数意义上 x = m^3

# 整数三次方根（二分查找，适用于大整数）
def iroot3(num):
    l, r = 0, num
    while l <= r:
        mid = (l + r) // 2
        v = mid ** 3
        if v == num:
            return mid
        elif v < num:
            l = mid + 1
        else:
            r = mid - 1
    return r  # 若未精确匹配，向下取整（这里必定精确匹配）

m = iroot3(x)  # 恢复出明文

print("m =", m)
print("check:", m ** 3 == x)  # 验证是否成功