RSA 作为最广泛使用的非对称加密算法，其安全性基于大整数分解的困难性。然而在实际应用中，由于参数选择不当或实现错误，存在多种攻击方法。本文系统性地介绍 RSA 的各种攻击类型。

1. 基础数学攻击

1.1 因子分解攻击

原理：直接分解模数 n = p × q

• 暴力分解：试除法

• Pollard's p-1 方法：当 p-1 的质因子都很小时有效

• Williams' p+1 方法：当 p+1 的质因子都很小时有效

• 二次筛法：适用于中等大小的 n

• 通用数域筛法：目前最有效的因子分解算法

# Pollard's p-1 方法示例
def pollard_p_minus_1(n, B=10000):
    a = 2
    for i in range(2, B + 1):
        a = pow(a, i, n)
        d = gcd(a - 1, n)
        if 1 < d < n:
            return d
    return None

1.2 共模攻击

条件：相同的 n，不同的 e
原理：如果 gcd(e₁, e₂) = 1，存在 r,s 使得 r·e₁ + s·e₂ = 1

def common_modulus_attack(c1, c2, e1, e2, n):
    r, s, g = extended_gcd(e1, e2)
    if r < 0:
        c1 = mod_inverse(c1, n)
        r = -r
    if s < 0:
        c2 = mod_inverse(c2, n)
        s = -s
    m = (pow(c1, r, n) * pow(c2, s, n)) % n
    return m

2. 参数选择不当攻击

2.1 小明文攻击

条件：mᵉ < n
原理：加密时未发生模运算，直接开 e 次方

def small_message_attack(c, e):
    m = exact_integer_root(c, e)
    return m

2.2 低加密指数攻击

条件：e 很小，相同明文发送给多个接收者
原理：使用中国剩余定理恢复明文

def low_exponent_attack(c_list, e_list, n_list):
    # 使用中国剩余定理
    result = chinese_remainder_theorem(c_list, n_list)
    m = exact_integer_root(result, e_list[0])
    return m

2.3 Wiener 攻击

条件：d < ⅓N⁰·²⁵
原理：使用连分数展开逼近私钥

def wiener_attack(e, n):
    # 连分数展开 e/n
    conv = continued_fraction(e, n)
    for k, d in get_convergents(conv):
        if k == 0:
            continue
        phi = (e * d - 1) // k
        # 验证是否找到正确的 φ(n)
        if validate_phi(n, phi):
            return d
    return None

2.4 小素数间隔攻击 (Fermat 分解)

条件：p 和 q 接近
原理：n = p×q，当 |p-q| 很小时可用 Fermat 分解

def fermat_factorization(n):
    a = isqrt(n)
    while True:
        b2 = a*a - n
        if is_square(b2):
            b = isqrt(b2)
            return a - b, a + b
        a += 1

3. 侧信道攻击

3.1 时序攻击

原理：通过测量解密时间推测私钥位

# 防御措施：恒定时间实现
def constant_time_pow(base, exponent, modulus):
    result = 1
    base = base % modulus
    # 从左到右扫描指数位，保持操作时间恒定
    for i in range(exponent.bit_length() - 1, -1, -1):
        result = (result * result) % modulus
        if (exponent >> i) & 1:
            result = (result * base) % modulus
    return result

3.2 功耗分析

• 简单功耗分析：直接从功耗轨迹读取密钥位

• 差分功耗分析：统计分析多次运行的功耗差异

3.3 错误注入攻击

原理：在解密过程中注入错误，通过错误结果推断密钥信息

4. 协议层攻击

4.1 选择密文攻击

类型：

• CCA1：在获得目标密文前可询问解密预言机

• CCA2：自适应选择密文攻击

防御：使用 OAEP 填充

def oaep_encode(message, n_bit_length, label=b''):
    # 最优非对称加密填充
    # 添加随机性和冗余防止CCA攻击
    pass

4.2 广播攻击

条件：相同明文用相同 e 加密给多个接收者

def broadcast_attack(ciphertexts, moduli, e):
    # 使用中国剩余定理
    result = crt(ciphertexts, moduli)
    m = exact_integer_root(result, e)
    return m

4.3 相关消息攻击

条件：明文之间存在已知线性关系
原理：建立多项式方程组求解

5. 高级数学攻击

5.1 Coppersmith 相关攻击

应用场景：

• 已知明文高位攻击

• 已知 p 或 q 的高位攻击

• 小私钥攻击的改进

def coppersmith_attack(n, known_bits, total_bits):
    # 使用Coppersmith方法求解模方程的小根
    # 需要SageMath等数学软件支持
    pass

5.2 循环攻击

条件：加密指数 e 与 φ(n) 不互质的特殊情况
原理：寻找最小的 k 使得 mᵉᵏ ≡ m (mod n)

5.3 不动点攻击

原理：寻找满足 mᵉ ≡ m (mod n) 的明文
这种明文加密后不变，可能泄露信息。

6. 实现相关攻击

6.1 填充预言攻击 (Bleichenbacher)

目标：PKCS#1 v1.5 填充
原理：利用解密错误信息逐步缩小明文范围

6.2 ROCA 攻击

目标：Infineon 芯片生成的 RSA 密钥
原理：利用密钥生成过程中的数学漏洞

6.3 密钥生成攻击

• 弱随机数生成器

• 重复使用质数

• 可预测的种子

7. 量子计算威胁

7.1 Shor 算法

原理：在量子计算机上多项式时间分解大整数
影响：一旦实用化量子计算机出现，RSA 将不再安全

# 经典计算机无法有效实现的Shor算法概念
def shors_algorithm(n):
    # 1. 随机选择 a < n
    # 2. 用量子傅里叶变换求阶 r: a^r ≡ 1 mod n
    # 3. 如果 r 是偶数，计算 gcd(a^(r/2) ± 1, n)
    # 4. 以高概率得到 n 的因子
    pass

8. 混合攻击类型

8.1 维纳攻击 + Coppersmith

结合小私钥攻击和Coppersmith方法处理更复杂情况

8.2 因子分解 + 侧信道

结合数学攻击和物理攻击提高成功率

9. 防御措施总结

攻击类型	防御措施
因子分解	使用足够大的密钥（≥2048位）
小指数攻击	使用 e=65537，添加适当填充
侧信道攻击	恒定时间实现，随机化
选择密文攻击	使用OAEP填充，验证密文完整性
协议攻击	遵循标准协议，添加随机数