拿到一个RSA加密的密文和公钥n是个几百位的大整数e是65537下面还附着一串Base64编码的密文。这就是CTF密码学题最常见的面孔也是软考信息安全工程师里RSA计算题的升级版。很多人卡在这一步n太大手算不现实常规的分解工具又撑不住。这时候你需要的是一把专门干这事的瑞士军刀——yafu。yafu是一个自动化的大整数因式分解工具专门用来分解那些用常规方法搞不定的合数。在RSA破解流程里它承担的是最核心也最耗时的一步把公钥里的模数n拆成p和q。只要这一步能成后面计算私钥指数d、还原明文就全是机械操作了。这篇东西我打算把yafu从安装到实战踩坑完整讲一遍适合刚接触CTF密码学的新手也适合那些在软考备考里被RSA计算题折磨、想用工具辅助验证的考生。1. yafu在RSA解题中的定位什么时候需要它1.1 RSA的安全性根基与破解逻辑先花一分钟把RSA为什么能被yafu破解这件事说清楚。RSA的安全性建立在“大整数分解困难”这一假设上。简单说给你两个大素数p和q把它们乘起来得到n很容易但给你一个n反推回p和q计算上被认为是不可行的。加密的时候公钥就是(n, e)私钥是d而d的推导需要知道n的欧拉函数phi(n) (p-1)(q-1)也就必须知道p和q。所以RSA破解的核心问题就一个怎么把n拆开。如果n的位数很小比如256位以下普通电脑用试除法就能解但CTF和考试里常见的n动不动就是512位、1024位这时候就需要专业工具了。yafu的价值在于它内置了多种分解算法能根据n的特征自动选择合适的策略用户只需要输入一条命令剩下的交给它去跑。1.2 yafu与同类工具的取舍很多人会问Python里有sympy的factorint还有在线工具factordb为什么还要专门学yafu我的经验是factordb确实方便但它是查库命中不了就白搭sympy的factorint在小数上很好用但到了80位以上的数就显得力不从心yafu则是真正在本地“干活”的它实现了从试除法到二次筛法SIQS再到数域筛法NFS的完整算法栈能够处理100位以上的合数分解。还有一个场景是yafu不可替代的当题目涉及到多个n共同使用同一个素数因子的时候yafu可以批量导入多个n进行分解。这在真实网络攻击案例里常出现也是软考里“RSA公因子网络攻击”那道题的命门。多个公钥如果共享了一个素数p用yafu批量处理能一下把所有n全部解开效率远超一个个复制到浏览器里去查。2. 环境准备与安装两种系统下的实操2.1 Windows下的快速上手yafu的官方发布包在GitHub上作者是bbuhrow。不需要编译直接下载对应系统架构的压缩包就能用。这里有几个容易被忽略的点。第一要区分64位和32位版本。现在绝大多数电脑都是64位系统下载yafu-64.exe即可。但如果你用WSL或者某些精简环境建议同时把32位版也下下来因为在某些老版本的Linux发行版里缺少32位兼容库时64位版反而跑不起来这种玄学问题我遇到过不止一次。第二yafu运行时会生成日志文件默认在当前目录下。建议单独建一个文件夹比如C:\yafu把exe放进去。不然你在某个临时目录里跑它日志和session文件会散落各处后续想断点续跑都不方便。第三Windows下如果遇到缺少DLL的错误比如找不到libgmp-10.dll说明你的环境缺了运行依赖。yafu的发布包有时候不会自带所有依赖库你需要把GMP、MSVC运行时这些装上。最快的办法是去装一个完整版的MSYS2把依赖一次补齐。2.2 Linux下的编译与依赖Linux下我推荐自己编译原因很简单官方发布的二进制在部分新内核上有兼容问题而且自己编译可以针对CPU指令集做优化跑大数分解能快不少。编译yafu需要准备这些依赖sudo apt-get install libgmp-dev libmpfr-dev libmpc-dev build-essential m4 git clone https://github.com/bbuhrow/yafu.git cd yafu make编译完成之后会在当前目录生成yafu这个可执行文件。建议把它复制到/usr/local/bin下面或者做一个软链接这样在任何目录下输入yafu都能直接调用就像系统自带命令一样方便。我记得第一次编译的时候卡在m4没装报了一堆看不懂的宏错误后来才搞清楚是构建系统需要m4来生成解析器代码。2.3 验证安装是否正常装好之后先跑一条最简单的命令验证一下yafu factor(21)正常情况下yafu会先启动一个交互式环境然后自动执行factor(21)结果应该输出3和7这两个因子。如果这里都出问题多半是环境没配好先把依赖补齐再往下看。3. yafu的核心用法与参数解析3.1 交互模式与命令行模式yafu有两种使用方式。一种是进入交互模式输入yafu回车然后在一个类似shell的环境里输入factor(n)这样的指令另一种是命令行直接带参数一次性执行适合脚本化调用。我个人的习惯是做题的时候用交互模式因为可以在一次会话里连续分解多个n还能用factor(0)这类指令查看帮助。但在CTF比赛里时间就是分数建议直接用命令行模式一条命令跑完就节省了等待交互提示符的时间yafu-x64.exe factor(8794830329102910939192918)注意括号和逗号之间不要有空格yafu的命令行解析比较死板多了空格可能报错。3.2 常用参数详解yafu参数非常多但真正在RSA解题里常用的就几个。-threads参数用来指定线程数。默认情况下yafu会用满所有CPU核心这在服务器上可能没问题但在本地共享机器上容易卡死别的程序。我的经验是设成物理核心数减一比如8核CPU就设-threads 7既能保证速度又不至于让电脑卡到没法切窗口。-pretest参数控制预测试的强度。yafu在进入大数分解算法之前会先用小素数试除、Pollard rho、P-1这些“快速检查”手段扫一遍。默认的-pretest是足够用的但如果你怀疑n里面有个很小的因子但yafu没扫出来可以显式指定-pretest 1甚至-pretest 2来增强检查力度。-siqs和-nfs这两个参数分别强制使用二次筛法和数域筛法。正常情况下不需要手动指定yafu会根据n的位数自动选择。但在某些极端场景下比如n只有40位但yafu误判了可以手动指定-siqs来强制跑二次筛法速度反而更快。-r参数非常关键它表示“如果找到一个因子但不是全部因子继续递归分解剩余部分”。比如npqr三个素数相乘的情况yafu默认找到一个因子就停了加了-r才会继续处理剩下的合数。CTF里也遇到过三个素数相乘的题目这个参数救过我一次。3.3 yafu的工作机制算法调度流程搞清楚yafu内部怎么调度算法有助于你判断它要跑多久、以及当场卡住时到底在干什么。当一个n送进来yafu的流程是这样的先做试除法用前几千个小素数直接筛这一步很快秒级完成。接着做Pollard rho和Pollard p-1这一步对“刚好有一个小因子”的n特别有效能在几秒到几分钟内出结果。如果还没分解完就开始做椭圆曲线法ECM用一组曲线去尝试找出中等大小的因子。最后如果n还有剩余的大因子并且位数在90位以下就走二次筛法SIQS90位以上则自动切换到数域筛法NFS。这个调度顺序对应了不同分解算法的“性价比”排序越靠前的算法越便宜先花小钱办大事实在不行才上重型武器。理解了这一点你就知道为什么某些n几秒就出结果、某些n要跑十几个小时——前者n里有弱因子后者n是精心设计的强合数只能硬碰硬。4. 实战一道完整RSA题目的破解流程4.1 题目描述与信息提取我拿一道我自己做过、印象深刻的题目来演示完整流程。这道题模拟的是软考下午题的风格给定信息如下n 8794830329102910939192918... (153位十进制数) e 65537 c 58239783028184759823749825702938475... (和n同数量级的密文)第一步是把这些参数整理清楚。实际赛题里n和c通常以十六进制字符串给出或者藏在PEM格式的公钥里你需要先用工具把它们转成十进制整数。提取公钥中n的代码很简单from Crypto.PublicKey import RSA pub RSA.import_key(open(pub.pem).read()) n pub.n e pub.e print(n)只要n能被yafu分解这题就算破了。4.2 调用yafu分解模数n接下来把n丢给yafu。我在命令行里执行yafu-x64.exe factor(8794830329102910939192918...)如果n的位数在100位以下yafu通常会在几分钟内跑完。输出结果里会有一行以***factors found***开头下面就是分解出来的p和q。这里有件事必须提醒yafu有时候会中途提示保存session文件并让你用resume命令恢复。这是正常的因为长任务的中间状态落在磁盘上防止断电丢进度。你只需要在同一个目录下再次启动yafu输入resume就能接着跑。我在比赛里遇到过跑了三个小时的任务靠这个功能省下了大量重复计算。4.3 计算私钥并解密密文拿到p和q之后剩下的就是纯数学计算。写一段Python脚本来完成解密from Crypto.Util.number import inverse, long_to_bytes p 1234567890123456789012345678901 q 7123456789012345678901234567890 n p * q e 65537 c 58239783028184759823749825702938475 phi (p - 1) * (q - 1) d inverse(e, phi) m pow(c, d, n) print(long_to_bytes(m))如果题目给出的c是十六进制字符串别忘了多一步int(c, 16)转换。这里我踩过一个坑直接用整数除法去算phi结果因为Python的整除符号用错导致d算不出来后来统一用(p-1)*(q-1)这种显式乘法逻辑清楚多了。4.4 快速解题脚本模板为了应对比赛和考试中的重复劳动我把上面这些步骤封装成了一个通用脚本。适合所有“已知n, e, c需要求m”的场景from Crypto.Util.number import inverse, long_to_bytes def rsa_decrypt(n, e, c): # 用yafu分解n之后填入p, q p 0 # TODO: 填入yafu的输出 q 0 # TODO: 填入yafu的输出 assert p * q n phi (p - 1) * (q - 1) d inverse(e, phi) m pow(c, d, n) return long_to_bytes(m) if __name__ __main__: n int(input(n )) e int(input(e )) c int(input(c )) print(rsa_decrypt(n, e, c))这个脚本我比赛用了五六年只改p和q两个变量就行基本零出错。分享给一起打比赛的朋友后他们也觉得省心。5. 常见问题与排查“坑”实录5.1 分解时间过长或看起来卡死这是最常遇到的情况几乎每一个第一次用yafu的人都会慌。其实大多数时候不是卡死而是yafu正在跑ECM或者SIQS这类算法本身就需要大量计算屏幕上暂时没有输出也是正常的。我的判断方法是看CPU占用率。如果CPU占用接近100%说明它是真在算如果CPU占用是0那就是真卡了。真卡的情况多半是因为线程设置过高或者内存被占满可以试着减少-threads或者重启yafu。另外一个技巧是观察yafu生成的日志文件大小只要文件在持续变大就说明任务有进展。如果分解时间超过三个小时而且n的位数在100位以上我的建议是先去factordb查一下如果有前人记录过的分解结果直接就秒杀别在yafu上死磕。5.2 n位数过大导致内存溢出yafu在跑NFS的时候内存消耗非常可观尤其是100位以上的数字低配机器很容易内存溢出错乱。解决思路有两个一个是修改yafu的配置文件yafu.ini把内存限制参数调低比如设置maxmem2000表示最多使用2G内存另一个是改用ECM跑法牺牲速度换取稳定性。我自己的笔记本只有16G内存跑1024位的大数时曾经因为内存爆掉导致系统直接重启后来学乖了先看n有多少位超过110位就直接放弃yafu改用云服务器跑或者去factordb碰运气。5.3 对特定的n总是分解失败有些RSA题目出题人会用一些特殊手法来防分解。比如p和q故意选得很接近这种情况下Pollard rho能很快找到因子yafu通常没问题。但如果出题人用了强素数p-1和p1都有大素数因子那P-1和P1这几个“便宜算法”就全部失效只能硬跑ECM或者SIQS时间会指数级上升。遇到这种情况我建议先检查这个n是不是故意设了陷阱用n % 2检查奇偶性用gcd(n, 2)排除偶数因子再看看n是否为完全平方数。有个特殊情况是n本身是素数——那这题就不该用分解的思路而是可能有其他漏洞。yafu对这类“伪RSA题目”也无能为力因为它本质上不是干这个的。5.4 工具报错和信息解读yafu的错误输出信息比较少看多了就习惯了。最常见的几个factor: short read表示输入格式有问题多半是括号或者逗号写错了could not open session file表示当前目录下找不到延续任务的session文件检查一下你启动yafu的目录是否和之前一致failed to allocate memory就是内存不够降低线程数或者换个机器。还有一个小细节yafu解析输入时会把大小写字母和空格全部忽略所以factor( N )和factor(n)是一样的。但要注意不要在数字内部加引号比如factor(879)会报错直接把数字写进去就好。5.5 多个n同时需要分解的批量处理对付RSA公因子攻击题目需要同时分解好几个n。这时候不要一个一个手敲yafu支持从文件读取多个数字yafu-x64.exe factor()配合一个包含了所有n的文件每行一个数字yafu会依次处理所有n。批量分解时建议加上-r参数这样即便遇到三素数相乘的n也能一次性全部分解出来。6. 效率提升与其他工具和脚本的配合6.1 yafu与Python的联动yafu输出的是文本天然容易和Python配合。我写过一个很简单的自动化流程先用Python脚本解析题目给的所有n逐个调用yafu命令行然后从输出里用正则表达式提取因子再把p、q回填到解密脚本里。这个流程在处理大量已知n的题目时效率极高因为省去了人工复制粘贴的时间。提取因子的正则表达式很简单import re output open(yafu_output.txt).read() factors re.findall(rP\d\s*\s*(\d), output) p int(factors[0]) q int(factors[1])注意yafu的输出格式通常是P32 123456789...这种P后面的数字代表这个因子的十进制位数。6.2 yafu与在线工具的互补我从来不排斥用在线工具。有一个很高频的解题路径是先用factordb查n如果能查到就直接抄答案查不到再把n丢给yafu。因为factordb背后有一个巨大的历史数据库很多比赛题目用的n其实已经被前人分解过查库比跑分解快几个数量级。但也别完全依赖factordb因为有些新题用的n是出题人新生成的数据库里没有记录。而且考试环境根本不允许联网。所以在本地掌握yafu是刚需factordb只是锦上添花。6.3 当yafu都搞不定时怎么办我遇到过一些nyafu跑了十几个小时都没出来而且factordb也没有记录。这种情况下我的经验是大概率这题不是让你直接分解的。可以回头检查题目描述看有没有给出d、或者p和q的某个线性关系。CTF题经常留一些巧妙的暗示比如提示“p和q共享一个高位前缀”这时候用Fermat分解法或者基于已知部分的Coppersmith攻击会更有效。yafu是RSA解题的重要工具但不是万能的。掌握它的同时也建议了解一些RSA攻击面知识比如低加密指数攻击、共模攻击、维纳攻击等。这些攻击不依赖分解n而是利用密码系统参数选择上的失误往往比盲目分解更快。7. 实战心得与后续扩展7.1 从小白到熟练踩坑的历程我第一次用yafu是在去年一个CTF训练赛中当时连从哪里下载都不知道折腾了半个多小时。真正跑起来的那一刻看到屏幕上刷出***factors found***那种“原来这就是密码学破解”的感觉至今记忆犹新。但那次比赛我也犯了蠢——没带-r参数导致一个三素数乘积的n只分解出了一半白白丢了分数。后来用多了慢慢总结出几条习惯。第一拿到题目先看n的位数心里有个预期80位以下秒出100位以下可能跑几分钟120位以上基本要挂机。第二能开多线程就尽量开减少等待时间。第三跑之前先看一眼n的末尾是不是偶数或者5的倍数有些粗心的出题人甚至会给你一个偶数n这时候根本不用yafu直接除以2就行。7.2 结合软考场景的针对性建议如果你是在准备软考信息安全工程师的RSA计算题我的建议是别死记公式最好亲手用yafu跑通一遍完整流程。因为软考下午题里经常出现大数运算手算根本算不出1024位整数的高次幂用工具辅助验证是合理且高效的学习方式。考试不能联网但本地工具是允许的。把yafu和Python的RSA解密脚本都提前准备好考试时直接套用模板速度比手推快十倍不止。我当年备考时就是用这种方式把RSA相关的计算题全部刷了一遍从看题目到出答案最快只需要两分钟。7.3 后续还能怎么扩展学会了yafu之后我建议你把RSA其他类型的攻击也过一遍。yafu解决了“分解n”这个问题但RSA题目还有很多变种比如你不知道n的完整值、只知道高位或低位的一部分这类题需要用到SageMath里的Coppersmith方法这就超出了yafu的能力范围了。还有一个值得扩展的方向是深入了解yafu内部算法的实现。它的二次筛法SIQS在多核并行上的调度逻辑写得非常漂亮读一遍源码对理解大整数分解的工程实现很有帮助。虽然日常做题不需要懂这些但如果你以后想走密码学或安全研究路线这是一个不错的切入点。7.4 最后分享一个小技巧yafu的session恢复功能特别实用但很多人不知道。当任务跑到一半中断再次启动yafu后输入resume它会读取目录下的session文件继续跑。这个功能在跑大数分解时几乎是保命级别的。我建议你每次启动yafu前先看一下当前目录有没有session文件如果有就优先resume而不是重新factor能省下好几个小时的重算时间。另外yafu输出的日志文件factor.log也会记录每次分解的结果就算屏幕输出被冲掉了日志里也有完整记录。我习惯每次跑完都把日志重命名保存按题目编号存下来方便复盘。这样积累多了甚至会形成一个小型“因子库”以后再遇到相同或相近的n查自己的日志就行。