RSA 共模攻击实战：BUUCTF RSA3 双密文单模数场景解密（附 Python 代码）

RSA共模攻击深度解析从数学原理到CTF实战1. 共模攻击场景概述在传统RSA加密中每个用户使用不同的模数n和公钥e进行加密。但当两个不同的公钥共享同一个模数n时就会产生严重的安全漏洞——共模攻击Common Modulus Attack。这种攻击方式允许攻击者在不知道私钥的情况下仅通过两个使用相同n的密文恢复出原始明文。典型攻击场景同一消息被两个不同公钥加密e₁, e₂两个公钥使用相同的模数n攻击者获取了c₁ mᵉ¹ mod n和c₂ mᵉ² mod n2. 数学原理与推导共模攻击的核心在于扩展欧几里得算法的应用。当e₁和e₂互质时存在整数s₁和s₂满足e₁*s₁ e₂*s₂ 1通过这个关系我们可以推导出m (c₁ˢ¹ * c₂ˢ²) mod n关键步骤证明根据欧几里得算法求出s₁和s₂处理负数指数的情况使用模逆元组合两个密文恢复明文注意当s₁或s₂为负数时需要先计算对应密文的模逆元再执行幂运算。3. BUUCTF RSA3题目实战3.1 题目参数分析给定参数n 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801 e1 11187289 e2 9647291 c1 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 c2 187020100451870155565486916423949828356692621472302127313099386752264585552104259724294184492734105353879859310367118542656239050668056657518032691068807467690034789007910995902395139254497488140759040174715855728484735564905654500626647064491284158347879619472662597897859629222387011340797204142284140661930714953046123410529874556159300235368238014992697733571860874527475008406404193650115544211830375056534612867327409837027408226711480456194976671845861236572856040618756539095678223289140653377977334446403515187754876498199782623636172657979828431796308887294072384966509877204287082171152579890078673316983973.2 攻击脚本实现from gmpy2 import invert import binascii def common_modulus_attack(n, c1, c2, e1, e2): def egcd(a, b): if b 0: return a, 1, 0 else: g, x, y egcd(b, a % b) return g, y, x - (a // b) * y # 计算s1和s2 g, s1, s2 egcd(e1, e2) # 处理负数情况 if s1 0: s1 -s1 c1 invert(c1, n) if s2 0: s2 -s2 c2 invert(c2, n) # 计算明文 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return m # 执行攻击 result common_modulus_attack(n, c1, c2, e1, e2) print(Decrypted message:, result) print(Flag:, binascii.unhexlify(hex(result)[2:].strip(L)))3.3 代码逐行解析扩展欧几里得算法def egcd(a, b): if b 0: return a, 1, 0 else: g, x, y egcd(b, a % b) return g, y, x - (a // b) * y递归实现返回gcd(a,b)和系数x,y满足ax by gcd(a,b)负数指数处理if s1 0: s1 -s1 c1 invert(c1, n)当s₁为负时计算c₁的模逆元将指数转为正数明文恢复m (pow(c1, s1, n) * pow(c2, s2, n)) % n利用中国剩余定理组合两个计算结果4. 防御措施与最佳实践绝对避免的做法多个用户共享相同模数n重复使用素数p和q生成不同密钥对推荐方案1. **密钥生成规范** - 每个实体独立生成密钥对 - 使用安全随机数生成素数 2. **加密增强** - 添加随机填充如OAEP - 对同一消息使用不同随机数 3. **系统设计检查** - 定期审计密钥生成流程 - 验证n的唯一性5. CTF中的扩展应用常见变种题型多组共模攻击2组密文结合中国剩余定理的题型部分密钥泄露场景解题技巧对比表攻击类型所需条件典型特征解题步骤共模攻击相同n不同e提供多组(e,c)对1. 检查gcd(e₁,e₂)12. 应用扩展欧几里得算法低加密指数小e值e3或e5直接开e次方根维纳攻击d较小e非常大连分数分解6. 密码学安全启示通过BUUCTF RSA3这道题我们深刻认识到数学基础的重要性欧几里得算法等基础数论知识是理解现代密码学的关键实现细节的致命性看似微小的实现错误如模数复用可能导致整个系统崩溃防御性编程的必要性在开发加密系统时必须严格遵循密码学标准和建议在实际项目中遇到类似场景时我的经验是永远假设攻击者会获得所有公开参数设计系统时要确保即使在这种情况下也能保持安全性。共模攻击这类漏洞之所以危险正是因为它们利用了看似无害的参数共享。