RSA低加密指数广播攻击实战：从数学原理到AI辅助Writeup

最近在整理CTF题解的时候翻到自己之前做的一道RSA题目当时正好在尝试用AI辅助写Writeup整个过程挺有代表性的。以前遇到RSA题目基本都是手推公式、手写脚本但这道题虽然套路经典却因为数据格式和工具链的问题卡了一会儿反而是在AI的帮助下把思路理清了脚本也顺利调通。这篇就当一次完整复盘从题目分析、数学原理、AI配合的正确姿势到踩过的坑都展开说说。需要先说明一点这篇不是“AI自动解题”的银弹教程而是讲清楚在什么环节让AI介入、如何提问、如何判断AI给出的答案才能让解题效率真正提升。适合刚接触CTF密码学、想做RSA题目复现或者想用AI辅助写技术Writeup的朋友参考。1. 题目分析与AI辅助的介入点1.1 题目基本信息与文件处理先说题目本身。这是一道经典的CTF RSA题目压缩包解开之后有两个文件pub.pem和flag.enc。前者是OpenSSL生成的标准RSA公钥文件后者是二进制密文。很多新手看到这两个文件就懵了不知道从哪下手其实流程是固定的。第一步用OpenSSL读取公钥信息。在终端里执行openssl rsa -pubin -in pub.pem -text -noout输出大致是下面这个样子Public-Key: (1024 bit) Modulus: 00:b2:6a:... Exponent: 3 (0x3)这里两个关键信息就出来了模数n是1024位公钥指数e3。看到e3的时候我脑子里立刻闪过“低加密指数攻击”这个选项。CTF里大部分RSA题目都不会让你老老实实去分解一个正常生成的1024位n反而会在参数选取上留出破绽e3就是非常典型的一类。第二步把密文读取出来。flag.enc是二进制文件在Python里可以直接用open(..., rb).read()读取。但要注意解RSA题的时候密文通常要转成整数才能参与模幂运算。具体可以这么处理from Crypto.Util.number import bytes_to_long data open(flag.enc, rb).read() c bytes_to_long(data) print(f密文长度: {len(data)} 字节) print(f密文整数位长: {c.bit_length()})如果密文长度和n的字节长度不一致也不用慌后面会排查。拿到n、e、c之后题目才算真正开始。1.2 攻击面初判e3是一个危险信号RSA题目的核心就一句话找到一条路还原出明文m。常见路径包括分解n得到p、q算出私钥d之后直接解密也有不需要分解n的攻击方式比如低加密指数广播攻击、共模攻击、Wiener攻击等。面对一道题第一步是判断该走哪条路。我当时列了一个快速判断清单这里也分享出来检查n是否已经被FactorDB收录能直接查出p和q。检查e是否很小比如3如果e很小考虑低加密指数攻击。检查e是否非常大比如接近n考虑Wiener攻击。检查是否存在多个公钥文件如果有用GCD求公共因子。检查p和q是否可能接近相关参数可以用Fermat分解验证。回到这道题e3非常突出。但光有e3还不够低加密指数攻击需要一个重要前提同一个明文m被加密进了多组不同的模数n中或者m^3本身小于n。如果只是单独一组n、c且m^3大于n那么开三次方之后还要对n取模没法直接还原m。所以我又确认了一下题目目录发现一共给了三组n和c都是e3明文显然相同。这就把攻击路径锁定到了“低加密指数广播攻击”。1.3 为什么用AI辅助而不是纯手写理论上这种题型的数学原理很固定用手写脚本完全可行。但实际操作中有大量琐碎环节从PEM公钥里提取n和e、处理不同格式的密文、用CRT组建同余方程组、对大整数开三次方根……每个环节都有自己的坑。我第一次尝试用AI辅助是因为在代码实现上卡住了。印象最深的是我想用gmpy2.iroot开三次方但手边临时没有现成的脚本模板正好脑袋里又想着“要不让AI先写一版”于是就把题面信息发给AI让它生成一个可跑的Python脚本。结果证明AI在“把数学想法翻译成代码”这件事上确实快但在“判断该用哪个数学想法”这件事上依赖的还是人的经验。所以我把AI定位成“结对编程的实习助手”它负责快速产出代码片段、解释报错、提供备选方案我负责做最终判断。这个定位在后来的调试过程中帮了大忙。2. RSA数学原理与低加密指数广播攻击2.1 RSA加密解密核心流程在继续解题之前得把RSA的基础原理过一遍。这一节不是凑字数而是因为很多AI生成的脚本写得再漂亮如果你不理解背后的数学关系出了问题根本不知道从哪调。RSA的安全性建立在大整数分解困难这个假设上。生成密钥时选择两个大素数p和q计算模数 n p × q欧拉函数 φ(n) (p - 1) × (q - 1)选择一个与φ(n)互素的公钥指数e例如65537或3计算私钥指数 d满足 d × e ≡ 1 mod φ(n)也就是d是e在模φ(n)下的逆元公钥是(n, e)私钥是(n, d)。加密过程是给定明文m计算密文c m^e mod n解密过程是m c^d mod n整个过程可以类比成“上锁”和“开锁”公钥是锁任何人都能把消息锁进去私钥是钥匙只有持有钥匙的人能打开。但问题在于如果钥匙的齿形也就是参数设计得太简单锁匠就能用特殊工具绕开钥匙直接开锁。低加密指数攻击就是其中一把“特殊工具”。2.2 低加密指数攻击的原理与中国剩余定理当e很小比如e3时加密公式实际上是c m^3 mod n如果恰好m^3 n那么取模操作没有生效c直接就是m^3的整数结果只需要对c开三次方就能得到m。但CTF题目通常不会让你这么舒服因为m一般是flag转化的整数m^3很大会超过n。这时如果同样的m分别用三组不同的公钥(n1,3)、(n2,3)、(n3,3)加密得到三个密文c1、c2、c3就可以利用中国剩余定理CRT构造一个同余方程组x ≡ c1 mod n1x ≡ c2 mod n2x ≡ c3 mod n3因为n1、n2、n3两两互素这个方程组在模N n1 × n2 × n3下有唯一解x。而x实际上等于m^3。关键是如果m^3小于n1 × n2 × n3那么x就是m^3的精确整数结果不需要再模N。这样我们直接对x开三次方就能还原出明文m。这里有个前提容易被忽略题目里的三组n必须两两互素。如果某些n之间存在公因子反而可以退化成求最大公约数的攻击——这也提醒我们做题前一定要对数据做基本检查。2.3 什么时候可以采用这种攻击低加密指数广播攻击不是万能的它有三个条件缺一不可e足够小通常为3。同一明文被加密了至少e组如果e3就至少三组。各组模数n两两互素且m^e小于所有n的乘积。如果题目只给了一组n和c也可以用另一种思路直接遍历m看m^3是否等于c。但flag通常很长遍历空间很大不现实。所以这种攻击本质上依赖“多组数据复用同一个明文”的误用场景。从生活角度理解想象你给三个人寄同一封信但每次都只用一个三位数的密码锁锁上三位数密码显然不够安全。如果这三个人都能看到锁上的数字你把三组数字收集起来就能通过数学关系还原出信件内容。3. AI辅助Writeup实操从提问到脚本落地3.1 第一轮提示词让AI帮忙梳理题面我拿到三组n和c之后没有急着写代码而是先把题面信息整理成一段文字发给AI。最初的问题是我有一道CTF RSA题目有三组数据公钥指数e都是3分别有n1, n2, n3和c1, c2, c3明文相同。请帮我写一个Python脚本解密。AI很快就给出了方向使用中国剩余定理组合三个密文然后用gmpy2.iroot开三次方。这个方向本身正确但它回复里给的一段示例脚本有一个小问题——它直接使用了pow(c, 1/3)。在Python里1/3是浮点数对于大整数会丢失精度得到的结果基本是错的。这也是AI写大数运算代码时非常常见的坑。所以不要盲信AI的第一版输出。我把它当草稿自己检查关键点然后要求它改成基于gmpy2.iroot的实现。3.2 第二轮提示词针对e3生成攻击脚本第二版我用了一个更明确的提示词请不要使用浮点数开方改用gmpy2.iroot。请实现中国剩余定理并返回最终解密后的flag。这一版生成的核心脚本已经可以跑了大致是这个结构import gmpy2 from functools import reduce def crt(moduli, remainders): 中国剩余定理 prod reduce(lambda a, b: a * b, moduli) result 0 for n_i, r_i in zip(moduli, remainders): p prod // n_i inv_p gmpy2.invert(p, n_i) result r_i * inv_p * p return result % prod n [ n1, n2, n3 ] c [ c1, c2, c3 ] e 3 m_cubed crt(n, c) m, exact gmpy2.iroot(m_cubed, e) if exact: flag m.to_bytes((m.bit_length() 7) // 8, big) print(flag) else: print(开三次方失败可能数据不满足条件)gmpy2.iroot返回两个值第一个是整数根第二个是布尔值表示是否为精确的整数幂。用exact判断是否开方成功比直接断言更稳妥。这个方法在CTF大整数运算里几乎成了标配。3.3 脚本关键代码逐段解析整个脚本看起来不长但每一步都值得拆开讲。crt函数里prod是所有模数的乘积也就是N。对每个模数n_i计算p prod // n_i相当于N除以n_i。然后利用gmpy2.invert(p, n_i)求p在模n_i下的逆元。这样做是因为中国剩余定理的解可以用如下公式表示x Σ (r_i × p × inv_p) mod N最终返回result % prod就是满足所有同余方程的最小正整数解m_cubed。因为题目里m^3 N这个解就等于m^3本身不需要对模数N取额外处理。严格来说就算m^3大于N返回的也是m^3 mod N那就无法直接开方了所以exact判断很有必要。m.to_bytes((m.bit_length() 7) // 8, big)这行很关键。m是整数要还原成flag字符串必须把它转成字节串。字节长度是bit_length向上取整到8的倍数7再整除8就是这个效果。注意不能写死成16或32字节因为flag长度每次都不一样。3.4 从AI输出到正确脚本的修正过程现在复盘一下AI帮我省下了哪些手写时间又增加了哪些坑。省时间的地方在于CRT的模板代码、字节与整数的转换、gmpy2.iroot的调用方式这些AI都写得很快。但我后来在本地跑的时候遇到了一个实际问题crt函数返回的m_cubed是Python的mpz类型gmpy2.iroot能处理没问题。倒是to_bytes方法要求整数是Python原生int如果直接把mpz传过去有些Python版本会报TypeError。解决办法是加一个int()转换m int(m) flag m.to_bytes((m.bit_length() 7) // 8, big)这是我实际调试中遇到的真实问题AI不会替你想到。如果对底层类型不敏感写出来的脚本可能看一眼能过一跑就崩。另外AI第一版给的代码里把三个密文直接作为c列表传入CRT但密文文件读入后其实是一串二进制字符串必须先转成整数。如果忘了转CRT里会直接报类型错误。这类细节在AI生成的代码里经常被忽略但它会间接提示你检查数据预处理。4. 实战中的报错排查与AI协作心得4.1 常见bug与解决方式手动跑脚本的过程中我记录了三个最有代表性的报错场景每一个都有对应的解决思路。第一个场景是读取密文时类型混乱。如果直接用int(data)处理bytes对象会抛ValueError因为bytes不能被直接转换成十进制整数。正确做法是用bytes_to_long或者先转成hex再int(hex_str, 16)。我在这个环节纠结了一会儿最后是让AI解释报错原因才意识到问题出在“字节串”和“整数”在RSA语境里的双重含义上。第二个场景是CRT结果开方后exact为False。这说明可能某个密文对应的n不是两两互素或者明文并不完全相同或者数据里混入了额外填充。遇到这种情况我的建议是立刻验证三对n之间的两两GCDimport math print(math.gcd(n1, n2)) print(math.gcd(n1, n3)) print(math.gcd(n2, n3))如果GCD不是1那题目可能根本不需要CRT而是用共模攻击或者求公因子后直接分解n。这个检查我在做题时习惯性地写在了最前面省了很多无用功。第三个场景是文件编码问题。有些题目里的flag.enc是文本形式的十六进制串比如666c6167...而不是真正的二进制文件。如果不管三七二十一直接bytes_to_long解出来的可能是错误的数字序列。这时候要先看文件开头几个字节判断是文本还是二进制。4.2 问题排查速查表把实战中遇到的典型问题整理成了一张表后续做题遇到类似报错可以快速对照。现象可能原因解决思路TypeError: mpz object cannot be interpreted as an integergmpy2类型未转int使用int()包裹后再用to_bytesValueError: invalid literal for int() with base 16把bytes当hex字符串解析用int.from_bytes或bytes_to_longiroot返回exactFalsem^3不够小或CRT组合错误或明文不同检查三对n是否互素确认明文一致性AttributeError: module object has no attribute iroot没有安装gmpy2或导入错误执行pip install gmpy2并import gmpy2解出的flag乱码nc数据的填充方式不同或字节序错误检查大端/小端约定尝试调整to_bytes字节序公钥文件解析失败PEM文件格式损坏或包含私钥信息用openssl rsa -pubin -in pub.pem -text -noout检查这张表不是固定的每个人遇到的题目都有差异但排查思路是通用的先确认数据格式再确认参数关系最后看代码操作是否匹配数学定义。4.3 AI辅助安全边界哪些能信哪些不能信和AI协作几轮下来我最大的感受是AI是一个效率放大器但不是一个正确的保证器。它能信的部分包括常见算法的模板实现比如CRT、Wiener攻击、Fermat分解。报错信息的常见原因排查。把一段数学描述“翻译”成Python代码。对标准库和常用第三方库的调用方式。它不能信的部分包括对具体题目数据的判断。比如它不知道你的n是否满足攻击条件除非你在提示词里把相关检查结果都贴进去。对不需要库的“伪代码”可行性。它会偶尔写出一个看上去合理、实际上在Python里不存在的API。对精度敏感的大整数运算。浮点数开方、普通整数除法都可能在大数场景下翻车。所以我在用AI辅助写Writeup时给自己定了一条纪律AI输出的每一行关键代码我都要想清楚它在数学上做了什么再放到真实数据上验证。这样既能利用AI的速度又不会被它的“一本正经胡说八道”带偏。5. 其他高频RSA题型的快速判断指南5.1 各类型攻击对照表RSA题目变化多端但绝大多数都能归到几种经典模式里。我结合自己的刷题经验列了一张对照表方便以后遇到类似题目时快速定位。攻击类型题目特征核心思路低加密指数广播攻击e很小多组n/c且明文相同CRT构造m^e再开e次方共模攻击多组e/c但n相同扩展欧几里得组合密文还原mWiener攻击e非常大接近n对e/n做连分数展开逼近dFermat分解n是1024位但p和q很接近从sqrt(n)开始寻找平方差Pollard p-1n的某个因子减1有很小素因子用B-Smooth阶模幂试探求因子GCD公共因子多个n之间有公因子直接两两求gcd得到pCoppersmith已知m的一部分或p的部分位构造多项式用小根求解已知p、q、e、c给了全部私钥成分直接求d后解密这张表不是完整的攻击知识体系但覆盖了CTF基础RSA八成以上的考察点。看到题目时先对号入座再决定用AI生成哪种脚本效率会高很多。5.2 一个极简的checklist流程最后分享一个我自己十分钟就能走完的检查流程你可以直接抄拿到题目目录先用file查看每个文件类型。用OpenSSL读取公钥文件记录n的bit长度和e。用Python读取密文文件判断它是二进制还是hex文本。把n、e、c整理成固定格式的变量打印一次确认值。判断e的大小e很小走低加密指数e很大走Wienere65537继续往下。检查多组数据之间是否存在公因子有就直接gcd分解。如果n是1024位且看起来是随机生成尝试FactorDB在线查询。实在不行再用Fermat分解或YAFU跑一下。得到p、q后用pow(c, d, n)解密并转成字节输出。这个流程看起来朴素但能覆盖大多数入门级RSA题。我过去经常一上来就写脚本结果发现方向错了白折腾半小时。后来改成先做静态检查再决定行动路径反而解题速度快了很多。回到一开始说的AI辅助。有了这个checklist再用AI写脚本时我可以把“第几类攻击”直接告诉AI而不是让它去猜。比如我只需要说“已经确认是低加密指数广播攻击请生成CRT脚本”AI的输出会稳定得多。这是一种更聪明的协作方式人做判断AI做执行。个人体会是RSA题目的Writeup最值钱的不是最后那段十几行的解密脚本而是中间那个人脑做方向判断、AI快速落地、再人工验证修正的过程。遇到类似题目你也可以试试让AI先出一版“草稿代码”但一定要记得自己把数学关系捋一遍。真到了赛场上能信任的还是那些被你亲手验证过的代码。