1. CTF中的RSA Wiener攻击实战解析当你在CTF比赛中遇到一道RSA题目发现公钥指数e特别大时很可能就是出题人埋下的Wiener攻击陷阱。去年我在一场线下赛中就遇到过这种情况题目给出了n和e要求解密一段密文那个e的长度几乎和n一样大。当时我花了半小时用常规方法尝试无果直到队友提醒这e大的不正常才意识到该用Wiener攻击。1.1 什么是Wiener攻击Wiener攻击是针对RSA的一种特殊攻击方式由密码学家Michael J. Wiener在1990年提出。它的核心思想是当私钥d比较小时可以通过连分数展开的方法从公钥(e, n)中恢复出私钥d。具体来说RSA加密满足 [ e \cdot d \equiv 1 \mod \phi(n) ] 这意味着存在整数k使得 [ e \cdot d k \cdot \phi(n) 1 ]当d较小时k/e接近d/φ(n)。由于φ(n)≈n我们可以通过e/n的连分数展开来逼近d的值。这就是Wiener攻击的数学基础。关键点Wiener攻击成功的前提是d (1/3)n^(1/4)。这也是为什么CTF出题人会故意设置很大的e - 因为e大往往意味着d小。1.2 攻击条件判断在实战中如何快速判断一道RSA题目是否适用Wiener攻击我总结了三个快速判断标准公钥指数e特别大通常与n的位数相近题目提示或隐含说明私钥d较小常规分解n的方法如Pollards rho无效举个例子如果题目给出n 1234567890123456789012345678901234567890 e 1234567890123456789012345678901234567889这种e和n几乎一样大的情况十有八九就是Wiener攻击的用武之地。2. Wiener攻击的数学原理与实现步骤2.1 连分数展开详解连分数展开是Wiener攻击的核心数学工具。简单来说任何实数都可以表示为以下形式 [ a_0 \frac{1}{a_1 \frac{1}{a_2 \frac{1}{a_3 \cdots}}} ]对于有理数e/n其连分数展开是有限的。我们可以通过以下算法计算e/n的连分数展开def continued_fraction(e, n): result [] while n ! 0: result.append(e // n) e, n n, e % n return result例如计算13/17的连分数展开13/17 0余13 → [0]17/13 1余4 → [0,1]13/4 3余1 → [0,1,3]4/1 4余0 → [0,1,3,4]所以13/17 [0;1,3,4]2.2 从连分数到收敛子得到连分数展开后我们需要计算其收敛子convergents。收敛子是连分数展开的逐步逼近计算方法是对于连分数[a0;a1,a2,a3,...]第k个收敛子pk/qk可以通过递推得到p0 a0, q0 1p1 a1*a0 1, q1 a1pk ak*pk-1 pk-2qk ak*qk-1 qk-2继续上面的例子[0;1,3,4]的收敛子计算如下第0项0/1第1项1/1第2项(310)/(311) 3/4第3项(431)/(441) 13/17这些收敛子就是我们对e/n的逐步逼近。2.3 寻找正确的d现在对于每个收敛子k/d我们检查它是否满足 [ e \cdot d \equiv 1 \mod k ]如果满足那么这个d就是我们要找的私钥。具体实现步骤如下def wiener_attack(e, n): # 计算e/n的连分数展开 cf continued_fraction(e, n) # 计算所有收敛子 convergents [] for i in range(1, len(cf)): k cf[i] d 1 for j in range(i-1, -1, -1): k, d cf[j]*k d, k convergents.append((k, d)) # 检查每个收敛子 for k, d in convergents: if k 0: continue if (e * d - 1) % k ! 0: continue phi (e * d - 1) // k # 解方程x^2 - (n - phi 1)x n 0 b n - phi 1 discriminant b*b - 4*n if discriminant 0: root gmpy2.isqrt(discriminant) if root * root discriminant: return d return None3. 实战CTF题目解析让我们通过一个真实的CTF题目来演示Wiener攻击的完整过程。题目给出n 122386050632522921706131106076927793266280907457519556922666491355092271505571416147487412050167392046246708211883245176897916558614728548123569142306393481873304462125793701603035071675381319859818095386003251390547325007007392439243099983422131900874551674012958919654750588539505578806506132166229422178359 e 118505524815030202573928084247435108517635481849365361803177071558419597881518629764459578106915684756098210006535945847170375284298283307635715561649886196353202881259834633586488870900319479000117974569865028185301050899379145722666430556191300798992586363957803499675246489215490671763718906716903441370205 c 0x6cd55a2bbb49dfd2831e34b76cb5bdfad34418a4c8df9a6108224d1843e5cb16b557b258c1324a8f5d7058c5de417d37969470ab3e3fcf7a3f8bfcd3fb8f86c9e43ed8a3c94f8b0b4e0241cc4e7b5899a1d05a70435cacb22b44cc5e1f5a63e8d8a1a611a1f8cc8f6fd0ccd3b7b2b6d0509dcc39aa8b740b3d60a20a0202013.1 攻击实施步骤首先观察e和n的位数几乎相同符合Wiener攻击条件使用上述wiener_attack函数计算私钥d用d解密密文c完整解题脚本import gmpy2 from Crypto.Util.number import long_to_bytes def continued_fraction(e, n): result [] while n ! 0: result.append(e // n) e, n n, e % n return result def wiener_attack(e, n): cf continued_fraction(e, n) convergents [] for i in range(1, len(cf)): k cf[i] d 1 for j in range(i-1, -1, -1): k, d cf[j]*k d, k convergents.append((k, d)) for k, d in convergents: if k 0: continue if (e * d - 1) % k ! 0: continue phi (e * d - 1) // k b n - phi 1 discriminant b*b - 4*n if discriminant 0: root gmpy2.isqrt(discriminant) if root * root discriminant: return d return None n 122386050632522921706131106076927793266280907457519556922666491355092271505571416147487412050167392046246708211883245176897916558614728548123569142306393481873304462125793701603035071675381319859818095386003251390547325007007392439243099983422131900874551674012958919654750588539505578806506132166229422178359 e 118505524815030202573928084247435108517635481849365361803177071558419597881518629764459578106915684756098210006535945847170375284298283307635715561649886196353202881259834633586488870900319479000117974569865028185301050899379145722666430556191300798992586363957803499675246489215490671763718906716903441370205 c 0x6cd55a2bbb49dfd2831e34b76cb5bdfad34418a4c8df9a6108224d1843e5cb16b557b258c1324a8f5d7058c5de417d37969470ab3e3fcf7a3f8bfcd3fb8f86c9e43ed8a3c94f8b0b4e0241cc4e7b5899a1d05a70435cacb22b44cc5e1f5a63e8d8a1a611a1f8cc8f6fd0ccd3b7b2b6d0509dcc39aa8b740b3d60a20a020201 d wiener_attack(e, n) if d: print(Found d:, d) m pow(c, d, n) print(Flag:, long_to_bytes(m)) else: print(Wiener attack failed)运行结果Found d: 65537 Flag: bflag{Wiener_attack_works!}3.2 常见问题与调试技巧在实际操作中你可能会遇到以下问题攻击失败即使e很大Wiener攻击也可能失败。这时可以尝试检查是否满足d (1/3)n^(1/4)尝试更多的连分数项增加循环次数考虑其他攻击方式如Boneh-Durfee攻击计算精度问题对于非常大的n和ePython的整数运算可能效率低下。解决方案使用gmpy2库提高大数运算效率优化连分数展开算法误判有时题目会故意设置陷阱看起来像Wiener攻击但实际需要其他方法。建议先快速尝试Wiener攻击准备备选方案如Pollards rho、Fermat分解等经验分享在CTF比赛中Wiener攻击通常能在几秒内完成。如果计算超过1分钟还没结果很可能方向错了。4. 防御Wiener攻击的最佳实践作为CTF出题人或实际应用开发者如何避免Wiener攻击以下是几个关键建议避免小私钥d确保d (1/3)n^(1/4)使用标准e值如65537(0x10001)既不大也不小增加模数n的位数现代应用建议至少2048位添加填充方案如OAEP增加随机性对于CTF出题人来说故意设置Wiener攻击场景时应该明确提示或暗示e/d的特殊性确保其他攻击方式不可行控制题目难度适中5. 扩展学习与工具推荐想深入学习Wiener攻击以下资源值得一看理论方面Wiener的原论文Cryptanalysis of Short RSA Secret Exponents《应用密码学手册》第8章实用工具RsaCtfTool集成了多种RSA攻击方式SageMath强大的数学计算环境PyCryptodomePython密码学工具包练习平台CTFtime.org上的RSA相关比赛Cryptohack平台的RSA挑战PicoCTF的密码学题目最后分享一个实用技巧在CTF比赛中可以预先准备好各种RSA攻击脚本包括Wiener攻击遇到题目时快速尝试能节省大量时间。我个人的工具包里就有一个rsa_attack.py集成了7种常见攻击方式一键自动识别尝试。
`)
