CTF实战：手把手教你用Python脚本秒解BUUCTF那道RSA共模攻击题（附完整代码）
CTF实战：Python脚本秒解BUUCTF RSA共模攻击题
第一次在BUUCTF平台遇到RSA共模攻击题时，我盯着两组相似的n值和不同的e值完全摸不着头脑。直到理解了背后的数学原理，才发现这类题目其实有固定的解题套路。本文将用最直白的方式，带你从零开始攻破BJDCTF2020这道典型题目。
1. 识别共模攻击场景
当看到题目附件给出以下特征时，就要立即想到共模攻击的可能性：
- 相同的模数n：两组数据中的n值完全一致
- 不同的指数e：e1和e2值不同且通常互质
- 对应的密文：提供两个用不同公钥加密的密文c1和c2
# 题目给出的典型数据结构 n = 2105833933... # 长达617位的相同n值 e1, c1 = 2767, 2015249016... e2, c2 = 3659, 1129869732...共模攻击可行的核心原理在于：当两个加密指数互质时，存在整数s1和s2满足：
e1*s1 + e2*s2 = 1这个等式让我们能够组合两个密文还原出原始明文。
2. 必备数学工具准备
解决这类题目需要两个关键Python库：
- gmpy2：处理大整数运算
- libnum：实现数值与字节转换
安装命令：
pip install gmpy2 libnum注意：Windows用户可能需要先安装Microsoft Visual C++ 14.0以上版本
3. 攻击脚本编写详解
完整攻击脚本可分为三个逻辑部分：
3.1 参数输入阶段
直接从题目复制粘贴参数值：
n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111 e1, c1 = 2767, 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599 e2, c2 = 3659, 112986973231409888120577353242859084805047214541457965350144187389590352456006799472978745178189281815090815450270565237900225982339180112610119731963863956893715267747855823261219591861955860698515924676378193666240441336610163733608851589569552636456143458813504940123282752158213069552127882826178126865488831510668661490603634829587083647269829087983401822887021010233938397814273865372304594365126130473115858750680082108189969414601565893141350104383624475224282068849449526398266772478190668127068357731070595670828223123007210498270136604186102651892888402471865981457417240843516335084927077552068862028762273.2 核心攻击逻辑
使用扩展欧几里得算法求解系数：
import gmpy2 # 计算满足e1*s1 + e2*s2 = 1的系数 _, s1, s2 = gmpy2.gcdext(e1, e2) # 注意s1或s2可能为负数，需要处理模逆元 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关键点：当s1或s2为负数时，需要对对应密文取模逆元，这是很多初学者容易忽略的步骤
3.3 结果输出处理
将大整数转换为可读字符串：
import libnum flag = libnum.n2s(int(m)).decode() print("Flag:", flag)4. 完整脚本与执行结果
将上述代码组合成完整解决方案：
import gmpy2 import libnum # 题目参数 n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111 e1, c1 = 2767, 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599 e2, c2 = 3659, 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227 # 共模攻击 _, 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 flag = libnum.n2s(int(m)).decode() print("成功获取flag:", flag)执行后将直接输出flag内容，整个过程在普通电脑上耗时不足1秒。
5. 实战技巧与扩展思考
通过这道题可以总结出RSA共模攻击的快速识别特征：
题目特征
- 提供两组或多组公钥(n,e)
- 模数n相同而e不同
- 每组公钥对应一个密文
防御措施
- 在实际系统中绝对避免重复使用模数n
- 为不同用户生成独立的密钥对
变种题型
- 结合Base64编码的密文
- 需要先解压或解码的附件
- 隐藏的n值需要从其他信息推导
建议将核心攻击代码保存为模板文件，遇到类似题目只需替换参数即可快速解题。对于更复杂的RSA题型，可以尝试以下扩展学习路径：
学习路线图: 基础RSA → 共模攻击 → 低加密指数攻击 → 中国剩余定理 → Wiener攻击 → Boneh-Durfee攻击掌握这些技巧后，你会发现BUUCTF上80%的RSA题都能在5分钟内解决。记住，CTF竞赛中效率是关键，建立自己的密码学代码库能大幅提升解题速度。