本文章没有找到对应的语言版本

引言

hello！欢迎回到咪猫魔法世界~ 🐾✨

RSA的安全看似靠“大数分解”撑着，但如果私钥d选得太短，就会被维纳攻击轻松破解！本文专门拆解了维纳攻击的核心逻辑——用连分数逼近找到短小的d，不用分解n就能直接拿到私钥（cool），并在文末给出了完整代码和CTF例题，全程带着“踩坑实录”，帮新来的师傅们搞懂“为什么d短了就不安全”。

我们之前已经了解过了 RSA 的各种攻击，而维纳攻击算是“剑走偏锋”的一种，核心依赖数论里的连分数工具，看似复杂，实则思路超清晰——不过如果我们能掌握“连分数+收敛子验证”，这类题也是能拿下的。

一、前置知识：连分数——维纳攻击的核心工具

维纳攻击的本质是“用连分数逼近有理数”，所以先搞懂连分数的基础，攻击原理就顺理成章了。

1.1 连分数的定义

连分数是一种特殊的分数表示形式，通过整数与单位分数（分子为1的分数）递归嵌套表达，比如正分数\(a/b\)可展开为：

\[ x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \ddots}}} \]

简记为\([a_0; a_1, a_2, ..., a_k]\)，其中\(a_0\)是整数部分，\(a_1,a_2,...,a_k\)是正整数“部分商”。

举个例子：\(11/35\)的连分数展开为\([0; 3, 5, 2]\)，计算过程如下：

  1. \(35 ÷ 11 = 3\) 余 \(2\) → 部分商\(a_0=0\)，剩余\(2/11\)；
  2. \(11 ÷ 2 = 5\) 余 \(1\) → 部分商\(a_1=3\)，剩余\(1/2\)；
  3. \(2 ÷ 1 = 2\) 余 \(0\) → 部分商\(a_2=5\)，\(a_3=2\)，终止。

1.2 连分数的核心概念：收敛子

收敛子是“截取连分数前n项部分商”得到的近似分数，记为\(h_n/m_n\)（\(h_n\)为分子，\(m_n\)为分母）。它的关键性质是：

  • 逼近精度随项数增加而提高，交替大于、小于原分数；
  • 是原分数的“最优逼近”——没有分母更小的分数能比收敛子更接近原分数。

比如\(11/35\)的收敛子：

  • 前1项：\([0] → 0/1\)；
  • 前2项：\([0;3] → 1/3 ≈0.333\)；
  • 前3项：\([0;3,5] → 5/16 ≈0.3125\)；
  • 前4项：\([0;3,5,2] → 11/35 ≈0.314\)（完全等于原分数）。

1.3 关键定理（维纳攻击的数学基础）

  1. 狄利克雷逼近定理：对任意实数x和正整数N，存在整数h、m（\(1≤m≤N\)），使得\(|x - h/m| < 1/(mN)\)。当\(N=\sqrt{n}\)且\(d < \sqrt{n}\)时，\(k/d\)（k为余因子）是\(e/n\)的“优质逼近”，差距极小；
  2. 拉格朗日收敛子性质：若\(|x - h/m| < 1/(2m²)\)，则\(h/m\)必是x的某个收敛子。这直接关联“\(e/n\)的收敛子”与“\(k/d\)”，为捕捉d提供数学保证。

这部分貌似涉及到了大一高数的重点知识？所以说密码和数学关系真的密切！

二、维纳攻击核心原理：抓出短小的私钥d

2.1 攻击前提：d过短的漏洞本质

RSA的核心等式是\(e×d ≡ 1 \pmod{\phi(n)}\)，即存在整数k，使得\(e×d = k×\phi(n) + 1\)。

当d过短时（满足\(d < n^{1/4}/3\)，n的四次方根的1/3），\(d/\phi(n)\)会非常小，变形核心等式可得：

\[ \frac{e}{\phi(n)} = \frac{k}{d} + \frac{1}{d×\phi(n)} \]

由于\(n = p×q\)，\(\phi(n) = (p-1)(q-1) ≈ n\)，所以\(e/n ≈ e/\phi(n) ≈ k/d\)——即\(k/d\)是\(e/n\)的近似分数，且分母d就是我们要找的私钥！

结合连分数的收敛子性质，\(k/d\)必然是\(e/n\)的某个收敛子，所以只要计算\(e/n\)的所有收敛子，验证分母是否为d即可。

2.2 攻击特征

  • 题目明确提示“d是小整数”或“d选择不当”；
  • 模数n难以直接分解，但e和n已知，且无其他明显漏洞（如共模、低指数）；
  • e较大（若e过小，优先考虑低指数攻击；e过大，维纳攻击更适用）。

2.3 维纳攻击vs扩展欧几里得算法

对比维度 维纳攻击 扩展欧几里得算法
攻击目标 从\((e,n)\)破解短小的d 从\((e,\phi(n))\)计算精准的d
已知条件 公钥\((e,n)\)（无需分解n） 需已知\(e\)和\(\phi(n)\)（依赖n分解）
核心工具 连分数+收敛子验证 辗转相除法求模逆元
结果 候选d（需验证有效性） 精准d（无需验证）
适用场景 d过短（\(d < n^{1/4}/3\)） RSA正常密钥生成（\(\gcd(e,\phi(n))=1\)）

三、维纳攻击实现步骤

3.1 攻击步骤拆解

  1. 计算\(e/n\)的连分数展开，得到所有部分商；
  2. 计算连分数的所有收敛子\(h_i/m_i\)（分子\(h_i\)，分母\(m_i\)）；
  3. 对每个收敛子，验证分母\(m_i\)是否为私钥d：
    • 计算\(\phi(n) = (e×m_i - 1)/h_i\)（需满足\(e×m_i - 1\)能被\(h_i\)整除）；
    • 验证\(\phi(n)\)是否合理：\(n - \phi(n) + 1\)的判别式需为完全平方数（因为\(p+q = n - \phi(n) + 1\)，\(pq = n\)，可解二次方程求p、q）；
    • 验证\(e×d ≡ 1 \pmod{\phi(n)}\)，若成立则d有效；
    • 用d解密密文c，若能得到合理明文（如CTF flag格式），则攻击成功。

3.2 Python代码实现 

 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

import gmpy2
from Crypto.Util.number import long_to_bytes

def continued_fraction(e, n):
    """计算e/n的连分数展开，返回部分商列表"""
    cf = []
    while n != 0:
        cf.append(e // n)
        e, n = n, e % n
    return cf

def convergents(cf):
    """计算连分数的所有收敛子，返回列表[(h0,m0), (h1,m1), ...]"""
    convs = []
    h_prev, h_curr = 0, 1  # 前一项分子、当前分子
    m_prev, m_curr = 1, 0  # 前一项分母、当前分母
    for a in cf:
        h_next = a * h_curr + h_prev
        m_next = a * m_curr + m_prev
        convs.append((h_next, m_next))
        h_prev, h_curr = h_curr, h_next
        m_prev, m_curr = m_curr, m_next
    return convs

def wiener_attack(e, n, c=None):
    """
    维纳攻击核心函数
    :param e: 公钥指数
    :param n: 模数
    :param c: 密文（可选，用于验证明文）
    :return: 有效私钥d，若未找到返回None
    """
    # 步骤1：计算e/n的连分数和收敛子
    cf = continued_fraction(e, n)
    convs = convergents(cf)
    print(f"连分数部分商：{cf}")
    print(f"所有收敛子：{convs}")
    
    # 步骤2：验证每个收敛子的分母是否为d
    for h, m in convs:
        d = m
        if d == 0:
            continue  # 分母不能为0
        # 验证e*d -1是否能被h整除（确保phi(n)为整数）
        if (e * d - 1) % h != 0:
            continue
        phi = (e * d - 1) // h
        # 验证phi是否合理：通过p+q和pq构造二次方程，判断是否有整数解
        pq = n
        p_plus_q = n - phi + 1
        # 二次方程：x² - (p+q)x + pq = 0，判别式delta = (p+q)² - 4pq
        delta = p_plus_q * p_plus_q - 4 * pq
        if delta < 0:
            continue
        sqrt_delta = gmpy2.isqrt(delta)
        if sqrt_delta * sqrt_delta != delta:
            continue  # 判别式不是完全平方数，无整数解
        # 计算p和q，验证是否为素数（简化验证，CTF中可省略素数判断，直接解密）
        p = (p_plus_q + sqrt_delta) // 2
        q = (p_plus_q - sqrt_delta) // 2
        if p * q != n:
            continue
        # 验证e*d ≡ 1 mod phi(n)
        if (e * d) % phi != 1:
            continue
        # 若有密文，验证解密是否合理（如含flag格式）
        if c is not None:
            m = pow(c, d, n)
            try:
               明文 = long_to_bytes(m).decode('ascii')
                if "flag" in 明文.lower() or "gwht" in 明文.lower():
                    print(f"找到有效私钥d：{d}")
                    print(f"解密明文：{明文}")
                    return d
            except:
                pass
        # 无密文时，返回验证通过的d
        print(f"找到有效私钥d：{d}")
        return d
    return None

# 测试示例（简化CTF真题）
if __name__ == "__main__":
    # 已知公钥(e,n)和密文c
    e = 30749686305802061816334591167284030734478031427751495527922388099381921172620569310945418007467306454160014597828390709770861577479329793948103408489494025272834473555854835044153374978554414416305012267643957838998648651100705446875979573675767605387333733876537528353237076626094553367977134079292593746416875606876735717905892280664538346000950343671655257046364067221469807138232820446015769882472160551840052921930357988334306659120253114790638496480092361951536576427295789429197483597859657977832368912534761100269065509351345050758943674651053419982561094432258103614830448382949765459939698951824447818497599
    n = 109966163992903243770643456296093759130737510333736483352345488643432614201030629970207047930115652268531222079508230987041869779760776072105738457123387124961036111210544028669181361694095594938869077306417325203381820822917059651429857093388618818437282624857927551285811542685269229705594166370426152128895901914709902037365652575730201897361139518816164746228733410283595236405985958414491372301878718635708605256444921222945267625853091126691358833453283744166617463257821375566155675868452032401961727814314481343467702299949407935602389342183536222842556906657001984320973035314726867840698884052182976760066141
    c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

    d = wiener_attack(e, n, c)
    if d is None:
        print("未找到有效私钥d，可能d不满足长度条件或攻击失败")

四、维纳攻击的扩展应用（2020羊城杯例题）

维纳攻击不止能抓d！当比例关系满足“近似逼近”时，还能破解p或q，比如2020羊城杯例题：

例题背景

  • 已知\(N1 = P1²×Q1\)，\(N2 = P2²×Q2\)，\(P2\)是\(P1\)的下一个素数（\(P2-P1 < 1000\)）；
  • 核心思路：\(N1/N2 ≈ (P1²×Q1)/(P2²×Q2) ≈ Q1/Q2\)，对\(N1/N2\)做连分数展开，收敛子的分母可能是\(Q2\)，进而分解\(N2\)得到\(P2\)和\(Q2\)，再推导\(P1\)和\(Q1\)。

核心结论

维纳攻击的本质是“比例逼近”，只要两个数的比例能被连分数的收敛子近似，且分母是目标参数（d、p、q等），就能尝试用该方法破解——这也是CTF中维纳攻击的常见拓展题型！

✨ 咪猫碎碎念

维纳攻击的难点在于“连分数的理解”，但实际实现时，只要记住“计算连分数→求收敛子→验证d”三步，代码套模板就行了。

踩坑提醒：

  1. 连分数计算时，e和n的顺序不能搞反（是\(e/n\)，不是\(n/e\)）；
  2. 验证d时，一定要检查\(p×q是否等于n\)，避免phi(n)计算错误；
  3. 若攻击失败，可能是d不满足长度条件（\(d ≥ n^{1/4}/3\)），可尝试扩展维纳攻击（结合其他约束）。

学习时建议先手动计算小例子的连分数和收敛子，比如\(e=65537\)，\(n=248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113\)，手动算收敛子，再用代码验证，理解会更深刻~o( =∩ω∩= )m～

参考blog