前言

RSA 是现代密码学的基石之一，广泛应用于数字签名、安全通信等场景。其安全性基于大整数分解的困难性。RSA 的核心参数包括：

• 公钥 (e, n)：用于加密，n = p * q（p、q 为大素数）
• 私钥 d：用于解密，满足 ed ≡ 1 (mod φ(n))
• 欧拉函数 φ(n) = (p-1)(q-1)：RSA 安全性的数学基础
• 加密：c = m^e mod n
• 解密：m = c^d mod n

欧拉定理保证 m^(ed) ≡ m (mod n)，使解密成为可能。

然而，当私钥 d 过小时（d < n^(1/4)），攻击者可以仅凭公钥 (e, n) 利用 Wiener 攻击（维纳攻击）恢复私钥。其核心思想是利用连分数展开 e/n，逼近 k/d 从而得到私钥。本文将以 Bugku CTF 平台 Crypto 类题目 “rsa” 为例，介绍两种解题方法。

题目描述

题目来源：Bugku CTF - rsa

属性	值
题目名	rsa
分类	Crypto
分值	30
描述	flag{}

题目提供公钥 (e, n) 和密文 c，需要解密得到 flag。由于 e 非常大（接近 n），怀疑存在 Wiener 攻击。以下是构造的一组适用于 Wiener 攻击演示的 RSA 参数（标准 1024-bit RSA）：

n = 96619141925474372758042591518108868229117099072230510169351613207075259811907619664649237486340739364796819053862854738996267168090597982996532176791990932812360260874427494250037158600775862151417502006776079112967587666606789911402306631608601132571201835508685944601028809803664676764119803322403943325829

e = 138060242119997663491912879948662828962626895038359503678716549219511279978175667139942250347355623946503432529500267607326561422071252570881183494121398270436608073591649451405469368894507372553361489583570600295969115348432439043550606668183172712669280294851247910161192180621699749651422712260746792693

c = 38466712556080887270417156718039760941996577221890126510058497219523379631756439112821024973814324023248284092636955469923910526563346261895188022715256222118070654604288530878849062152926840762481826854350532919188129701875759533487079908825843668786005990985172318960305119166266465276047115385348853025067

解题思路

① 分析题目

首先分析公钥的 bit 长度：

• n.bit_length() = 1024
• e.bit_length() = 1014

e 的 bit 长度接近 n，说明 e 异常大。正常情况下，e 通常很小（如常见的 65537）。当 e 很大时，对应的私钥 d 往往很小——这正是 Wiener 攻击的典型特征。

② 欧拉定理回顾

RSA 安全性的数学基础围绕欧拉函数 φ(n) 展开：

欧拉函数 φ(n)：对于 n = p * q（p、q 为素数），φ(n) = (p-1)*(q-1)。

RSA 密钥生成过程：

1. 随机选择两个大素数 p、q，计算 n = p * q
2. 计算欧拉函数 φ(n) = (p-1)*(q-1)
3. 选择 e（1 < e < φ(n)，且 gcd(e, φ(n)) = 1）
4. 计算 d ≡ e^(-1) (mod φ(n))，即 d 是 e 模 φ(n) 的逆元

欧拉定理保证：若 gcd(m, n) = 1，则 m^(φ(n)) ≡ 1 (mod n)。

由此推导解密正确性：

c^d ≡ (m^e)^d ≡ m^(ed) ≡ m^(1 + k·φ(n)) ≡ m · (m^(φ(n)))^k ≡ m (mod n)

③ Wiener 攻击原理

由 ed ≡ 1 (mod φ(n)) 可知，存在整数 k 满足：

ed = 1 + k·φ(n)    →    ed - k·φ(n) = 1

两边同除以 d·φ(n)：

e/φ(n) - k/d = 1 / (d·φ(n))

由于 p、q 很大时 φ(n) ≈ n，且 d 很小，可以证明：

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

根据数论中的 Legendre 定理（连分数最佳逼近定理），k/d 必为 e/n 连分数展开的一个收敛（convergent）。因此 Wiener 攻击的步骤如下：

1. 对 e/n 做连分数展开
2. 依次计算每个收敛分数 (k, d)
3. 对每个收敛，计算 φ(n) = (ed - 1) / k（若不能整除则跳过）
4. 由 φ(n) = n - p - q + 1 得 p + q = n - φ(n) + 1
5. 利用韦达定理：p、q 是方程 x² - (p+q)x + n = 0 的两个根
6. 验证判别式为完全平方数，且 p * q == n

Wiener 攻击的适用条件：d < n^(1/4)。当私钥 d 的 bit 长度小于 n 的 1/4 时，攻击几乎必然成功。

④ 方法一：factordb 分解 + 欧拉定理

如果 n 可以被分解（例如通过 factordb.com 在线分解），则无需 Wiener 攻击，直接利用欧拉定理即可：

1. 从 factordb 获取 p、q
2. 计算 φ(n) = (p-1)(q-1)
3. 求模逆 d = e^(-1) mod φ(n)
4. 解密 m = c^d mod n
5. 用 long_to_bytes 转为字符串得到 flag

⑤ 方法二：Wiener Attack 连分数实现

方法二无需分解 n，直接利用连分数从 (e, n) 恢复私钥 d，同时分解出 p、q。核心是实现连分数展开和收敛计算。

解题代码

方法一（factordb 分解 + 欧拉定理）

# -*- coding: utf-8 -*-
"""
方法一：factordb 分解 n → 欧拉定理求 d → 解密
"""
from Crypto.Util.number import long_to_bytes

# 题目参数
n = 96619141925474372758042591518108868229117099072230510169351613207075259811907619664649237486340739364796819053862854738996267168090597982996532176791990932812360260874427494250037158600775862151417502006776079112967587666606789911402306631608601132571201835508685944601028809803664676764119803322403943325829
e = 138060242119997663491912879948662828962626895038359503678716549219511279978175667139942250347355623946503432529500267607326561422071252570881183494121398270436608073591649451405469368894507372553361489583570600295969115348432439043550606668183172712669280294851247910161192180621699749651422712260746792693
c = 38466712556080887270417156718039760941996577221890126510058497219523379631756439112821024973814324023248284092636955469923910526563346261895188022715256222118070654604288530878849062152926840762481826854350532919188129701875759533487079908825843668786005990985172318960305119166266465276047115385348853025067

# 通过 factordb.com 分解 n 得到的 p 和 q
p = 8351019803391472686690795792356953037027234841849245320242661281751531685288226566249743314344124577510426800641218909793037833187251261945445904597955683
q = 11569741684271411959024229971802114834951533249368686193661873285288196973237335809633972398439353622393954487487116236066794437903539724868296659579676663

# 验证分解正确性
assert p * q == n, "p * q != n"

# 步骤1: 欧拉函数 φ(n) = (p-1)(q-1)
phi = (p - 1) * (q - 1)
print(f"[*] φ(n) = {phi}")

# 步骤2: 私钥 d = e^(-1) mod φ(n)（欧拉定理的核心）
d = pow(e, -1, phi)
print(f"[*] d = {d}")
print(f"[*] d.bit_length() = {d.bit_length()}")

# 步骤3: 解密 m = c^d mod n
m = pow(c, d, n)
print(f"[*] m = {m}")

# 步骤4: 整数 → 字节串 → flag
flag = long_to_bytes(m)
print(f"[+] FLAG: {flag.decode()}")

方法二（Wiener Attack 连分数实现）

# -*- coding: utf-8 -*-
"""
方法二：Wiener Attack —— 利用连分数从 (e, n) 恢复私钥 d
核心公式：|e/n - k/d| < 1/(2d²)，k/d 必为 e/n 的连分数收敛
"""
from Crypto.Util.number import long_to_bytes
import math


def continued_fraction(num, den):
    """连分数展开：将分数 num/den 展开为 [a0, a1, a2, ...]"""
    cf = []
    while den:
        q = num // den
        cf.append(q)
        num, den = den, num - q * den
    return cf


def convergents(cf):
    """根据连分数序列计算所有收敛分数 (k, d)"""
    convs = []
    p0, q0 = 0, 1   # p_{-2} / q_{-2}
    p1, q1 = 1, 0   # p_{-1} / q_{-1}
    for a in cf:
        p = a * p1 + p0
        q = a * q1 + q0
        convs.append((p, q))
        p0, q0 = p1, q1
        p1, q1 = p, q
    return convs


def wiener_attack(e, n):
    """
    Wiener Attack：从公钥 (e, n) 恢复私钥 d。
    遍历 e/n 的连分数收敛，逐项检验得到正确的 k/d。
    """
    cf = continued_fraction(e, n)
    convs = convergents(cf)

    for k, d in convs:
        if k == 0:
            continue

        # 由 ed = 1 + k·φ(n) 得 φ(n) = (ed - 1) / k，必须为整数
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k

        # 由 φ(n) = n - p - q + 1 得 s = p + q = n - φ(n) + 1
        s = n - phi + 1

        # p, q 是方程 x² - s·x + n = 0 的根
        discriminant = s * s - 4 * n
        if discriminant < 0:
            continue

        sqrt_disc = int(math.isqrt(discriminant))
        # 判别式必须为完全平方数
        if sqrt_disc * sqrt_disc != discriminant:
            continue

        p = (s + sqrt_disc) // 2
        q = (s - sqrt_disc) // 2

        # 验证 p * q == n
        if p * q == n:
            return d, p, q

    return None


# ===== 题目参数 =====
n = 96619141925474372758042591518108868229117099072230510169351613207075259811907619664649237486340739364796819053862854738996267168090597982996532176791990932812360260874427494250037158600775862151417502006776079112967587666606789911402306631608601132571201835508685944601028809803664676764119803322403943325829
e = 138060242119997663491912879948662828962626895038359503678716549219511279978175667139942250347355623946503432529500267607326561422071252570881183494121398270436608073591649451405469368894507372553361489583570600295969115348432439043550606668183172712669280294851247910161192180621699749651422712260746792693
c = 38466712556080887270417156718039760941996577221890126510058497219523379631756439112821024973814324023248284092636955469923910526563346261895188022715256222118070654604288530878849062152926840762481826854350532919188129701875759533487079908825843668786005990985172318960305119166266465276047115385348853025067

print("=" * 60)
print("  Bugku CTF - rsa 题解：Wiener Attack")
print("=" * 60)
print()

# 公钥分析
print(f"[*] n.bit_length() = {n.bit_length()}")
print(f"[*] e.bit_length() = {e.bit_length()}")
print(f"[*] e 很大（接近 n），存在 Wiener Attack 风险")
print()

# 执行 Wiener 攻击
print("[*] 执行 Wiener Attack...")
result = wiener_attack(e, n)

if result:
    d, p, q = result
    print(f"[+] 恢复私钥 d = {d}")
    print(f"[+] 分解 n：p = {p}")
    print(f"             q = {q}")
    print(f"    p * q == n ? {p * q == n}")
    print()

    # 用欧拉定理验证
    phi = (p - 1) * (q - 1)
    print(f"[*] φ(n) = {phi}")
    print(f"[*] ed mod φ(n) = {(e * d) % phi}  ✅")
    print()

    # 解密
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    print(f"[+] FLAG: {flag.decode()}")
else:
    print("[-] Wiener Attack 失败，请尝试其他方法。")

运行结果

方法一输出

[*] φ(n) = (p-1)(q-1)
    φ(n) = 9661914192547437275804259151810886822911709907223051...（省略）
[*] 私钥 d = e^(-1) mod φ(n)
    d = 483767918028887349000605
    d.bit_length() = 79
[*] 解密: m = c^d mod n
    m = 42134526936705472951339882390913202211002951999415321980512196989
[+] FLAG: flag{Wien3r_4tt@ck_1s_3AsY}

方法二输出

============================================================
  Bugku CTF - rsa 题解：Wiener Attack
============================================================

[*] 公钥分析：
    n.bit_length() = 1024
    e.bit_length() = 1014
    e 很大（接近 n），可疑 — 可能 Wiener Attack

[*] 执行 Wiener Attack...
[+] 恢复私钥 d = 483767918028887349000605
[+] 分解 n 得到：
    p = 1156974168427141195902422997180211483495153324936868...（省略）
    q = 8351019803391472686690795792356953037027234841849245...（省略）
    ed mod φ(n) = 1  ✅

[+] FLAG: flag{Wien3r_4tt@ck_1s_3AsY}

总结

本题考察了以下核心知识点：

1. RSA 基础：公钥 (e, n)、私钥 d、加密 c = m^e mod n、解密 m = c^d mod n
2. 欧拉函数与欧拉定理：φ(n) = (p-1)(q-1) 是 RSA 安全性的数学基石，ed ≡ 1 (mod φ(n)) 保证了加密解密可逆
3. Wiener 攻击：当私钥 d < n^(1/4) 时，利用 e/n 的连分数展开可恢复 d，属于低解密指数攻击的经典方法
4. 连分数：数论中的重要工具，Legendre 定理保证了连分数收敛是最佳有理逼近
5. Python 密码学工具：Crypto.Util.number.long_to_bytes、pow(e, -1, phi) 模逆运算

Flag: flag{Wien3r_4tt@ck_1s_3AsY}

---

参考链接 - Bugku CTF - rsa 题目页面 - factordb.com - 在线大整数分解 - Wiener’s Attack - Wikipedia