1. 项目概述

最近在复盘去年宁波“天一永安杯”网络安全竞赛的一道Crypto题目，核心考点是RSA的低解密指数攻击，也就是经典的Wiener‘s Attack。这道题目的设计非常典型，公钥指数e长得离谱，几乎和模数n一样大，这几乎是Wiener攻击的“身份证”。很多刚接触密码学的朋友，一看到这种e和n长度相近的情况，可能第一反应是“这怎么解？”，或者试图去分解n，但往往无功而返。实际上，这正是出题人留下的一个精巧的“陷阱”或者说“提示”。通过这道题，我们可以深入理解RSA算法中，为了提升解密速度而使用小私钥d所带来的安全隐患，并掌握一种基于连分数理论的优雅攻击方法。这篇文章，我将从一个实战解题者的角度，完整拆解这道题的解题思路、背后的数学原理、代码实现细节，并分享我在复现过程中遇到的一些坑和调试技巧。无论你是CTF新手，还是想巩固RSA攻击知识的老手，相信都能从中获得一些实用的经验。

2. 低指数RSA与Wiener攻击原理深度解析

2.1 RSA算法回顾与安全隐患点

在深入Wiener攻击之前，我们有必要快速回顾一下标准的RSA算法流程，并明确其安全性的几个关键假设。RSA的安全性基于大整数分解的困难性，但这是有前提条件的。标准的密钥生成过程如下：

1. 选择两个大素数 p 和 q。
2. 计算模数 n = p * q。
3. 计算欧拉函数 φ(n) = (p-1)*(q-1)。
4. 选择一个公钥指数 e，满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。
5. 计算私钥指数 d，使得 e * d ≡ 1 (mod φ(n))。

这里的安全假设是：攻击者只知道公钥 (n, e)，而无法获知私钥 d 或分解 n。然而，这个假设成立的前提是所有的参数都选择得“足够好”。如果参数选择不当，即使不分解n，也可能直接计算出d。Wiener攻击攻击的就是其中一种不当选择：私钥d过小。

为什么有人会用小的d？这完全是出于性能考虑。在RSA解密或签名生成过程中，需要进行模幂运算 m = c^d mod n。指数d的大小直接决定了运算时间。在一些计算能力受限的环境中（如早期的智能卡、嵌入式设备），使用一个较小的d可以显著加快解密速度。这道赛题正是模拟了这种场景，出题人故意使用了一个很大的e来对应一个很小的d，从而引入了漏洞。

2.2 Wiener攻击的核心数学思想：从等式到逼近

Wiener攻击的精妙之处在于，它并不试图暴力破解或直接进行数学求解，而是利用数论中的“连分数逼近”理论，从一个看似无关的公开信息 e/n 中，巧妙地“猜出”私钥 d。

攻击的起点是RSA的基本等式：e * d = k * φ(n) + 1。其中k是某个正整数。 我们对这个等式做一个简单的变换：e * d - k * φ(n) = 1。

现在，我们把目光投向 φ(n)。我们知道 φ(n) = (p-1)(q-1) = n - (p+q) + 1。由于p和q都是大素数，p+q相对于n来说是非常小的（数量级约为 √n）。因此，φ(n) 非常接近于 n。我们可以做一个近似：φ(n) ≈ n。

将这个近似代入上面的等式：e * d - k * n ≈ 1。 然后，我们在等式两边同时除以 d * n，得到：e/n - k/d ≈ 1/(d*n)。

由于d和n都很大，右边 1/(d*n) 是一个非常接近于0的数。这意味着，分数 e/n 非常接近于分数 k/d。换句话说，k/d 是 e/n 的一个“极好”的有理数逼近。

关键理解：这里“极好”的逼近不是随便说的。在数论中，如果一个有理数 a/b 是另一个实数 x 的“很好”的逼近，那么 a/b 必然会出现在 x 的连分数展开的某个渐近分数中。Wiener的贡献在于，他严格证明了，在 d 小于 n^(1/4)/3 的条件下，k/d必定是 e/n 的连分数展开中的某一个渐近分数。

因此，攻击思路就清晰了：

1. 计算 e/n 的连分数展开。
2. 遍历这个连分数展开产生的每一个渐近分数。
3. 每个渐近分数都对应着一对可能的 (k, d)。
4. 用这对 (k, d) 和已知的 e, n，尝试反推 φ(n) 并验证是否能成功分解 n。如果能，那么我们就找到了正确的 d。

2.3 攻击成立的条件与题目特征识别

理解攻击原理后，我们就能明白为什么这道题的参数如此“扎眼”。题目给出的 e 和 n 长度几乎一致，这是一个强烈的信号。我们来分析一下：

• 条件：d < (1/3) * n^(1/4)
• 由 ed ≈ kφ(n) ≈ k*n，且 e 和 n 位数相同，可知 e 和 n 处于同一数量级。
• 假设 e ≈ n，那么 ed ≈ kn => d ≈ k。因为 d 很小，所以 k 也很小。
• 从等式 ed = kφ(n)+1 看，如果 k 很小，而 e 很大，那么 d 就必须非常小，才能让乘积 e*d 不至于太大。这正好符合 d 很小的条件。

所以，当你看到一个RSA题目，公钥 e 大得异常（比如长达上千位，和 n 差不多长），你首先就应该怀疑这是不是一道Wiener攻击题。这是一种非常重要的“题感”，需要在大量练习中培养。

3. 解题实战：从理论到代码的完整实现

3.1 题目数据与初步分析

我们拿到题目的数据通常是这样三个部分：

• n: 一个非常大的合数（模数）。
• e: 一个非常大的公钥指数（异常大）。
• c: 密文。

以一道典型的练习题为例（数据已做处理，原理相同）：

e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517 n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827 c = 6423785507684416773666948899915169554070001400671738254418895224701431744592066315840324501358322894303666459029450295999767148813342646167264341287124393625378316616139863708766163081219598771527606199602984020288261461737264281249264845116375731213029934802447231553854792109268285484082449452535764527888708733739012186167288822598437102840518848315984522212122067222074782253835923782275677317977038532227511279242281012000471845266622423324215667858024608033813931825929847132259909037530308932262269043122554140838785194939880489778556772907801622627958920544315663033749462060571279761917620516943658053070420

第一步永远是观察。这里的 e 是 617 位，n 是 617 位，两者长度完全相同。这几乎就是 Wiener 攻击的“官方认证”。我们的目标就是利用 (n, e) 恢复出私钥 d，然后解密 c。

3.2 连分数展开与渐近分数计算

连分数展开是Wiener攻击的核心工具。对于一个有理数或实数 x，其连分数展开形式为： x = a0 + 1/(a1 + 1/(a2 + 1/(a3 + ...))) 其中 a0 是整数部分，a1, a2, a3... 都是正整数。

计算 e/n 的连分数展开，本质上就是进行欧几里得算法（辗转相除法）。在Python中，我们可以这样实现：

def get_continued_fraction(a, b): """ 计算 a/b 的连分数展开序列 [a0, a1, a2, ...] """ frac = [] while b: frac.append(a // b) # 取商 a, b = b, a % b # 辗转相除 return frac

对于题目中的 e 和 n，调用get_continued_fraction(e, n)会得到一个很长的整数列表。这个列表的前面若干项，就包含了我们需要的渐近分数。

接下来，我们需要根据连分数展开序列，逐步重建出每一个渐近分数。渐近分数就是取连分数展开的前 i 项，然后计算其值。计算过程是一个从内到外的分数化简过程。这里有一个高效的迭代计算方法：

def convergents_from_continued_fraction(frac): """ 根据连分数展开序列 frac，生成所有渐近分数 (分子, 分母)。 使用递推公式： h_{-2}=0, h_{-1}=1 k_{-2}=1, k_{-1}=0 h_i = a_i * h_{i-1} + h_{i-2} k_i = a_i * k_{i-1} + k_{i-2} 则第i个渐近分数为 h_i / k_i。 """ h_2, h_1 = 0, 1 # h_{i-2}, h_{i-1} k_2, k_1 = 1, 0 # k_{i-2}, k_{i-1} for a in frac: h = a * h_1 + h_2 k = a * k_1 + k_2 yield h, k h_2, h_1 = h_1, h k_2, k_1 = k_1, k

这个生成器会依次产生 e/n 的各个渐近分数。每一个渐近分数 (h_i, k_i) 都对应着 Wiener 攻击中一个可能的 (k, d) 对。注意，这里渐近分数的分子 h_i 对应着 k，分母 k_i 对应着 d。

3.3 候选验证与私钥恢复

拿到一系列 (k, d) 候选对后，我们不能盲目地认为第一个就是正确的。我们需要一个验证机制。验证的思路是：如果当前的 (k, d) 是正确的，那么根据等式 ed = kφ(n) + 1，我们可以反推出 φ(n) = (e*d - 1) / k。这个结果必须是整数。

得到 φ(n) 后，我们可以利用它与 n 的关系来分解 n。我们知道： φ(n) = n - (p+q) + 1 设 s = p+q = n - φ(n) + 1。 又因为 n = pq。 所以 p 和 q 是方程 x^2 - sx + n = 0 的两个根。 判断这个一元二次方程的判别式 Δ = s^2 - 4n 是否为一个完全平方数，如果是，则说明我们找到了正确的 p 和 q，从而也验证了 d 是正确的。

将这个过程写成代码：

import gmpy2 from Crypto.Util.number import long_to_bytes def wiener_attack(e, n): """ 实施Wiener攻击，返回私钥d，或分解出的p, q。 """ # 1. 计算 e/n 的连分数展开 cf = get_continued_fraction(e, n) # 2. 遍历所有渐近分数 for h, k in convergents_from_continued_fraction(cf): # h 对应 k（论文中的），k 对应 d（私钥） if k == 0: # 分母为0无意义 continue # 3. 检查等式 e*d = k*phi + 1 是否（近似）成立 # 即检查 (e*k - 1) 是否能被 h 整除，这里注意对应关系：渐近分数 h/k 对应 (k_candidate)/d_candidate # 所以我们的 d_candidate = k, k_candidate = h d_candidate = k k_candidate = h if (e * d_candidate - 1) % k_candidate != 0: continue # 4. 计算 phi phi = (e * d_candidate - 1) // k_candidate # 5. 根据 phi 和 n 求解 p, q # s = p+q = n - phi + 1 s = n - phi + 1 # 判别式 delta = s^2 - 4n delta = s * s - 4 * n if delta < 0: continue # 检查 delta 是否为完全平方数 sqrt_delta, is_perfect_square = gmpy2.iroot(delta, 2) if not is_perfect_square: continue # 6. 成功分解，计算 p 和 q p = (s + sqrt_delta) // 2 q = (s - sqrt_delta) // 2 # 简单验证 p*q == n if p * q == n: print(f"[+] Found private exponent d: {d_candidate}") print(f"[+] p = {p}") print(f"[+] q = {q}") # 也可以直接计算模逆元得到d，但这里我们已经有了d_candidate # 为了严谨，可以用phi再算一次 d = gmpy2.invert(e, phi) return int(d), int(p), int(q) # 如果遍历完都没找到 print("[-] Wiener's attack failed. Maybe d is not small enough.") return None, None, None

3.4 解密与Flag获取

一旦我们成功恢复了私钥 d（以及 p, q），解密就变得轻而易举。RSA解密就是计算 m = c^d mod n。在Python中，使用内置的pow函数即可，它支持模幂运算。

# 假设我们已经通过 wiener_attack 函数得到了 d d, p, q = wiener_attack(e, n) if d: # 解密 m = pow(c, d, n) # 将解密后的长整数转换为字节串（flag通常是可读文本） try: flag = long_to_bytes(m).decode('utf-8') print(f"[+] Decrypted message: {flag}") except UnicodeDecodeError: # 如果不是utf-8，可能是hex或bytes形式 flag_bytes = long_to_bytes(m) print(f"[+] Decrypted bytes (hex): {flag_bytes.hex()}") print(f"[+] Decrypted bytes (raw): {flag_bytes}")

运行针对题目数据的脚本，我们通常能在连分数展开的前几十项内就找到正确的 d。解密出的明文往往就包含了flag，格式可能是flag{...}、CTF{...}或者题目指定的其他格式。

4. 代码实现中的关键细节与避坑指南

4.1 大整数处理与库的选择

在CTF密码学题目中，动辄就是数百位、上千位的大整数，Python的原生整数类型虽然可以处理，但在进行模幂、开方等运算时，效率是关键。gmpy2库是处理大整数的利器，它封装了GMP库，速度远超Python原生运算。

• 安装：pip install gmpy2。在某些环境中（如在线CTF平台）可能无法安装，这时可以尝试使用libnum或纯Python实现，但性能会差很多。
• 核心函数：
  • gmpy2.iroot(a, b)：计算 a 的 b 次方根，返回一个元组(根, 是否完全方)。在验证判别式是否为完全平方数时必不可少。
  • gmpy2.invert(a, b)：计算 a 模 b 的乘法逆元，即求解 x 使得 a*x ≡ 1 (mod b)。用于根据 e 和 φ(n) 计算 d。
  • gmpy2.gcd(a, b)：计算最大公约数。
• 注意事项：gmpy2返回的对象是mpz类型，在与Python原生int类型混合运算时通常是透明的，但有时需要显式转换，比如打印或进行位操作时。使用int()包裹即可。

4.2 连分数计算的效率与精度

理论上，我们需要遍历 e/n 连分数展开产生的每一个渐近分数。对于两个617位的大整数，其连分数展开序列可能非常长。但根据Wiener定理，正确的 d 会在序列的前面部分出现。在实践中，我们通常不需要遍历超过 d 的比特长度那么多项。一个常见的优化是设置一个遍历上限，比如len(continued_fraction)或者2 * d.bit_length()。

然而，这里有一个巨大的坑：Python的整数除法//在计算连分数时，如果 e 和 n 非常接近，可能会导致连分数序列的前几项是巨大的（比如第一项 a0 = e//n 可能是1），而后续项的计算由于精度问题（实际上是大整数除法的余数仍然巨大），可能会产生一个极其漫长的序列，甚至导致循环无法在合理时间内结束。

实操心得：在实际编写攻击脚本时，我强烈建议不要直接对原始的、巨大的 e 和 n 进行连分数展开。一个更稳健的做法是，先计算一个高精度的浮点数近似值e/n，然后对这个浮点数进行连分数展开。虽然浮点数有精度限制，但对于识别渐近分数中的 k/d 已经足够了。因为 k 和 d 都是整数，只要浮点数精度足够高（比如使用decimal库设置高精度），我们就能得到正确的连分数序列前若干项。这个方法比直接处理大整数更快，也更稳定。许多现成的Wiener攻击脚本（如rsa-wiener-attack库）内部就采用了这种策略。

4.3 验证逻辑的严谨性

在验证候选对 (k, d) 时，我们的逻辑链必须严谨：

1. 整除性检查：(e*d - 1) % k == 0。这是必须满足的，否则计算出的 φ(n) 就不是整数。
2. φ(n) 合理性检查：计算出的 φ(n) 应该小于 n，且是偶数（因为 p-1 和 q-1 都是偶数）。这是一个快速的过滤条件。
3. 二次方程有理解检查：通过判别式 Δ 是否为完全平方数来验证。这是最关键的一步。使用gmpy2.iroot可以高效准确地判断。
4. 最终验证：通过求出的 p 和 q 计算 n‘ = p*q，必须严格等于原始的 n。这是防止误报的最后一道防线。

有时候，可能会遇到多个候选对都能通过前几步检查，但只有一对能通过最终的p*q == n验证。所以最后一步绝对不能省略。

4.4 解密后的数据处理

解密得到的长整数 m，需要转换为可读的字符串。通常使用Crypto.Util.number.long_to_bytes或libnum.n2s。

• 编码问题：Flag可能是UTF-8文本，也可能是ASCII，甚至是十六进制字符串的字节表示。如果直接decode('utf-8')失败，可以尝试decode('ascii')，或者先输出十六进制形式hex(m)看看结构。
• 填充问题：真实的RSA解密通常涉及填充方案（如PKCS#1 v1.5或OAEP）。但在CTF的“教科书式RSA”题目中，通常没有填充，明文 m 直接就是 flag 的整数表示。如果解密后得到一堆乱码，可以检查一下是否需要对结果进行进一步的转换或剥离填充。不过对于Wiener攻击题，明文通常就是直接的flag字符串。

5. 扩展场景与变种题型分析

掌握了基础的Wiener攻击后，我们来看看它在CTF中可能出现的其他形式。

5.1 已知部分私钥的Wiener攻击

有时题目不会直接给出超大的 e，而是给出一个正常的 e（如65537），但同时给出了私钥 d 的一部分高位或低位比特。如果已知的私钥部分足够多，并且未知部分很小，也可能通过Coppersmith等攻击方法结合Wiener攻击的思想进行破解。这要求我们对RSA的数学结构有更深的理解。

5.2 多素数RSA（Multi-prime RSA）下的Wiener攻击

标准的RSA使用两个素数 p 和 q。但有些变种使用多个素数：n = p1 * p2 * ... * pk。此时的欧拉函数 φ(n) = n * Π(1 - 1/pi)。Wiener攻击的条件d < n^(1/4)/3是基于两个素数的推导。对于多素数情况，安全边界会更小，攻击可能更容易成功，但攻击脚本中关于 φ(n) 与 n 的关系式需要调整。

5.3 Boneh-Durfee攻击：更强大的小d攻击

Wiener攻击要求 d < n^(0.25)。1999年，Boneh和Durfee提出了一种基于格规约（Lattice Reduction）的更强攻击，将边界提升到了 d < n^(0.292)。在CTF中，如果题目参数看起来像是小d攻击，但Wiener攻击失败了，可以尝试使用Boneh-Durfee攻击。工具有sage脚本或一些现成的库（如RSA-and-LLL-attacks）。Boneh-Durfee攻击的数学复杂度更高，但原理同样是利用 ed 与 kφ(n) 的近似关系，构建格基并进行LLL规约来求解小根。

5.4 与其他攻击方式的结合

一道复杂的RSA题目可能不会只考一个知识点。例如：

• 低加密指数e：与低解密指数d同时出现的情况较少，因为一个很小通常意味着另一个很大。
• 共模攻击：如果多个密文使用相同的 n 但不同的 e，且这些 e 互质，则可以恢复明文。这与Wiener攻击是独立的。
• 因子碰撞：如果两个不同的 n 共享一个质因子，可以通过计算 gcd(n1, n2) 来分解。这通常与Wiener攻击无关。

在解题时，要养成先全面观察所有给定参数的习惯，再判断最可能的攻击路径。

6. 防御措施与安全启示

从这道题我们能学到什么？不仅仅是攻击技巧，更重要的是理解如何安全地使用RSA。

1. 私钥d绝不能小：这是最直接的教训。在生成RSA密钥时，私钥d必须是一个与n位数相近的大数。绝对不能为了解密性能而牺牲安全性。现代的标准（如PKCS#1）在生成d时，通常会确保d的位数大约为n的位数。
2. 公钥e可以很小，但必须规范：公钥e小（如65537）是常见且安全的做法，因为它能加快加密和验证速度。但e必须与φ(n)互质。使用65537这样的费马素数是一个好习惯。
3. 使用标准的密钥生成库：不要自己手动实现RSA密钥生成。使用经过严格审计的密码学库（如OpenSSL,cryptography(Python),javax.crypto等）。这些库会避免所有已知的陷阱，包括小d问题。
4. 理解安全边界：Wiener攻击的边界是 d < n^(1/4)/3。对于2048位的n，这意味着d必须大于约2^512。这是一个巨大的数，任何合理的密钥生成算法都不会产生小于这个值的d。但了解这个边界有助于评估自定义或非标准实现的危险性。

7. 工具与资源推荐

1. SageMath：一个强大的数学软件系统，内置了数论、代数、离散数学等大量功能。对于Boneh-Durfee等基于格的复杂攻击，Sage是首选工具。它也有现成的wiener_attack函数。
2. RsaCtfTool：一个功能强大的CTF RSA攻击工具集，集成了数十种攻击方法，包括Wiener攻击、小q攻击、共模攻击等。在实战中，如果识别出题型，可以先用这个工具快速尝试。
3. libnum：一个轻量级的Python数论库，提供了n2s,s2n,gcd,invmod等常用函数，比gmpy2更轻便，在某些无法安装gmpy2的环境下是很好的替代。
4. 在线连分数计算器：在学习和调试阶段，可以使用在线工具计算 e/n 的连分数展开，直观地观察渐近分数。这有助于加深对攻击过程的理解。

最后，密码学攻击的学习是一个理论与实践紧密结合的过程。看懂原理只是第一步，亲手编写代码、调试脚本、解决遇到的各种边界情况和异常，才能真正掌握。这道“低指数RSA”题目是一个完美的起点，它串联起了数论、算法和代码实现。希望这篇详细的拆解能帮助你不仅解出这道题，更能建立起一套分析、解决RSA相关挑战的方法论。下次再看到长得怪异的 e 和 n，你就能会心一笑，知道该从哪里入手了。