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的安全性基于大整数分解的困难性但这是有前提条件的。标准的密钥生成过程如下选择两个大素数 p 和 q。计算模数 n p * q。计算欧拉函数 φ(n) (p-1)*(q-1)。选择一个公钥指数 e满足 1 e φ(n) 且 gcd(e, φ(n)) 1。计算私钥指数 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 - (pq) 1。由于p和q都是大素数pq相对于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 的连分数展开中的某一个渐近分数。因此攻击思路就清晰了计算 e/n 的连分数展开。遍历这个连分数展开产生的每一个渐近分数。每个渐近分数都对应着一对可能的 (k, d)。用这对 (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 - (pq) 1 设 s pq 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 pq 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([-] Wieners attack failed. Maybe d is not small enough.) return None, None, None3.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) 时我们的逻辑链必须严谨整除性检查(e*d - 1) % k 0。这是必须满足的否则计算出的 φ(n) 就不是整数。φ(n) 合理性检查计算出的 φ(n) 应该小于 n且是偶数因为 p-1 和 q-1 都是偶数。这是一个快速的过滤条件。二次方程有理解检查通过判别式 Δ 是否为完全平方数来验证。这是最关键的一步。使用gmpy2.iroot可以高效准确地判断。最终验证通过求出的 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 多素数RSAMulti-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。私钥d绝不能小这是最直接的教训。在生成RSA密钥时私钥d必须是一个与n位数相近的大数。绝对不能为了解密性能而牺牲安全性。现代的标准如PKCS#1在生成d时通常会确保d的位数大约为n的位数。公钥e可以很小但必须规范公钥e小如65537是常见且安全的做法因为它能加快加密和验证速度。但e必须与φ(n)互质。使用65537这样的费马素数是一个好习惯。使用标准的密钥生成库不要自己手动实现RSA密钥生成。使用经过严格审计的密码学库如OpenSSL,cryptography(Python),javax.crypto等。这些库会避免所有已知的陷阱包括小d问题。理解安全边界Wiener攻击的边界是 d n^(1/4)/3。对于2048位的n这意味着d必须大于约2^512。这是一个巨大的数任何合理的密钥生成算法都不会产生小于这个值的d。但了解这个边界有助于评估自定义或非标准实现的危险性。7. 工具与资源推荐SageMath一个强大的数学软件系统内置了数论、代数、离散数学等大量功能。对于Boneh-Durfee等基于格的复杂攻击Sage是首选工具。它也有现成的wiener_attack函数。RsaCtfTool一个功能强大的CTF RSA攻击工具集集成了数十种攻击方法包括Wiener攻击、小q攻击、共模攻击等。在实战中如果识别出题型可以先用这个工具快速尝试。libnum一个轻量级的Python数论库提供了n2s,s2n,gcd,invmod等常用函数比gmpy2更轻便在某些无法安装gmpy2的环境下是很好的替代。在线连分数计算器在学习和调试阶段可以使用在线工具计算 e/n 的连分数展开直观地观察渐近分数。这有助于加深对攻击过程的理解。最后密码学攻击的学习是一个理论与实践紧密结合的过程。看懂原理只是第一步亲手编写代码、调试脚本、解决遇到的各种边界情况和异常才能真正掌握。这道“低指数RSA”题目是一个完美的起点它串联起了数论、算法和代码实现。希望这篇详细的拆解能帮助你不仅解出这道题更能建立起一套分析、解决RSA相关挑战的方法论。下次再看到长得怪异的 e 和 n你就能会心一笑知道该从哪里入手了。
RSA低解密指数攻击：从Wiener攻击原理到CTF实战代码实现
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的安全性基于大整数分解的困难性但这是有前提条件的。标准的密钥生成过程如下选择两个大素数 p 和 q。计算模数 n p * q。计算欧拉函数 φ(n) (p-1)*(q-1)。选择一个公钥指数 e满足 1 e φ(n) 且 gcd(e, φ(n)) 1。计算私钥指数 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 - (pq) 1。由于p和q都是大素数pq相对于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 的连分数展开中的某一个渐近分数。因此攻击思路就清晰了计算 e/n 的连分数展开。遍历这个连分数展开产生的每一个渐近分数。每个渐近分数都对应着一对可能的 (k, d)。用这对 (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 - (pq) 1 设 s pq 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 pq 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([-] Wieners attack failed. Maybe d is not small enough.) return None, None, None3.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) 时我们的逻辑链必须严谨整除性检查(e*d - 1) % k 0。这是必须满足的否则计算出的 φ(n) 就不是整数。φ(n) 合理性检查计算出的 φ(n) 应该小于 n且是偶数因为 p-1 和 q-1 都是偶数。这是一个快速的过滤条件。二次方程有理解检查通过判别式 Δ 是否为完全平方数来验证。这是最关键的一步。使用gmpy2.iroot可以高效准确地判断。最终验证通过求出的 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 多素数RSAMulti-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。私钥d绝不能小这是最直接的教训。在生成RSA密钥时私钥d必须是一个与n位数相近的大数。绝对不能为了解密性能而牺牲安全性。现代的标准如PKCS#1在生成d时通常会确保d的位数大约为n的位数。公钥e可以很小但必须规范公钥e小如65537是常见且安全的做法因为它能加快加密和验证速度。但e必须与φ(n)互质。使用65537这样的费马素数是一个好习惯。使用标准的密钥生成库不要自己手动实现RSA密钥生成。使用经过严格审计的密码学库如OpenSSL,cryptography(Python),javax.crypto等。这些库会避免所有已知的陷阱包括小d问题。理解安全边界Wiener攻击的边界是 d n^(1/4)/3。对于2048位的n这意味着d必须大于约2^512。这是一个巨大的数任何合理的密钥生成算法都不会产生小于这个值的d。但了解这个边界有助于评估自定义或非标准实现的危险性。7. 工具与资源推荐SageMath一个强大的数学软件系统内置了数论、代数、离散数学等大量功能。对于Boneh-Durfee等基于格的复杂攻击Sage是首选工具。它也有现成的wiener_attack函数。RsaCtfTool一个功能强大的CTF RSA攻击工具集集成了数十种攻击方法包括Wiener攻击、小q攻击、共模攻击等。在实战中如果识别出题型可以先用这个工具快速尝试。libnum一个轻量级的Python数论库提供了n2s,s2n,gcd,invmod等常用函数比gmpy2更轻便在某些无法安装gmpy2的环境下是很好的替代。在线连分数计算器在学习和调试阶段可以使用在线工具计算 e/n 的连分数展开直观地观察渐近分数。这有助于加深对攻击过程的理解。最后密码学攻击的学习是一个理论与实践紧密结合的过程。看懂原理只是第一步亲手编写代码、调试脚本、解决遇到的各种边界情况和异常才能真正掌握。这道“低指数RSA”题目是一个完美的起点它串联起了数论、算法和代码实现。希望这篇详细的拆解能帮助你不仅解出这道题更能建立起一套分析、解决RSA相关挑战的方法论。下次再看到长得怪异的 e 和 n你就能会心一笑知道该从哪里入手了。
