RSA 共模攻击实战：BUUCTF RSA3 双密文单模数场景，Python 3.11 脚本 5 步解密

RSA 共模攻击实战从双密文单模数到明文还原引言在CTF竞赛中RSA共模攻击是一种经典且实用的密码学攻击技术。当同一明文使用相同的模数n但不同的公钥指数e1和e2进行加密时如果这两个指数互质攻击者就能在不获取私钥的情况下恢复原始明文。本文将深入剖析BUUCTF RSA3题目的解题过程通过Python 3.11实现完整的攻击流程并解释背后的数学原理。1. 共模攻击原理与数学基础1.1 RSA加密机制回顾RSA加密的核心在于欧拉定理的应用选择两个大素数p和q计算n p × q计算欧拉函数φ(n) (p-1)(q-1)选择公钥指数e满足1 e φ(n)且gcd(e, φ(n)) 1计算私钥d ≡ e⁻¹ mod φ(n)加密过程c ≡ mᵉ mod n解密过程m ≡ cᵈ mod n1.2 共模攻击成立条件当以下条件满足时共模攻击可行同一明文m用相同模数n加密使用两个不同的公钥指数e₁和e₂gcd(e₁, e₂) 1即两指数互质1.3 攻击的数学推导根据扩展欧几里得算法存在整数s₁和s₂使得e₁·s₁ e₂·s₂ 1利用加密结果c₁ ≡ mᵉ¹ mod n和c₂ ≡ mᵉ² mod n可通过以下计算恢复明文m ≡ c₁ˢ¹ · c₂ˢ² mod n2. 实战环境准备2.1 题目参数分析给定BUUCTF RSA3题目参数n 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801 e1 11187289 e2 9647291 c1 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 c2 187020100451870155565486916423949828356692621472302127313099386752264585552104259724294184492734105353879859310367118542656239050668056657518032691068807467690034789007910995902395139254497488140759040174715855728484735564905654500626647064491284158347879619472662597897859629222387011340797204142284140661930714953046123410529874556159300235368238014992697733571860874527475008406404193650115544211830375056534612867327409837027408226711480456194976671845861236572856040618756539095678223289140653377977334446403515187754876498199782623636172657979828431796308887294072384966509877204287082171152579890078673316983972.2 工具与库准备需要安装Python的gmpy2和binascii库pip install gmpy23. 共模攻击实现步骤3.1 扩展欧几里得算法实现def extended_gcd(a, b): if b 0: return a, 1, 0 else: gcd, x, y extended_gcd(b, a % b) return gcd, y, x - (a // b) * y3.2 模逆运算处理当s₁或s₂为负数时需要计算模逆from gmpy2 import invert if s1 0: c1 invert(c1, n) s1 -s1 if s2 0: c2 invert(c2, n) s2 -s23.3 完整攻击脚本from gmpy2 import invert import binascii def rsa_common_modulus_attack(n, c1, c2, e1, e2): # 计算扩展欧几里得系数 gcd, s1, s2 extended_gcd(e1, e2) # 处理负指数情况 if s1 0: c1 invert(c1, n) s1 -s1 if s2 0: c2 invert(c2, n) s2 -s2 # 计算明文 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return m # 执行攻击 plaintext rsa_common_modulus_attack(n, c1, c2, e1, e2) print(Decrypted message:, plaintext) print(Flag:, binascii.unhexlify(hex(plaintext)[2:].strip(L)))4. 数学原理深度解析4.1 扩展欧几里得算法算法通过递归求解gcd(a,b)的同时找到满足贝祖等式ax by gcd(a,b)的整数x和y。对于互质的e₁和e₂必有gcd(e₁,e₂)1因此存在s₁和s₂使得e₁s₁ e₂s₂ 1。4.2 模运算性质应用利用模运算的幂次性质m ≡ m¹ ≡ m^(e₁s₁ e₂s₂) ≡ (m^e₁)^s₁ · (m^e₂)^s₂ ≡ c₁^s₁ · c₂^s₂ mod n4.3 负指数处理当s₁或s₂为负数时需要先计算c₁或c₂的模逆元因为c⁻ˢ ≡ (c⁻¹)ˢ mod n5. 防御措施与变种分析5.1 共模攻击防御方案避免密钥重用同一模数不应被多个用户共享填充方案使用OAEP等随机填充方案密钥管理确保每个加密实例使用独立密钥对5.2 攻击变种场景多组密文攻击当有k组(eᵢ, cᵢ)时要求gcd(e₁,...,eₖ)1部分密钥暴露结合已知私钥部分信息可增强攻击侧信道攻击组合与计时攻击等结合可突破更多限制6. CTF实战技巧与调试6.1 常见问题排查模逆计算失败检查gcd(c,n)1大数运算溢出使用gmpy2库处理大整数编码转换错误注意hex解码时的字节顺序6.2 性能优化技巧# 使用gmpy2的powmod替代Python内置pow from gmpy2 import powmod as pow # 并行计算大数幂模 m1 pow(c1, abs(s1), n) m2 pow(c2, abs(s2), n)7. 完整代码与测试案例7.1 可重用攻击类实现class RSACoModulusAttacker: def __init__(self, n, e1, e2, c1, c2): self.n n self.e1 e1 self.e2 e2 self.c1 c1 self.c2 c2 def attack(self): gcd, s1, s2 extended_gcd(self.e1, self.e2) assert gcd 1, Exponents must be coprime if s1 0: self.c1 invert(self.c1, self.n) s1 -s1 if s2 0: self.c2 invert(self.c2, self.n) s2 -s2 return (pow(self.c1, s1, self.n) * pow(self.c2, s2, self.n)) % self.n # 使用示例 attacker RSACoModulusAttacker(n, e1, e2, c1, c2) flag attacker.attack() print(binascii.unhexlify(hex(flag)[2:].strip(L)))7.2 单元测试验证import unittest class TestRSACoModulusAttack(unittest.TestCase): def test_attack(self): # 生成测试密钥 from Crypto.Util.number import getPrime p getPrime(512) q getPrime(512) n p * q phi (p-1)*(q-1) # 生成互质的e1,e2 from math import gcd e1 65537 e2 65539 while gcd(e1, e2) ! 1: e2 2 # 测试明文 m 1234567890 c1 pow(m, e1, n) c2 pow(m, e2, n) # 执行攻击 attacker RSACoModulusAttacker(n, e1, e2, c1, c2) recovered attacker.attack() self.assertEqual(m, recovered) if __name__ __main__: unittest.main()8. 密码学安全实践建议密钥生成规范使用安全随机数生成器遵循NIST等标准密钥长度要求对p和q进行强素数检验加密实现要点# 安全加密示例 from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP key RSA.generate(2048) cipher PKCS1_OAEP.new(key) ciphertext cipher.encrypt(bSecret message)系统安全设计实现密钥轮换机制结合对称加密处理长明文部署入侵检测监控异常解密请求通过本实战演练我们不仅掌握了RSA共模攻击的技术细节更深入理解了公钥密码系统的安全边界。在CTF竞赛和实际安全评估中这类攻击强调了对加密方案全面风险分析的重要性。