RSA共模攻击实战：从数学原理到Python脚本一键解密

1. 什么是RSA共模攻击想象一下你给同一个朋友发了两封内容完全相同的信但用了两把不同的锁。RSA共模攻击就像是有人找到了这两把锁之间的关系不用钥匙就能拆开你的信封。在密码学中当同一段明文用相同的模数n但不同公钥e1、e2加密时就可能遭遇这种攻击。我第一次在CTF比赛中遇到这种题目时完全被那个神奇的数学公式惊呆了m ((c1 * s1 % n) * (c2 * s2 % n)) % n。这个看似简单的等式背后其实藏着扩展欧几里得算法的精妙运用。对于安全研究人员来说理解这个攻击方式不仅能解决CTF题目更重要的是能意识到在实际系统中重复使用模数的危险性。2. 数学原理深度剖析2.1 欧几里得扩展算法是关键让我们拆解这个攻击的数学核心。假设我们有两个加密等式c1 ≡ m^e1 mod nc2 ≡ m^e2 mod n如果e1和e2互质最大公约数为1根据贝祖定理必然存在整数s1和s2使得 e1s1 e2s2 1这个等式就是整个攻击的突破口。通过扩展欧几里得算法我们可以高效地计算出这两个关键系数s1和s2。我在实际测试中发现即使用非常大的e1和e2比如几万的大数gmpy2库的gcdext函数也能在毫秒级完成计算。2.2 解密公式的推导过程现在我们来一步步推导那个神奇的解密公式。从加密等式出发 m ≡ m^(e1s1 e2s2) mod n ≡ (m^e1)^s1 * (m^e2)^s2 mod n ≡ c1^s1 * c2^s2 mod n这里有个关键点因为s1或s2可能是负数直接计算会遇到模运算中负指数的难题。好在Python的pow函数第三个参数完美支持模逆元计算使得我们可以直接使用负指数。3. Python实战代码详解3.1 环境准备与依赖安装在开始写攻击脚本前需要确保环境正确配置。我强烈推荐使用Python 3.8版本并安装gmpy2库pip install gmpy2对于CTF选手还需要安装pycryptodome库来处理flag的格式转换pip install pycryptodome3.2 完整攻击脚本解析下面是我在多次CTF比赛中优化过的通用解题模板from Crypto.Util.number import long_to_bytes import gmpy2 # 题目给出的参数 n 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801 e1 11187289 c1 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 e2 9647291 c2 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397 # 关键攻击步骤 r, s1, s2 gmpy2.gcdext(e1, e2) m (pow(c1, s1, n) * pow(c2, s2, n)) % n print(long_to_bytes(m))这个脚本中最关键的是gcdext函数它会返回三个值最大公约数r应该是1以及系数s1和s2。有次比赛中我犯了个低级错误忘记检查r是否为1导致解密失败浪费了半小时调试时间。4. 实战案例BUUCTF RSA3解析让我们用这个脚本实际解决BUUCTF的RSA3题目。题目给出的参数正是上面代码中的数值直接运行脚本bflag{49d91077a1abcb14f1a9d546c80be9ef}成功获取flag但作为学习者我建议你不要止步于此。试着修改代码中的n、e、c值用不同的参数组合测试比如尝试交换e1和e2的位置观察s1和s2的变化故意使用不互质的e1和e2看看会发生什么用超大的n值比如4096位测试脚本的性能我在本地测试时发现即使是4096位的n整个解密过程也只需要几毫秒这让我对gmpy2库的效率刮目相看。5. 防御措施与最佳实践理解了攻击原理后我们更应该知道如何防御。在实际系统中绝对要避免使用相同的模数n。我见过一些开发者为图方便在多处重用相同的密钥对这简直是安全灾难。正确的做法是每次密钥生成都使用独立的随机质数定期轮换密钥使用标准的密钥生成工具不要自己实现对于CTF出题者共模攻击是个不错的考点但要注意题目设计。有次我出了道题故意给了不互质的e1和e2结果大部分选手直接套模板失败反而起到了很好的教学效果。6. 进阶思考与扩展掌握了基本攻击后可以尝试这些变种如果有多个2相同模数的密文怎么办如果部分私钥已知如何结合共模攻击在实际流量中如何检测是否存在共模攻击风险我在研究过程中发现很多区块链项目的早期实现都存在共模攻击风险。有次审计时我通过分析交易签名发现了这个问题帮助项目方及时修复避免了潜在的数百万美元损失。