CTF BUUOJ rsa2 攻防战：Wiener 攻击与 Python 2 的“坑”

题目描述

题目提供了 RSA 的公钥参数 $N$ 和 $e$，并给出了生成 Flag 的代码片段：

N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
import hashlib
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"

题目提示：“听说这题是rsa的续集”。

解题思路

1. 分析参数特征

首先观察题目给出的 $N$ 和 $e$。

• $N$ 是一个 1024 位的大整数。
• $e$ 是一个非常大的整数，接近 $N$ 的数量级。
  在 RSA 算法中，通常 $e$ 会选择较小的值（如 65537）。当 $e$ 非常大时，根据关系式 $ed\equiv 1(\mathrm{mod}\varphi (N))$，对应的私钥 $d$ 往往会非常小。
  当 $d<\frac{1}{3}{N}^{\frac{1}{4}}$ 时，RSA 系统存在 Wiener 攻击 漏洞。我们可以利用连分数逼近的方法来求解 $d$。

2. Wiener 攻击原理

Wiener 攻击的核心思想是利用连分数展开。因为 $ed-1=k\varphi (N)$，所以 $\frac{e}{\varphi (N)}\approx \frac{k}{d}$。又因为 $\varphi (N)\approx N$，所以 $\frac{e}{N}$ 的连分数展开中，某一项的收敛分数 $\frac{k}{d}$ 很可能就是我们要求的 $k$ 和 $d$。
算法步骤如下：

1. 计算 $\frac{e}{N}$ 的连分数展开。
2. 依次计算各个渐进分数 $\frac{k_i}{d_i}$。
3. 对于每一组 $(k_i,d_i)$，尝试计算 $\varphi (N)=\frac{e{d}_i-1}{k_i}$。
4. 如果得到的 $\varphi (N)$ 合理，则可以分解 $N$ 得到 $p$ 和 $q$，从而验证 $d$ 的正确性。

3. 获取私钥 d

使用 Python 进行 Wiener 攻击求解 $d$：

def isqrt(n):
    if n == 0: return 0
    x, y = n, (n + 1) // 2
    while y < x: x, y = y, (y + n // y) // 2
    return x
def continued_fractions(e, n):
    # 生成 e/n 的连分数项
    cf = []
    while n:
        cf.append(e // n)
        e, n = n, e % n
    return cf
def convergents(cf):
    # 生成分子和分母（即 k 和 d）
    n0, d0 = 0, 1
    n1, d1 = 1, 0
    for q in cf:
        n2 = q * n1 + n0
        d2 = q * d1 + d0
        yield n2, d2
        n0, d0 = n1, d1
        n1, d1 = n2, d2
def wiener_attack(e, n):
    cf = continued_fractions(e, n)
    for k, d in convergents(cf):
        if k == 0: continue
        
        # ed - 1 必须整除 k
        if (e * d - 1) % k != 0: continue
        
        phi = (e * d - 1) // k
        # p + q = n - phi + 1
        s = n - phi + 1
        # 判别式 p - q = sqrt(s^2 - 4n)
        discriminant = s * s - 4 * n
        if discriminant < 0: continue
        
        sqrt_disc = isqrt(discriminant)
        if sqrt_disc * sqrt_disc == discriminant:
            return d
    return None
d = wiener_attack(e, N)
print(f"找到私钥 d = {d}")
# 运行结果：d = 8920758995414587152829426558580025657357328745839747693739591820283538307445

4. 构造 Flag 的陷阱（关键步骤）

题目要求 Flag 的构造方式为：
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"
拿到 $d$ 后，第一反应是直接用 Python 3 跑一遍 hex(d) 并计算 MD5：

# Python 3 环境
import hashlib
d = 8920758995414587152829426558580025657357328745839747693739591820283538307445
hex_d = hex(d) 
# hex_d = '0x13b8f87d588e2aa4a27296cf2898f56ab4c8deb5a1222ec080e23afecaf7f975'
flag = "flag{" + hashlib.md5(hex_d.encode()).hexdigest() + "}"
# 结果：flag{8159e6c4abdd3b94ce461ed9a1a24017}

然而，提交后发现答案错误！
这里隐藏着一个经典 CTF 陷阱：Python 版本差异。
题目来源于较早的 CTF 比赛或环境，当时普遍使用 Python 2。
在 Python 2 中，长整型的 hex() 输出会在末尾加上一个 L 后缀：

# Python 2 环境
d = 8920758995414587152829426558580025657357328745839747693739591820283538307445L
print hex(d)
# 输出：0x13b8f87d588e2aa4a27296cf2898f56ab4c8deb5a1222ec080e23afecaf7f975L

注意到末尾的 L 了吗？这就是导致 MD5 值完全不同的原因。题目源码 hashlib.md5(hex(d)) 在 Python 2 下计算的是包含 L 的字符串的哈希值。

5. 最终求解

我们在 Python 3 中手动加上 L 来模拟 Python 2 的行为：

import hashlib
d = 8920758995414587152829426558580025657357328745839747693739591820283538307445
# 模拟 Python 2 的 hex(d) 输出，末尾带 'L'
hex_d_py2 = hex(d) + 'L' 
# 字符串内容：'0x13b8f87d588e2aa4a27296cf2898f56ab4c8deb5a1222ec080e23afecaf7f975L'
md5_hash = hashlib.md5(hex_d_py2.encode()).hexdigest()
flag = "flag{" + md5_hash + "}"
print(f"Hex String: {hex_d_py2}")
print(f"MD5 Hash: {md5_hash}")
print(f"Flag: {flag}")

输出结果：

Hex String: 0x13b8f87d588e2aa4a27296cf2898f56ab4c8deb5a1222ec080e23afecaf7f975L
MD5 Hash: 47bf28da384590448e0b0d23909a25a4
Flag: flag{47bf28da384590448e0b0d23909a25a4}

Flag

flag{47bf28da384590448e0b0d23909a25a4}

完整代码

import hashlib

def isqrt(n):
    """整数平方根（牛顿迭代法），确保返回整数"""
    if n == 0:
        return 0
    x, y = n, (n + 1) // 2
    while y < x:
        x, y = y, (y + n // y) // 2
    return x

def continued_fractions(e, n):
    """生成 e/n 的连分数项"""
    cf = []
    while n:
        cf.append(e // n)
        e, n = n, e % n
    return cf

def convergents(cf):
    """生成连分数的渐进分数（分子k，分母d）"""
    n0, d0 = 0, 1  # 初始值 h_-1=0, k_-1=1
    n1, d1 = 1, 0  # 初始值 h_0=1, k_0=0
    for q in cf:
        n2 = q * n1 + n0
        d2 = q * d1 + d0
        yield n2, d2
        # 更新迭代值
        n0, d0 = n1, d1
        n1, d1 = n2, d2

def wiener_attack(e, n):
    """Wiener攻击求解私钥d"""
    cf = continued_fractions(e, n)
    for k, d in convergents(cf):
        if k == 0:
            continue
        
        # 验证 ed - 1 能被k整除（核心条件）
        if (e * d - 1) % k != 0:
            continue
        
        # 计算phi(N)
        phi = (e * d - 1) // k
        # 计算p+q = n - phi + 1
        s = n - phi + 1
        # 判别式：(p-q)^2 = s^2 - 4n
        discriminant = s * s - 4 * n
        if discriminant < 0:
            continue
        
        # 验证判别式是完全平方数
        sqrt_disc = isqrt(discriminant)
        if sqrt_disc * sqrt_disc == discriminant:
            return d
    return None

# ===================== 题目给定的公钥参数 =====================
N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085

# ===================== 第一步：Wiener攻击求解d =====================
print("开始执行Wiener攻击...")
d = wiener_attack(e, N)
if d is None:
    print("Wiener攻击失败，未找到私钥d")
else:
    print(f"找到私钥 d = {d}")

    # ===================== 第二步：模拟Python2生成正确Flag =====================
    # Python2中hex(d)会在末尾带L，需手动拼接
    hex_d_py2 = hex(d) + 'L'
    # 计算MD5哈希（注意encode()转换为bytes）
    md5_hash = hashlib.md5(hex_d_py2.encode()).hexdigest()
    # 构造最终Flag
    flag = f"flag{{{md5_hash}}}"

    # 输出关键信息
    print(f"\nPython2风格的hex(d)：{hex_d_py2}")
    print(f"MD5哈希值：{md5_hash}")
    print(f"\n最终Flag：{flag}")

运行结果

开始执行Wiener攻击...
找到私钥 d = 8920758995414587152829426558580025657357328745839747693739591820283538307445

Python2风格的hex(d)：0x13b8f87d588e2aa4a27296cf2898f56ab4c8deb5a1222ec080e23afecaf7f975L
MD5哈希值：47bf28da384590448e0b0d23909a25a4

最终Flag：flag{47bf28da384590448e0b0d23909a25a4}

总结

这道题虽然考察的是经典的 Wiener 攻击，但难点在于最后一步的环境差异。CTF 中的旧题目往往带有 Python 2 的痕迹，遇到 hex()、print 语句或字符串编码问题时，转换一下思路，考虑一下 Python 2 的特性，往往能找到突破口。