用钥匙模子破解保险箱一个面包店的故事理解RSA共模攻击想象你是一家百年面包店的继承人祖传秘方锁在保险箱里。这个保险箱有两道锁分别由两位性格迥异的锁匠设计——他们各自持有独特的钥匙模子但保险箱本身是同一个。有一天你发现这两位锁匠的模子竟然能组合成万能钥匙...这就是RSA共模攻击的奇妙之处。1. 面包店保险箱的双重防护机制我们的故事从一家名为RSA Bakery的面包店开始。老店主为了防止秘方泄露定制了一个特殊保险箱同一个保险箱n存放着价值连城的发酵配方第一位锁匠e₁习惯用顺时针旋转11圈的钥匙模子第二位锁匠e₂偏爱逆时针旋转9圈的钥匙模子两位锁匠互不相识但他们的模子有个关键特性11和9没有公约数数学上称为互素。就像两个毫无交集的齿轮却能意外组合出新的机械结构。这里的n代表RSA加密中的模数e₁和e₂是两个不同的公钥指数。现实生活中这类似于两家银行对同一保险柜设置不同的开启方式。2. 锁匠模子的神奇组合某天你同时拿到了两个锁匠的加密信息第一把锁的密文c₁秘方^11 mod n第二把锁的密文c₂秘方^9 mod n传统方法需要分别破解两把锁但聪明的你发现了一个捷径——扩展欧几里得算法。这个算法就像找到两个齿轮的完美啮合点def 找组合系数(e1, e2): # 扩展欧几里得算法的简化版 if e2 0: return 1, 0 else: x, y 找组合系数(e2, e1 % e2) return y, x - (e1 // e2) * y s1, s2 找组合系数(11, 9) # 得到s14, s2-5验证一下11×4 9×(-5) 44 - 45 1。这意味着我们可以构造出万能钥匙3. 锻造万能钥匙的步骤现在我们有了组合系数s₁4和s₂-5。负数次方在密码学中需要特殊处理处理负指数c₂⁻⁵ mod n (c₂⁻¹)⁵ mod n先计算c₂的模逆元组合计算结果from gmpy2 import invert def 破解保险箱(n, c1, c2, e1, e2): s1, s2 找组合系数(e1, e2) if s1 0: c1 invert(c1, n) s1 -s1 if s2 0: c2 invert(c2, n) s2 -s2 秘方 (pow(c1, s1, n) * pow(c2, s2, n)) % n return 秘方数学原理c₁ˢ¹ ≡ (秘方^e₁)^s₁ ≡ 秘方^(e₁·s₁) mod nc₂ˢ² ≡ (秘方^e₂)^s₂ ≡ 秘方^(e₂·s₂) mod n乘积等于秘方^(e₁s₁e₂s₂) ≡ 秘方¹ ≡ 秘方 mod n4. 实战破解BUUCTF的RSA3挑战让我们把这个面包店理论应用到CTF竞赛题中。给定以下数据n 2270807881588501146... # 一个非常大的数 e1, e2 11187289, 9647291 c1 2232203527566323704... c2 1870201004518701555... result 破解保险箱(n, c1, c2, e1, e2) print(hex(result)[2:]) # 输出十六进制结果运行后会得到flag的十六进制形式转换后即可获得flag{49d91077a1abcb14f1a9d546c80be9ef}。5. 安全启示与防御措施虽然这个攻击很巧妙但防范其实很简单不要共享模数每个用户应该使用独立的n使用大素数增加分解难度定期更换密钥降低被攻击窗口期就像面包店后来给每个锁匠都定制了不同的保险箱彻底解决了模数共享的风险。在实际开发中遵循以下原则def 生成安全RSA密钥(): import Crypto.PublicKey.RSA key Crypto.PublicKey.RSA.generate(2048) # 2048位密钥 return key.n, key.e, key.d # 每个用户独立生成记住这个面包店的故事下次遇到RSA共模攻击时你会立刻想到那两个能组合出万能钥匙的锁匠模子。这种生活化的理解方式比死记硬背公式要牢固得多——毕竟谁不喜欢一个关于面包和保险箱的精彩故事呢