2026/9/12 3:10:00
FEATURED · 精选文章 
1. 内容整体设计与思路拆解1.1 为什么需要一个“RSA攻击工具箱”接触过CTF、密码学竞赛或安全测试的朋友肯定有体会——RSA这套公钥加密体系表面上就是一组大整数运算但真正撞上实际难题的时候大多数人会卡在“不知道从哪个方向下手”这一步。我在实战里最常遇到的场景是这样拿到一个公钥文件和一段密文n、e都很大看起来“无懈可击”但你知道这个密码体制肯定有问题不然对方不会出这道题。这时候手头如果没有一套整理好的工具就要临时百度、翻论文、现写脚本非常耗费时间。所谓“通用RSA密码学攻击工具箱”本质上是把RSA常见攻击场景的检测、分析、利用手段整合到一起的一个工作集合它不依赖某一门特定语言或某个特定的框架而是通过对RSA参数本身的性质做快速判断自动匹配最有可能的薄弱点然后实施对应的攻击方案。好多做了一年半载CTF的选手说起分解大整数、算逆元、解同余方程都头头是道但真遇到“给了两段密文同一个模数n两个不同加密指数e1和e2”的情况未必能第一时间反应出共模攻击。而这套工具箱的核心价值正是把这类碎片化的攻击知识“模块化”让使用者可以快速验证自己的假设节省排查时间。1.2 工具箱的整体功能模块划分我给自己整理的这套工具箱内部按“信息检测—攻击模式匹配—自动执行—结果输出”四个层级做了划分。信息检测这部分主要负责从公钥文件、证书、密文数据中提取n、e、c、p、q等基本参数同时对参数本身的属性做一轮扫描比如模数位数、加密指数大小、密文数量、是否使用标准填充等。这一步是后续所有攻击的基础参数没提取干净后面全是白搭。攻击模式匹配是把常见的RSA漏洞场景整理成一个一个独立的“问题模板”比如低加密指数、共模、模数可分解、Wiener低解密指数、相关消息攻击、选择密文攻击等。检测模块跑完以后会自动把当前参数跟这些模板做比对得出一个“命中率”排序优先尝试命中率高的方案。自动执行模块就是真正跑攻击脚本的部分每一个攻击场景对应一段独立实现互不干扰。输出模块则会清晰打印出执行状态、中间量以及最终恢复出的明文或私钥参数。这套思路的最大好处在于——它不是某个单一工具而是一套“检测执行”的工作流使用者完全可以把它理解成一个安全领域里的“瑞士军刀”碰到RSA相关的密文先整体扫描一遍再瞄准弱点打而不是一上来就盲目硬刚大数分解。1.3 常见的RSA攻击场景汇总要理解工具箱为什么这样设计需要先回顾一下RSA到底有哪些经典的“翻车现场”。第一类是参数选择不当导致的攻击最常见的就是加密指数e选得太小例如e3如果明文较短且没有使用合适的填充方案直接对密文开三次方就能还原明文。另一个参数层面的典型问题就是模数n复用好几个用户共用同一个n各自有不同的e当e彼此互质时同一明文加密两次所产生的两个密文可以不用分解n就直接恢复出明文。第二类是模数分解层面的攻击当p和q选择不当比如p和q相差太近、p-1或q-1由小因子构成、使用共享素数等情况常规大数分解算法Pollard‘s p-1、Fermat分解、ECM等可以让n“不攻自破”。一旦n被成功分解私钥d基本就等于直接拿到了。第三类是侧信道和实现层面的攻击包括时序攻击、能量分析、故障注入等这类玩法在CTF中不算主流但在现实世界的安全评估里很重要如果一个系统使用的是教科书式RSA或者OpenSSL库的低版本实现攻击面会更大。把这些场景汇总起来后你会发现它们的共性是攻击者并不需要穷举RSA的数学难题本身而是利用参数生成、使用方式、协议设计的薄弱环节来做文章。这也是整个工具箱的核心理念——不硬刚数学而是去找工程实现里留下的“后门”。2. 核心攻击细节解析与实操要点2.1 低加密指数攻击的原理与限制低加密指数攻击应该是入门RSA攻击时最先遇到的一种场景。它的原理非常直观假设明文m小加密指数e也小那么c m^e mod n。如果m^e n直接对c开e次方就能得到m完全不需要考虑模数n的存在。举个例子若e3密文c123456789而n是一个至少4096位的大数那么m^3 远小于 n时对c开三次方就拿到了原始明文。这种攻击在“没有随机填充”的前提下几乎是秒破但实际应用中有很多限制条件。最需要注意的一点就是如果明文m过大开完方之后结果超过了n这条路就走不通了——此时你需要用到“Hastad广播攻击”这类变体利用多组(n, c)做中国剩余定理求解。实战中我见过有人一上来就对密文开三次方然后直接打印结果发现是一堆乱码就以为攻击失败。其实可能的原因是明文是用十六进制字符串转整数存储的开方结果需要再做一次格式转换才能看到可读内容。这一步很多新手会栽跟头。具体实现时一个最简洁的版本是import gmpy2 def low_exponent_attack(c, e): m gmpy2.iroot(c, e)[0] return m代码虽然只有三行但里面有个坑gmpy2.iroot返回的是一个元组第一个元素是整数结果第二个元素是布尔值表示是否精确开方。务必检查第二个元素是否为True否则说明密文数值并不是一个完全e次方数这时候要么n参与了运算要么加密过程有填充的干扰。2.2 共模攻击的实现与边界条件共模攻击在我接触过的CTF题目中出现频率相当高基本属于“必考项”。它利用的场景是两条不同密文c1、c2用了同一个模数n但加密指数分别是e1、e2并且gcd(e1, e2) 1。攻击者不需要分解n也不清楚私钥就能恢复出明文。数学原理核心是扩展欧几里得算法因为e1和e2互质必然存在整数s1、s2使得e1s1 e2s2 1。然后结合密文的定义c1 m^e1 mod n c2 m^e2 mod n可以推出c1^s1 * c2^s2 ≡ m^(e1*s1 e2*s2) ≡ m^1 ≡ m (mod n)这个推导很漂亮但实现的时候必须注意s1或s2出现负数的情况。负指数的含义是模逆运算Python的pow函数能直接支持负指数模运算吗实际上不能。需要先把负指数对应的底数做模逆再转换成正指数来算。我写过一个稳妥的版本import gmpy2 def common_modulus_attack(c1, c2, e1, e2, n): gcd, s1, s2 gmpy2.gcdext(e1, e2) if s1 0: c1 gmpy2.invert(c1, n) s1 -s1 if s2 0: c2 gmpy2.invert(c2, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return mgcdext返回的第一个元素是最大公约数正常情况下应该为1如果输出不为1说明e1、e2并非互质需要换一组密文或者攻击前提本身不成立。实际使用中还要考虑两条密文是否对应同一明文如果使用了随机填充如PKCS#1 v1.5每条密文的填充不同共模攻击就失效了。这也是很多人明明满足共模条件却跑不出明文的原因——题目可能在填充环节做了手脚。2.3 模数分解类攻击的检测与实操选择模数分解是RSA攻击的“终极大招”一旦n被分解成p和q整个RSA体系瞬间崩塌。攻击工具箱里这部分我做得最重因为分解n往往是最后兜底的手段也是思路最容易卡壳的地方。分解n的策略要根据p、q的生成特征来选。如果p和q很接近即差值很小使用Fermat分解法会非常快。Fermat分解的思路是把n表示成a^2 - b^2的形式从而得到(a-b)(ab) n。我处理过一组4096位的np和q只有不到30位的差距用Fermat分解几秒钟就出结果了而直接上Pollard’s rho算法可能要跑到地老天荒。如果p-1或者q-1是光滑数由许多小素数相乘Pollard‘s p-1算法效果极佳。它的原理基于费马小定理通过计算a^(B!)对n取模不断尝试与n求最大公约数一旦某个因子的全部素数幂次都在B!里出现过就能把这个因子从n中剥离出来。边界B的选择很考验经验太小了漏过因子太大了计算量暴涨。我一般先用B10000试一轮不行再往上加每次翻倍最多加到2^20为止。对于n在512位以下的情况最简单的策略反而是直接上yafu或者SageMath里的factor()函数跑一遍秒出。很多CTF题为了降低难度故意用256位、512位的n这类题目用专业分解工具比任何自己写的脚本都靠谱。我在工具箱里固定提供了一个检测函数它会先判断p与q差值的估计规模再判断n的位数最后自动决定是否先跑Fermat还是直接调yafu。这种自动分流的设计能极大减少人工试错的成本。2.4 Wiener低解密指数攻击及变体当私钥指数d选择得过小即d n^(1/4)左右时攻击者可以通过连分数展开的方式从公钥(n, e)反推出d。这种攻击叫Wiener攻击在CTF里出现频率也不低。Wiener攻击的数学基础是连分数近似。因为ed ≡ 1 (mod φ(n))所以存在整数k使得ed - kφ(n) 1两边同时除以dφ(n)可得|e/φ(n) - k/d| 1/(d*φ(n))而φ(n)和n在数值上非常接近因此可以用e/n的连分数展开来逼近k/d。遍历连分数序列的每一个收敛子测试对应的d是否能正确解密即可。Python实现通常是def continued_fraction(numerator, denominator): while denominator: a numerator // denominator yield a numerator, denominator denominator, numerator - a * denominator def wiener_attack(e, n): for a in continued_fraction(e, n): # 根据连分数项计算k和d的候选值 ...这里最核心的坑点是连分数展开产生的候选k和d并不一定都是合法解需要代入ed ≡ 1 (mod φ(n))这个条件去验证。在具体实现上可以先由k、d估算出φ(n)再用φ(n)还原出pq和p-q最后检查pq是否等于n。如果标准Wiener攻击失败还可以考虑Boneh-Durfee攻击它把问题转换成一个二维格上的最近向量问题适用范围比Wiener更广但实现复杂度也高很多。一般工具箱里我会集成SageMath的相应实现毕竟单纯用Python写格攻击的代码容易在浮点误差和基规约算法上卡壳。3. 实操过程与核心环节实现3.1 工具链的搭建与依赖选择搭建RSA攻击工具箱首先要解决“轮子”的问题。我个人最推荐的组合是Python 3.10及以上版本 PyCryptodome gmpy2 SageMath可选外加yafu作为外部的大数分解引擎。PyCryptodome主要负责RSA公钥的解析和格式转换它能直接读取PEM格式的公钥证书从中提取出模数n和加密指数e。gmpy2则负责高精度整数运算无论是开方、求逆元、扩展欧几里得都比Python原生的int运算高效太多。SageMath虽然安装体积非常大但它的数论库非常完整在做格攻击、多项式求根、椭圆曲线相关攻击时能省下大量自研时间。yafu是一个独立的大整数分解工具对中小位数模数的分解能力非常强悍对几百位以内的n更是“秒杀”级别的存在。我通常把yafu作为外部进程调用在Python里通过subprocess启动然后解析它的输出结果。这个外部接口的设计让工具箱的扩展性变得很好以后有更好的分解工具直接替换外部进程就行。3.2 公钥解析与参数提取的实操代码写工具箱的第一步就是把各种格式的公钥信息标准化。RSA公钥在CTF题目中最常见的载体是PEM文件比如一个叫pub.pem的文件里面有一段明显的Base64编码。解析的代码其实并不复杂from Crypto.PublicKey import RSA with open(pub.pem, r) as f: key RSA.import_key(f.read()) n key.n e key.e print(fn {n}) print(fe {e})如果题目给的不是PEM文件而是一串十六进制字符串那就需要先解码成整数n int(hex_str, 16) e int(hex_e, 16)这一步看似简单却有一个特别容易踩的坑有些题目给出的十六进制字符串带有0x前缀有些没有有些是大小写混合还有些中间夹杂空格或换行。我的习惯是在解析前统一做一次清理去除所有空白字符再判断是否有0x前缀这样能避免大量低级报错。提取密文时常见的格式有整数、十六进制字符串、Base64字符串以及文件中的二进制数据。最稳妥的做法是统一转换成整数。Base64转整数时先用base64.b64decode解码成字节串再用int.from_bytes(bytes_data, byteorderbig)转成整数。很多初学者喜欢直接用eval()去解析题目给的表达式这非常危险强烈不建议在工具箱里这么做。3.3 攻击参数自动检测的实现逻辑所谓“自动检测”本质是一组启发式判断逻辑。我把它做成一个函数analyze_rsa_params(n, e, ciphertexts)它会依次检查n的位数是否过小比如小于512位直接提示“可尝试暴力分解”e是否为常见小值比如3、5、17、65537的变体如果是3且密文个数为1优先低加密指数攻击是否有多条密文共用同一个n如果有两条以上且各对应不同加密指数优先共模攻击n的素数因子是否有明显的平方因子或小因子可以通过gcd(n, gmpy2.mpz(2)**10000 - 1)之类的手段探测私钥指数d的规模是否可能过小这需要基于e和n的大小关系做粗略估计。这个检测模块并不追求“一把梭”而是输出一个攻击优先级列表。比如同时满足“n太小”和“密文有两条”系统会提示先尝试分解共享的n如果分解成功直接用私钥解密所有密文这样比逐条做共模攻击更彻底。我之前处理过一个题目它的n只有384位但题目包装了一层“两层加密”的概念——先用小n的公钥加密了一个对称密钥再用对称密钥加密了真正的flag。单纯对密文做低加密指数攻击只能拿到对称密钥的密文还得再解一层。这时候自动检测的作用就体现出来了它会提醒你检查明文是否可能是可读的对称密钥。3.4 格式化输出与结果验证机制攻击完以后最怕的就是已经拿到了m的整数形式却因为格式转换不对导致结果“看上去是一堆乱码”。我在工具箱里专门设计了一个结果展示模块负责把整数形式的明文转换成可读文本。转换逻辑是这样的def int_to_text(m): try: byte_length (m.bit_length() 7) // 8 return m.to_bytes(byte_length, byteorderbig).decode(utf-8, errorsreplace) except Exception: return str(m)这个模块会优先尝试把明文按UTF-8解码如果失败再尝试Base64解码、hex解码最终才会把明文当成普通整数打印出来。实际使用中我遇到过明文本身就是十六进制字符串的情况直接转UTF-8会得到一堆不可读字符但转成hex之后立刻就能看到flag。结果验证机制也是工具箱里不可或缺的一环。拿到可能的私钥指数d之后应该立刻用它对原始密文做一次解密检查得到的明文是否可读或是否满足某个已知格式比如包含flag字样。这一步自动化程度越高越能节约人工检查的时间。4. 常见问题与排查技巧实录4.1 攻击失效时的第一排查清单我整理工具的过程中踩过数不清的坑也积累了很多排查经验。如果你的攻击脚本跑了半天却始终没出结果先不要怀疑是数学原理错了90%的情况是参数输入有误或前提条件没满足。排查顺序我建议按下面这张表来现象可能原因排查方法解密结果乱码明文格式判断错误可能是hex或Base64尝试多种格式转换检查字节序是大端还是小端低加密指数攻击失败密文并不是精确的e次方说明填充介入或明文过大改用Hastad广播攻击或者检查是否使用标准填充共模攻击失败两条密文不是同一明文或e1、e2不互质验证密文来源、确认指数间gcd值为1Wiener攻击无结果d值并没有小于n^(1/4)或连分数遍历不完整尝试Boneh-Durfee攻击作为替代Fermat分解超时p和q差距仍然过大切换Pollard’s p-1或回归yafu暴力分解程序内存溢出密文或参数过大循环次数失控给gmpy2运算加位数限制防止无限循环这中间最容易被忽略的是字节序问题。RSA数学上所有整数都是自然数没有“字节序”的概念但一旦涉及把整数转换成字节串就必须约定字节序。OpenSSL生成公钥时使用大端序Python的int.to_bytes默认也是大端但如果题目脚本里用的是小端转换解出来的内容就会倒着排列看起来像是乱码。实际上只要reverse一下字节顺序明文就正常了。4.2 工具报错的经典场景与修复方案工具箱在开发过程中最常见的报错集中在几个方面类型不匹配、模逆不存在、精度溢出、外部进程调用失败。类型不匹配这个多数是因为把gmpy2.mpz类型和Python原生int混用导致的。gmpy2的iroot、invert等函数返回的类型是mpz跟原生int可以进行运算但一些库函数会对类型做严格检查比如PyCryptodome的解密接口就只接受原生int。解决方案很简单在传给其他库之前统一用int()做一次强转。模逆不存在的报错通常是在共模攻击或者私钥求解过程中某个底数跟模数n不互质此时gmpy2.invert会抛出异常。一旦发生这种情况意味着n存在一个小因子反而是一个好消息——可以直接用这个因子分解n。我在错误处理模块里会专门捕获这个异常然后转去尝试做因数分解。外部进程调用失败也是高频问题尤其是yafu它在Windows和Linux上的可执行文件名不一样输出格式也略有差异。我在工具箱里做了一个适配层检测操作系统后自动调整调用参数并对输出做正则提取。如果你的环境里没有yafu也可以用sage的factor()替代或者直接用factordb.com的在线API做查询接口很简单HTTP请求即可。4.3 踩坑记录从失败案例中学到的经验有一次处理一个题目n是1024位e是3密文看起来很规整我一开始自信满满地跑了低加密指数攻击结果开方出来根本不是明文。折腾了很久才发现题目中做了PKCS#1 v1.5填充也就是在真正的明文前面加了一段随机前缀整个消息块被补到了和n差不多的大小所以m^3远大于n直接开方完全失效。这给我的教训是任何RSA攻击场景第一步永远是判断填充方式。如果题目明确说“使用了标准RSA库加密”那大概率有填充此时低加密指数攻击基本可以放弃了除非题目为了出题故意绕过了填充或者让你自己构造明文。这个判断做不对后面的攻击全是徒劳。还有一次共模攻击的脚本怎么都解密不对后来检查发现两条“密文”根本不是对同一明文加密的一个是加密另一个是签名场景不同直接套共模公式当然没有结果。从那天起我在工具箱的检测模块里增加了一个步骤——先对两条密文做统计测试如果它们的数值差异过大可能是明文不同此时共模攻击的前提需要重新审视。4.4 给初学者的建议与进阶路径如果你刚开始接触RSA攻击我建议不要急着把所有攻击脚本抄下来堆在一起。先扎扎实实理解RSA的数学原理尤其是欧拉函数、模逆、费马小定理这几个基础概念然后逐个攻破攻击场景。每学一个攻击方法就动手写一个小脚本然后在本地用自己构造的公钥和密文做验证。比如构造一个e3的加密环境生成一条较小的密文验证低加密指数攻击能否恢复出原文。这样一轮下来你的印象会非常深刻远比直接跑现成工具箱更能锻炼实战能力。等基础打牢了再去研究更复杂的攻击场景比如Coppersmith相关攻击、Boneh-Durfee攻击、基于格的攻击方法这些就需要SageMath的参与。这个阶段建议直接看CTF的WriteUp不光是看解题思路还要看别人在代码实现里的工程细节比如参数怎么归一化、结果怎么转换为可读文本、异常怎么处理——这些细节往往比核心攻击算法更能决定你是否能顺利完成闭环。我个人还有一个习惯是给每个攻击脚本都写一个“使用前提”的注释块记录这个攻击为什么能成功、需要满足什么条件、什么情况下会失败。时间久了这就变成了自己的知识库比任何网上现成的工具包都好用。从最初的“只会拿现成命令跑一跑”到如今能根据参数特征快速匹配攻击路径这套工具箱带给我的不只是效率提升更是一种对RSA密码体制整体弱点的系统认知。安全攻防本来就是一个不断了解对手弱点的过程RSA虽然几十年历经考验但工程实现里的疏忽永远存在。趁手的工具能让你更快地发现漏洞、理解漏洞而这恰恰是每个密码学安全从业者都应该具备的基本功。
RSA攻击工具箱：从原理到实战的密码学安全指南
1. 内容整体设计与思路拆解1.1 为什么需要一个“RSA攻击工具箱”接触过CTF、密码学竞赛或安全测试的朋友肯定有体会——RSA这套公钥加密体系表面上就是一组大整数运算但真正撞上实际难题的时候大多数人会卡在“不知道从哪个方向下手”这一步。我在实战里最常遇到的场景是这样拿到一个公钥文件和一段密文n、e都很大看起来“无懈可击”但你知道这个密码体制肯定有问题不然对方不会出这道题。这时候手头如果没有一套整理好的工具就要临时百度、翻论文、现写脚本非常耗费时间。所谓“通用RSA密码学攻击工具箱”本质上是把RSA常见攻击场景的检测、分析、利用手段整合到一起的一个工作集合它不依赖某一门特定语言或某个特定的框架而是通过对RSA参数本身的性质做快速判断自动匹配最有可能的薄弱点然后实施对应的攻击方案。好多做了一年半载CTF的选手说起分解大整数、算逆元、解同余方程都头头是道但真遇到“给了两段密文同一个模数n两个不同加密指数e1和e2”的情况未必能第一时间反应出共模攻击。而这套工具箱的核心价值正是把这类碎片化的攻击知识“模块化”让使用者可以快速验证自己的假设节省排查时间。1.2 工具箱的整体功能模块划分我给自己整理的这套工具箱内部按“信息检测—攻击模式匹配—自动执行—结果输出”四个层级做了划分。信息检测这部分主要负责从公钥文件、证书、密文数据中提取n、e、c、p、q等基本参数同时对参数本身的属性做一轮扫描比如模数位数、加密指数大小、密文数量、是否使用标准填充等。这一步是后续所有攻击的基础参数没提取干净后面全是白搭。攻击模式匹配是把常见的RSA漏洞场景整理成一个一个独立的“问题模板”比如低加密指数、共模、模数可分解、Wiener低解密指数、相关消息攻击、选择密文攻击等。检测模块跑完以后会自动把当前参数跟这些模板做比对得出一个“命中率”排序优先尝试命中率高的方案。自动执行模块就是真正跑攻击脚本的部分每一个攻击场景对应一段独立实现互不干扰。输出模块则会清晰打印出执行状态、中间量以及最终恢复出的明文或私钥参数。这套思路的最大好处在于——它不是某个单一工具而是一套“检测执行”的工作流使用者完全可以把它理解成一个安全领域里的“瑞士军刀”碰到RSA相关的密文先整体扫描一遍再瞄准弱点打而不是一上来就盲目硬刚大数分解。1.3 常见的RSA攻击场景汇总要理解工具箱为什么这样设计需要先回顾一下RSA到底有哪些经典的“翻车现场”。第一类是参数选择不当导致的攻击最常见的就是加密指数e选得太小例如e3如果明文较短且没有使用合适的填充方案直接对密文开三次方就能还原明文。另一个参数层面的典型问题就是模数n复用好几个用户共用同一个n各自有不同的e当e彼此互质时同一明文加密两次所产生的两个密文可以不用分解n就直接恢复出明文。第二类是模数分解层面的攻击当p和q选择不当比如p和q相差太近、p-1或q-1由小因子构成、使用共享素数等情况常规大数分解算法Pollard‘s p-1、Fermat分解、ECM等可以让n“不攻自破”。一旦n被成功分解私钥d基本就等于直接拿到了。第三类是侧信道和实现层面的攻击包括时序攻击、能量分析、故障注入等这类玩法在CTF中不算主流但在现实世界的安全评估里很重要如果一个系统使用的是教科书式RSA或者OpenSSL库的低版本实现攻击面会更大。把这些场景汇总起来后你会发现它们的共性是攻击者并不需要穷举RSA的数学难题本身而是利用参数生成、使用方式、协议设计的薄弱环节来做文章。这也是整个工具箱的核心理念——不硬刚数学而是去找工程实现里留下的“后门”。2. 核心攻击细节解析与实操要点2.1 低加密指数攻击的原理与限制低加密指数攻击应该是入门RSA攻击时最先遇到的一种场景。它的原理非常直观假设明文m小加密指数e也小那么c m^e mod n。如果m^e n直接对c开e次方就能得到m完全不需要考虑模数n的存在。举个例子若e3密文c123456789而n是一个至少4096位的大数那么m^3 远小于 n时对c开三次方就拿到了原始明文。这种攻击在“没有随机填充”的前提下几乎是秒破但实际应用中有很多限制条件。最需要注意的一点就是如果明文m过大开完方之后结果超过了n这条路就走不通了——此时你需要用到“Hastad广播攻击”这类变体利用多组(n, c)做中国剩余定理求解。实战中我见过有人一上来就对密文开三次方然后直接打印结果发现是一堆乱码就以为攻击失败。其实可能的原因是明文是用十六进制字符串转整数存储的开方结果需要再做一次格式转换才能看到可读内容。这一步很多新手会栽跟头。具体实现时一个最简洁的版本是import gmpy2 def low_exponent_attack(c, e): m gmpy2.iroot(c, e)[0] return m代码虽然只有三行但里面有个坑gmpy2.iroot返回的是一个元组第一个元素是整数结果第二个元素是布尔值表示是否精确开方。务必检查第二个元素是否为True否则说明密文数值并不是一个完全e次方数这时候要么n参与了运算要么加密过程有填充的干扰。2.2 共模攻击的实现与边界条件共模攻击在我接触过的CTF题目中出现频率相当高基本属于“必考项”。它利用的场景是两条不同密文c1、c2用了同一个模数n但加密指数分别是e1、e2并且gcd(e1, e2) 1。攻击者不需要分解n也不清楚私钥就能恢复出明文。数学原理核心是扩展欧几里得算法因为e1和e2互质必然存在整数s1、s2使得e1s1 e2s2 1。然后结合密文的定义c1 m^e1 mod n c2 m^e2 mod n可以推出c1^s1 * c2^s2 ≡ m^(e1*s1 e2*s2) ≡ m^1 ≡ m (mod n)这个推导很漂亮但实现的时候必须注意s1或s2出现负数的情况。负指数的含义是模逆运算Python的pow函数能直接支持负指数模运算吗实际上不能。需要先把负指数对应的底数做模逆再转换成正指数来算。我写过一个稳妥的版本import gmpy2 def common_modulus_attack(c1, c2, e1, e2, n): gcd, s1, s2 gmpy2.gcdext(e1, e2) if s1 0: c1 gmpy2.invert(c1, n) s1 -s1 if s2 0: c2 gmpy2.invert(c2, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return mgcdext返回的第一个元素是最大公约数正常情况下应该为1如果输出不为1说明e1、e2并非互质需要换一组密文或者攻击前提本身不成立。实际使用中还要考虑两条密文是否对应同一明文如果使用了随机填充如PKCS#1 v1.5每条密文的填充不同共模攻击就失效了。这也是很多人明明满足共模条件却跑不出明文的原因——题目可能在填充环节做了手脚。2.3 模数分解类攻击的检测与实操选择模数分解是RSA攻击的“终极大招”一旦n被分解成p和q整个RSA体系瞬间崩塌。攻击工具箱里这部分我做得最重因为分解n往往是最后兜底的手段也是思路最容易卡壳的地方。分解n的策略要根据p、q的生成特征来选。如果p和q很接近即差值很小使用Fermat分解法会非常快。Fermat分解的思路是把n表示成a^2 - b^2的形式从而得到(a-b)(ab) n。我处理过一组4096位的np和q只有不到30位的差距用Fermat分解几秒钟就出结果了而直接上Pollard’s rho算法可能要跑到地老天荒。如果p-1或者q-1是光滑数由许多小素数相乘Pollard‘s p-1算法效果极佳。它的原理基于费马小定理通过计算a^(B!)对n取模不断尝试与n求最大公约数一旦某个因子的全部素数幂次都在B!里出现过就能把这个因子从n中剥离出来。边界B的选择很考验经验太小了漏过因子太大了计算量暴涨。我一般先用B10000试一轮不行再往上加每次翻倍最多加到2^20为止。对于n在512位以下的情况最简单的策略反而是直接上yafu或者SageMath里的factor()函数跑一遍秒出。很多CTF题为了降低难度故意用256位、512位的n这类题目用专业分解工具比任何自己写的脚本都靠谱。我在工具箱里固定提供了一个检测函数它会先判断p与q差值的估计规模再判断n的位数最后自动决定是否先跑Fermat还是直接调yafu。这种自动分流的设计能极大减少人工试错的成本。2.4 Wiener低解密指数攻击及变体当私钥指数d选择得过小即d n^(1/4)左右时攻击者可以通过连分数展开的方式从公钥(n, e)反推出d。这种攻击叫Wiener攻击在CTF里出现频率也不低。Wiener攻击的数学基础是连分数近似。因为ed ≡ 1 (mod φ(n))所以存在整数k使得ed - kφ(n) 1两边同时除以dφ(n)可得|e/φ(n) - k/d| 1/(d*φ(n))而φ(n)和n在数值上非常接近因此可以用e/n的连分数展开来逼近k/d。遍历连分数序列的每一个收敛子测试对应的d是否能正确解密即可。Python实现通常是def continued_fraction(numerator, denominator): while denominator: a numerator // denominator yield a numerator, denominator denominator, numerator - a * denominator def wiener_attack(e, n): for a in continued_fraction(e, n): # 根据连分数项计算k和d的候选值 ...这里最核心的坑点是连分数展开产生的候选k和d并不一定都是合法解需要代入ed ≡ 1 (mod φ(n))这个条件去验证。在具体实现上可以先由k、d估算出φ(n)再用φ(n)还原出pq和p-q最后检查pq是否等于n。如果标准Wiener攻击失败还可以考虑Boneh-Durfee攻击它把问题转换成一个二维格上的最近向量问题适用范围比Wiener更广但实现复杂度也高很多。一般工具箱里我会集成SageMath的相应实现毕竟单纯用Python写格攻击的代码容易在浮点误差和基规约算法上卡壳。3. 实操过程与核心环节实现3.1 工具链的搭建与依赖选择搭建RSA攻击工具箱首先要解决“轮子”的问题。我个人最推荐的组合是Python 3.10及以上版本 PyCryptodome gmpy2 SageMath可选外加yafu作为外部的大数分解引擎。PyCryptodome主要负责RSA公钥的解析和格式转换它能直接读取PEM格式的公钥证书从中提取出模数n和加密指数e。gmpy2则负责高精度整数运算无论是开方、求逆元、扩展欧几里得都比Python原生的int运算高效太多。SageMath虽然安装体积非常大但它的数论库非常完整在做格攻击、多项式求根、椭圆曲线相关攻击时能省下大量自研时间。yafu是一个独立的大整数分解工具对中小位数模数的分解能力非常强悍对几百位以内的n更是“秒杀”级别的存在。我通常把yafu作为外部进程调用在Python里通过subprocess启动然后解析它的输出结果。这个外部接口的设计让工具箱的扩展性变得很好以后有更好的分解工具直接替换外部进程就行。3.2 公钥解析与参数提取的实操代码写工具箱的第一步就是把各种格式的公钥信息标准化。RSA公钥在CTF题目中最常见的载体是PEM文件比如一个叫pub.pem的文件里面有一段明显的Base64编码。解析的代码其实并不复杂from Crypto.PublicKey import RSA with open(pub.pem, r) as f: key RSA.import_key(f.read()) n key.n e key.e print(fn {n}) print(fe {e})如果题目给的不是PEM文件而是一串十六进制字符串那就需要先解码成整数n int(hex_str, 16) e int(hex_e, 16)这一步看似简单却有一个特别容易踩的坑有些题目给出的十六进制字符串带有0x前缀有些没有有些是大小写混合还有些中间夹杂空格或换行。我的习惯是在解析前统一做一次清理去除所有空白字符再判断是否有0x前缀这样能避免大量低级报错。提取密文时常见的格式有整数、十六进制字符串、Base64字符串以及文件中的二进制数据。最稳妥的做法是统一转换成整数。Base64转整数时先用base64.b64decode解码成字节串再用int.from_bytes(bytes_data, byteorderbig)转成整数。很多初学者喜欢直接用eval()去解析题目给的表达式这非常危险强烈不建议在工具箱里这么做。3.3 攻击参数自动检测的实现逻辑所谓“自动检测”本质是一组启发式判断逻辑。我把它做成一个函数analyze_rsa_params(n, e, ciphertexts)它会依次检查n的位数是否过小比如小于512位直接提示“可尝试暴力分解”e是否为常见小值比如3、5、17、65537的变体如果是3且密文个数为1优先低加密指数攻击是否有多条密文共用同一个n如果有两条以上且各对应不同加密指数优先共模攻击n的素数因子是否有明显的平方因子或小因子可以通过gcd(n, gmpy2.mpz(2)**10000 - 1)之类的手段探测私钥指数d的规模是否可能过小这需要基于e和n的大小关系做粗略估计。这个检测模块并不追求“一把梭”而是输出一个攻击优先级列表。比如同时满足“n太小”和“密文有两条”系统会提示先尝试分解共享的n如果分解成功直接用私钥解密所有密文这样比逐条做共模攻击更彻底。我之前处理过一个题目它的n只有384位但题目包装了一层“两层加密”的概念——先用小n的公钥加密了一个对称密钥再用对称密钥加密了真正的flag。单纯对密文做低加密指数攻击只能拿到对称密钥的密文还得再解一层。这时候自动检测的作用就体现出来了它会提醒你检查明文是否可能是可读的对称密钥。3.4 格式化输出与结果验证机制攻击完以后最怕的就是已经拿到了m的整数形式却因为格式转换不对导致结果“看上去是一堆乱码”。我在工具箱里专门设计了一个结果展示模块负责把整数形式的明文转换成可读文本。转换逻辑是这样的def int_to_text(m): try: byte_length (m.bit_length() 7) // 8 return m.to_bytes(byte_length, byteorderbig).decode(utf-8, errorsreplace) except Exception: return str(m)这个模块会优先尝试把明文按UTF-8解码如果失败再尝试Base64解码、hex解码最终才会把明文当成普通整数打印出来。实际使用中我遇到过明文本身就是十六进制字符串的情况直接转UTF-8会得到一堆不可读字符但转成hex之后立刻就能看到flag。结果验证机制也是工具箱里不可或缺的一环。拿到可能的私钥指数d之后应该立刻用它对原始密文做一次解密检查得到的明文是否可读或是否满足某个已知格式比如包含flag字样。这一步自动化程度越高越能节约人工检查的时间。4. 常见问题与排查技巧实录4.1 攻击失效时的第一排查清单我整理工具的过程中踩过数不清的坑也积累了很多排查经验。如果你的攻击脚本跑了半天却始终没出结果先不要怀疑是数学原理错了90%的情况是参数输入有误或前提条件没满足。排查顺序我建议按下面这张表来现象可能原因排查方法解密结果乱码明文格式判断错误可能是hex或Base64尝试多种格式转换检查字节序是大端还是小端低加密指数攻击失败密文并不是精确的e次方说明填充介入或明文过大改用Hastad广播攻击或者检查是否使用标准填充共模攻击失败两条密文不是同一明文或e1、e2不互质验证密文来源、确认指数间gcd值为1Wiener攻击无结果d值并没有小于n^(1/4)或连分数遍历不完整尝试Boneh-Durfee攻击作为替代Fermat分解超时p和q差距仍然过大切换Pollard’s p-1或回归yafu暴力分解程序内存溢出密文或参数过大循环次数失控给gmpy2运算加位数限制防止无限循环这中间最容易被忽略的是字节序问题。RSA数学上所有整数都是自然数没有“字节序”的概念但一旦涉及把整数转换成字节串就必须约定字节序。OpenSSL生成公钥时使用大端序Python的int.to_bytes默认也是大端但如果题目脚本里用的是小端转换解出来的内容就会倒着排列看起来像是乱码。实际上只要reverse一下字节顺序明文就正常了。4.2 工具报错的经典场景与修复方案工具箱在开发过程中最常见的报错集中在几个方面类型不匹配、模逆不存在、精度溢出、外部进程调用失败。类型不匹配这个多数是因为把gmpy2.mpz类型和Python原生int混用导致的。gmpy2的iroot、invert等函数返回的类型是mpz跟原生int可以进行运算但一些库函数会对类型做严格检查比如PyCryptodome的解密接口就只接受原生int。解决方案很简单在传给其他库之前统一用int()做一次强转。模逆不存在的报错通常是在共模攻击或者私钥求解过程中某个底数跟模数n不互质此时gmpy2.invert会抛出异常。一旦发生这种情况意味着n存在一个小因子反而是一个好消息——可以直接用这个因子分解n。我在错误处理模块里会专门捕获这个异常然后转去尝试做因数分解。外部进程调用失败也是高频问题尤其是yafu它在Windows和Linux上的可执行文件名不一样输出格式也略有差异。我在工具箱里做了一个适配层检测操作系统后自动调整调用参数并对输出做正则提取。如果你的环境里没有yafu也可以用sage的factor()替代或者直接用factordb.com的在线API做查询接口很简单HTTP请求即可。4.3 踩坑记录从失败案例中学到的经验有一次处理一个题目n是1024位e是3密文看起来很规整我一开始自信满满地跑了低加密指数攻击结果开方出来根本不是明文。折腾了很久才发现题目中做了PKCS#1 v1.5填充也就是在真正的明文前面加了一段随机前缀整个消息块被补到了和n差不多的大小所以m^3远大于n直接开方完全失效。这给我的教训是任何RSA攻击场景第一步永远是判断填充方式。如果题目明确说“使用了标准RSA库加密”那大概率有填充此时低加密指数攻击基本可以放弃了除非题目为了出题故意绕过了填充或者让你自己构造明文。这个判断做不对后面的攻击全是徒劳。还有一次共模攻击的脚本怎么都解密不对后来检查发现两条“密文”根本不是对同一明文加密的一个是加密另一个是签名场景不同直接套共模公式当然没有结果。从那天起我在工具箱的检测模块里增加了一个步骤——先对两条密文做统计测试如果它们的数值差异过大可能是明文不同此时共模攻击的前提需要重新审视。4.4 给初学者的建议与进阶路径如果你刚开始接触RSA攻击我建议不要急着把所有攻击脚本抄下来堆在一起。先扎扎实实理解RSA的数学原理尤其是欧拉函数、模逆、费马小定理这几个基础概念然后逐个攻破攻击场景。每学一个攻击方法就动手写一个小脚本然后在本地用自己构造的公钥和密文做验证。比如构造一个e3的加密环境生成一条较小的密文验证低加密指数攻击能否恢复出原文。这样一轮下来你的印象会非常深刻远比直接跑现成工具箱更能锻炼实战能力。等基础打牢了再去研究更复杂的攻击场景比如Coppersmith相关攻击、Boneh-Durfee攻击、基于格的攻击方法这些就需要SageMath的参与。这个阶段建议直接看CTF的WriteUp不光是看解题思路还要看别人在代码实现里的工程细节比如参数怎么归一化、结果怎么转换为可读文本、异常怎么处理——这些细节往往比核心攻击算法更能决定你是否能顺利完成闭环。我个人还有一个习惯是给每个攻击脚本都写一个“使用前提”的注释块记录这个攻击为什么能成功、需要满足什么条件、什么情况下会失败。时间久了这就变成了自己的知识库比任何网上现成的工具包都好用。从最初的“只会拿现成命令跑一跑”到如今能根据参数特征快速匹配攻击路径这套工具箱带给我的不只是效率提升更是一种对RSA密码体制整体弱点的系统认知。安全攻防本来就是一个不断了解对手弱点的过程RSA虽然几十年历经考验但工程实现里的疏忽永远存在。趁手的工具能让你更快地发现漏洞、理解漏洞而这恰恰是每个密码学安全从业者都应该具备的基本功。 
)
