Wiener's Attack 教学文档：利用连分数攻破低解密指数RSA

1. 概述

维纳攻击(Wiener's Attack)是针对RSA密码系统的一种攻击方法，特别适用于私钥指数d较小的情况。该攻击通过连分数逼近的方法，从公钥e和模数n的比值中恢复出私钥d。

2. 前置知识

2.1 连分数

连分数是一种特殊的分数表示方法，将实数表示为一系列整数的序列：

对于有理数a，可以表示为：

a = a0 + 1/(a1 + 1/(a2 + 1/(... + 1/an)...))

记为a = [a0; a1, a2, ..., an]

2.2 收敛分数

收敛分数是利用连分数逐步逼近实数的过程：

对于a = [a0; a1, a2, ..., an]，其收敛分数序列为：

• [a0]
• [a0, a1]
• [a0, a1, a2]
• ...
• [a0, a1, a2, ..., an]

随着项数增加，收敛分数越来越接近原始数a。

2.3 连分数定理(Legendre's theorem)

定理：如果存在a ∈ Q，且p,q ∈ Z满足：

|a - p/q| < 1/(2q²)

那么p/q必定出现在a的收敛分数序列中。

3. 维纳攻击原理

3.1 攻击条件

维纳攻击适用于满足以下条件的RSA系统：

1. 私钥d较小：d < (1/3)n^(1/4)
2. q < p < 2q（这是RSA密钥生成的常见情况）
3. e < φ(n)

3.2 数学推导

RSA基本方程：

ed ≡ 1 mod φ(n) ⇒ ed = kφ(n) + 1

将方程两边除以dφ(n)：

e/φ(n) = k/d + 1/(dφ(n))

用n近似φ(n)（因为φ(n) ≈ n）：

e/n ≈ k/d

我们需要证明：

|e/n - k/d| < 1/(2d²)

这样就能应用Legendre定理，通过e/n的连分数展开找到k/d。

3.3 不等式证明

从ed = kφ(n) + 1开始：

|e/n - k/d| = |(ed - kn)/(nd)| = |(kφ(n) + 1 - kn)/(nd)| = |1 - k(n - φ(n))|/(nd)

由于φ(n) = n - p - q + 1，且n = pq：

n - φ(n) = p + q - 1 ≈ p + q

在q < p < 2q条件下：

• n = pq ⇒ q² < n < p² < 4q² ⇒ q < √n < p < 2q
• p + q < 3q < 3√n

因此：

|e/n - k/d| ≈ |1 - k(p + q)|/(nd) < k(p + q)/(nd) < 3k√n/(nd) = 3k/(d√n)

由于kφ(n) ≈ ed < dφ(n) ⇒ k < d：

3k/(d√n) < 3d/(d√n) = 3/√n

要使3/√n < 1/(2d²)，即：

d < √n/(6d²) ⇒ d³ < √n/6 ⇒ d < (1/6)^(1/3) n^(1/6)

实际上更严格的推导可以得到d < (1/3)n^(1/4)。

4. 攻击步骤

1. 计算e/n的连分数展开
2. 计算其收敛分数序列
3. 对每个收敛分数k'/d'：
   • 检查d'是否为奇数（因为φ(n)是偶数）
   • 计算φ'(n) = (ed' - 1)/k'
   • 解方程x² - (n - φ'(n) + 1)x + n = 0，检查是否得到整数解p,q
4. 如果找到有效的p,q，则成功分解n并恢复私钥d

5. 代码实现

5.1 连分数展开

def continued_fraction(e, n):
    cf = []
    while n != 0:
        cf.append(e // n)
        e, n = n, e % n
    return cf

5.2 计算收敛分数

def convergents(cf):
    convergents = []
    for i in range(len(cf)):
        numerator = 1
        denominator = 0
        for j in range(i, -1, -1):
            numerator, denominator = cf[j] * numerator + denominator, numerator
        convergents.append((numerator, denominator))
    return convergents

5.3 维纳攻击完整实现

import math

def wiener_attack(e, n):
    # 计算e/n的连分数展开
    cf = continued_fraction(e, n)
    
    # 计算收敛分数
    conv = convergents(cf)
    
    for (k, d) in conv:
        # 跳过d=0的情况
        if d == 0:
            continue
            
        # 检查ed ≡ 1 mod k
        if (e * d) % k != 1:
            continue
            
        # 计算phi(n)的候选值
        phi = (e * d - 1) // k
        
        # 解二次方程x^2 - (n - phi + 1)x + n = 0
        a = 1
        b = -(n - phi + 1)
        c = n
        
        # 计算判别式
        discriminant = b * b - 4 * a * c
        if discriminant < 0:
            continue
            
        # 检查是否为完全平方数
        sqrt_disc = math.isqrt(discriminant)
        if sqrt_disc * sqrt_disc != discriminant:
            continue
            
        # 计算p和q
        p = (-b + sqrt_disc) // (2 * a)
        q = (-b - sqrt_disc) // (2 * a)
        
        if p * q == n:
            return d  # 找到私钥d
    
    return None  # 攻击失败

6. 防御措施

为了防止维纳攻击，应采取以下措施：

1. 避免使用过小的私钥d
2. 确保d > (1/3)n^(1/4)
3. 使用较大的公钥指数e
4. 在密钥生成时添加额外约束条件

7. 总结

维纳攻击利用连分数逼近的方法，在私钥d较小时能够高效地恢复RSA私钥。理解这一攻击的原理不仅有助于CTF竞赛，也能帮助设计更安全的RSA实现。关键点在于：

• 连分数和收敛分数的概念
• Legendre定理的应用
• 从RSA方程到可逼近形式的转换
• 不等式条件的推导和验证