1. 初识RSA共模攻击当两个公钥共享模数在CTF密码学挑战中RSA共模攻击Common Modulus Attack是一种经典场景。想象这样一个情境Alice和Bob分别用不同的公钥(e1,n)和(e2,n)加密了同一份明文而攻击者恰好截获了这两份密文。这时如果两个公钥指数e1和e2互质就能利用扩展欧几里得算法恢复出原始明文——这就是共模攻击的核心思想。我曾在BUUCTF平台上遇到这样一道题题目给出了两个密文c1、c2对应的公钥分别是(e111187289, n)和(e29647291, n)。最关键的线索是——这两个加密使用了相同的模数n。这就像用同一把锁配了两把不同的钥匙只要找到数学上的关联就能打开保险箱。2. 攻击原理深度拆解从数学到代码2.1 欧几里得算法的妙用首先需要理解扩展欧几里得算法Extended Euclidean Algorithm。这个算法不仅能计算两个数的最大公约数还能找到满足贝祖等式的整数解。对于互质的e1和e2必然存在整数s1、s2使得e1*s1 e2*s2 1在Python中我们可以这样实现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) * y2.2 密文的魔法组合得到s1和s2后神奇的事情发生了由于密文c1 ≡ m^e1 mod nc2 ≡ m^e2 mod n将它们按特定方式组合m ≡ c1^s1 * c2^s2 mod n这个等式成立是因为c1^s1 * c2^s2 ≡ (m^e1)^s1 * (m^e2)^s2 ≡ m^(e1*s1 e2*s2) ≡ m^1 ≡ m mod n2.3 处理负指数的技巧实际计算时s1或s2可能是负数。这时需要用到模逆元from gmpy2 import invert if s1 0: c1 invert(c1, n) s1 -s1 elif s2 0: c2 invert(c2, n) s2 -s23. 实战BUUCTF题目完整解析3.1 题目数据准备题目给出的关键参数n 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801 e1, e2 11187289, 9647291 c1 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 c2 187020100451870155565486916423949828356692621472302127313099386752264585552104259724294184492734105353879859310367118542656239050668056657518032691068807467690034789007910995902395139254497488140759040174715855728484735564905654500626647064491284158347879619472662597897859629222387011340797204142284140661930714953046123410529874556159300235368238014992697733571860874527475008406404193650115544211830375056534612867327409837027408226711480456194976671845861236572856040618756539095678223289140653377977334446403515187754876498199782623636172657979828431796308887294072384966509877204287082171152579890078673316983973.2 完整攻击脚本from gmpy2 import invert import binascii def common_modulus_attack(n, c1, c2, e1, e2): 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) * y _, s1, s2 extended_gcd(e1, e2) if s1 0: c1 invert(c1, n) s1 -s1 elif s2 0: c2 invert(c2, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return m plaintext common_modulus_attack(n, c1, c2, e1, e2) print(Decrypted integer:, plaintext) flag binascii.unhexlify(hex(plaintext)[2:].strip(L)) print(Flag:, flag)3.3 关键步骤解析计算贝祖系数通过扩展欧几里得算法找到s1和s2处理负指数对负指数对应的密文取模逆元组合密文按照公式计算c1^s1 * c2^s2 mod n转换明文将得到的整数转换为字节串运行后会输出Decrypted integer: 13040004482819947212936436796507286940525898188874967465457845309271472287032383337801279101 Flag: bflag{49d91077a1abcb14f1a9d546c80be9ef}4. 防御措施与变种题型4.1 实际应用中的防护虽然共模攻击在CTF中很常见但真实场景中可以通过以下方式防御避免模数复用每个用户使用独立的np*q填充随机化采用OAEP等填充方案使相同明文加密结果不同密钥管理规范遵循PKCS#1等标准4.2 相关变种题型在CTF中还可能遇到这些变种多组共模攻击提供多组(e,c)对时的攻击方式部分密钥暴露已知p或q的部分比特时的攻击广播攻击相同e加密相同明文给不同n的情况我曾遇到过一道需要组合共模攻击和中国剩余定理的题目解题的关键在于灵活运用数论知识。记住密码学的魅力就在于将抽象的数学转化为实际的攻击手段。5. 从理论到实践的思考通过这道BUUCTF题目我们不仅学会了共模攻击的技术实现更重要的是理解了RSA系统的脆弱性来源。当我第一次成功还原出flag时那种豁然开朗的感觉至今难忘——数学公式不再是课本上的符号而成了破解系统的利器。建议读者可以尝试修改脚本处理以下扩展场景当e1和e2不互质时该如何处理如果提供了三组以上的密文如何优化计算当n无法直接分解时共模攻击是否依然有效密码学的学习就是不断拆解和重组的过程。每次遇到新题型不妨先问这里的关键数学原理是什么代码实现会有哪些边界情况只有通过这样持续的思考和实践才能真正掌握加密与攻击的艺术。