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

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

2. 前置知识<\/h2>

2.1 连分数<\/h3>

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

对于有理数a，可以表示为：<\/p>

a = a0 + 1\/(a1 + 1\/(a2 + 1\/(... + 1\/an)...))
<\/code><\/pre>
记为a = [a0; a1, a2, ..., an]<\/p>
2.2 收敛分数<\/h3>
收敛分数是利用连分数逐步逼近实数的过程：<\/p>
对于a = [a0; a1, a2, ..., an]，其收敛分数序列为：<\/p>

[a0]<\/li>
[a0, a1]<\/li>
[a0, a1, a2]<\/li>
...<\/li>
[a0, a1, a2, ..., an]<\/li>
<\/ul>
随着项数增加，收敛分数越来越接近原始数a。<\/p>
2.3 连分数定理(Legendre's theorem)<\/h3>
定理<\/strong>：如果存在a ∈ Q，且p,q ∈ Z满足：<\/p>
|a - p\/q| < 1\/(2q²)
<\/code><\/pre>
那么p\/q必定出现在a的收敛分数序列中。<\/p>
3. 维纳攻击原理<\/h2>
3.1 攻击条件<\/h3>
维纳攻击适用于满足以下条件的RSA系统：<\/p>

私钥d较小：d < (1\/3)n^(1\/4)<\/li>
q < p < 2q（这是RSA密钥生成的常见情况）<\/li>
e < φ(n)<\/li>
<\/ol>
3.2 数学推导<\/h3>
RSA基本方程：<\/p>
ed ≡ 1 mod φ(n) ⇒ ed = kφ(n) + 1
<\/code><\/pre>
将方程两边除以dφ(n)：<\/p>
e\/φ(n) = k\/d + 1\/(dφ(n))
<\/code><\/pre>
用n近似φ(n)（因为φ(n) ≈ n）：<\/p>
e\/n ≈ k\/d
<\/code><\/pre>
我们需要证明：<\/p>
|e\/n - k\/d| < 1\/(2d²)
<\/code><\/pre>
这样就能应用Legendre定理，通过e\/n的连分数展开找到k\/d。<\/p>
3.3 不等式证明<\/h3>
从ed = kφ(n) + 1开始：<\/p>
|e\/n - k\/d| = |(ed - kn)\/(nd)| = |(kφ(n) + 1 - kn)\/(nd)| = |1 - k(n - φ(n))|\/(nd)
<\/code><\/pre>
由于φ(n) = n - p - q + 1，且n = pq：<\/p>
n - φ(n) = p + q - 1 ≈ p + q
<\/code><\/pre>
在q < p < 2q条件下：<\/p>

n = pq ⇒ q² < n < p² < 4q² ⇒ q < √n < p < 2q<\/li>
p + q < 3q < 3√n<\/li>
<\/ul>
因此：<\/p>
|e\/n - k\/d| ≈ |1 - k(p + q)|\/(nd) < k(p + q)\/(nd) < 3k√n\/(nd) = 3k\/(d√n)
<\/code><\/pre>
由于kφ(n) ≈ ed < dφ(n) ⇒ k < d：<\/p>
3k\/(d√n) < 3d\/(d√n) = 3\/√n
<\/code><\/pre>
要使3\/√n < 1\/(2d²)，即：<\/p>
d < √n\/(6d²) ⇒ d³ < √n\/6 ⇒ d < (1\/6)^(1\/3) n^(1\/6)
<\/code><\/pre>
实际上更严格的推导可以得到d < (1\/3)n^(1\/4)。<\/p>
4. 攻击步骤<\/h2>

计算e\/n的连分数展开<\/li>
计算其收敛分数序列<\/li>
对每个收敛分数k'\/d'：

检查d'是否为奇数（因为φ(n)是偶数）<\/li>
计算φ'(n) = (ed' - 1)\/k'<\/li>
解方程x² - (n - φ'(n) + 1)x + n = 0，检查是否得到整数解p,q<\/li>
<\/ul>
<\/li>
如果找到有效的p,q，则成功分解n并恢复私钥d<\/li>
<\/ol>
5. 代码实现<\/h2>
5.1 连分数展开<\/h3>
def<\/span> continued_fraction<\/span>(e, n):
<\/span><\/span>    cf =<\/span> []
<\/span><\/span>    while<\/span> n !=<\/span> 0<\/span>:
<\/span><\/span>        cf.<\/span>append(e \/\/<\/span> n)
<\/span><\/span>        e, n =<\/span> n, e %<\/span> n
<\/span><\/span>    return<\/span> cf
<\/span><\/span><\/code><\/pre>5.2 计算收敛分数<\/h3>
def<\/span> convergents<\/span>(cf):
<\/span><\/span>    convergents =<\/span> []
<\/span><\/span>    for<\/span> i in<\/span> range(len(cf)):
<\/span><\/span>        numerator =<\/span> 1<\/span>
<\/span><\/span>        denominator =<\/span> 0<\/span>
<\/span><\/span>        for<\/span> j in<\/span> range(i, -<\/span>1<\/span>, -<\/span>1<\/span>):
<\/span><\/span>            numerator, denominator =<\/span> cf[j] *<\/span> numerator +<\/span> denominator, numerator
<\/span><\/span>        convergents.<\/span>append((numerator, denominator))
<\/span><\/span>    return<\/span> convergents
<\/span><\/span><\/code><\/pre>5.3 维纳攻击完整实现<\/h3>
import<\/span> math
<\/span><\/span>
<\/span><\/span>def<\/span> wiener_attack<\/span>(e, n):
<\/span><\/span>    # 计算e\/n的连分数展开<\/span>
<\/span><\/span>    cf =<\/span> continued_fraction(e, n)
<\/span><\/span>    
<\/span><\/span>    # 计算收敛分数<\/span>
<\/span><\/span>    conv =<\/span> convergents(cf)
<\/span><\/span>    
<\/span><\/span>    for<\/span> (k, d) in<\/span> conv:
<\/span><\/span>        # 跳过d=0的情况<\/span>
<\/span><\/span>        if<\/span> d ==<\/span> 0<\/span>:
<\/span><\/span>            continue<\/span>
<\/span><\/span>            
<\/span><\/span>        # 检查ed ≡ 1 mod k<\/span>
<\/span><\/span>        if<\/span> (e *<\/span> d) %<\/span> k !=<\/span> 1<\/span>:
<\/span><\/span>            continue<\/span>
<\/span><\/span>            
<\/span><\/span>        # 计算phi(n)的候选值<\/span>
<\/span><\/span>        phi =<\/span> (e *<\/span> d -<\/span> 1<\/span>) \/\/<\/span> k
<\/span><\/span>        
<\/span><\/span>        # 解二次方程x^2 - (n - phi + 1)x + n = 0<\/span>
<\/span><\/span>        a =<\/span> 1<\/span>
<\/span><\/span>        b =<\/span> -<\/span>(n -<\/span> phi +<\/span> 1<\/span>)
<\/span><\/span>        c =<\/span> n
<\/span><\/span>        
<\/span><\/span>        # 计算判别式<\/span>
<\/span><\/span>        discriminant =<\/span> b *<\/span> b -<\/span> 4<\/span> *<\/span> a *<\/span> c
<\/span><\/span>        if<\/span> discriminant <<\/span> 0<\/span>:
<\/span><\/span>            continue<\/span>
<\/span><\/span>            
<\/span><\/span>        # 检查是否为完全平方数<\/span>
<\/span><\/span>        sqrt_disc =<\/span> math.<\/span>isqrt(discriminant)
<\/span><\/span>        if<\/span> sqrt_disc *<\/span> sqrt_disc !=<\/span> discriminant:
<\/span><\/span>            continue<\/span>
<\/span><\/span>            
<\/span><\/span>        # 计算p和q<\/span>
<\/span><\/span>        p =<\/span> (-<\/span>b +<\/span> sqrt_disc) \/\/<\/span> (2<\/span> *<\/span> a)
<\/span><\/span>        q =<\/span> (-<\/span>b -<\/span> sqrt_disc) \/\/<\/span> (2<\/span> *<\/span> a)
<\/span><\/span>        
<\/span><\/span>        if<\/span> p *<\/span> q ==<\/span> n:
<\/span><\/span>            return<\/span> d  # 找到私钥d<\/span>
<\/span><\/span>    
<\/span><\/span>    return<\/span> None<\/span>  # 攻击失败<\/span>
<\/span><\/span><\/code><\/pre>6. 防御措施<\/h2>
为了防止维纳攻击，应采取以下措施：<\/p>

避免使用过小的私钥d<\/li>
确保d > (1\/3)n^(1\/4)<\/li>
使用较大的公钥指数e<\/li>
在密钥生成时添加额外约束条件<\/li>
<\/ol>
7. 总结<\/h2>
维纳攻击利用连分数逼近的方法，在私钥d较小时能够高效地恢复RSA私钥。理解这一攻击的原理不仅有助于CTF竞赛，也能帮助设计更安全的RSA实现。关键点在于：<\/p>

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

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

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

2. 前置知识<\/h2>

3. 维纳攻击原理<\/h2>

5. 代码实现<\/h2>

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