CTF RSA 共模攻击原理剖析：从欧几里得算法到 2 组密钥的明文恢复

CTF RSA 共模攻击原理深度解析从贝祖等式到明文恢复实战1. 密码学挑战中的共模攻击场景在CTF竞赛的密码学板块中RSA共模攻击Common Modulus Attack是一类经典题型。设想这样一个场景同一段明文m使用相同的模数n但不同的加密指数e1和e2进行加密得到密文c1和c2。此时若e1与e2互质攻击者无需分解n即可恢复明文——这正是共模攻击的核心要义。攻击成立的关键条件相同模数n用于多组加密两组加密指数e1、e2满足gcd(e1,e2)1攻击者能够获取两组密文c1、c2# 典型CTF题目参数结构示例 n 0xabcdef... # 公共模数 e1, e2 65537, 10001 # 互质的加密指数 c1 pow(m, e1, n) # 第一组密文 c2 pow(m, e2, n) # 第二组密文2. 数论基础扩展欧几里得算法共模攻击的数学基础是贝祖定理Bézouts identity对于任意整数a、b存在整数x、y使得a*x b*y gcd(a,b)当gcd(e1,e2)1时算法能求出满足e1*s1 e2*s2 1的整数s1和s2。这正是破解的关键def extended_gcd(a, b): if b 0: return a, 1, 0 else: g, x, y extended_gcd(b, a % b) return g, y, x - (a // b) * y # 计算系数示例 g, s1, s2 extended_gcd(17, 65537) assert g 1 and 17*s1 65537*s2 1算法可视化流程步骤abqa//bra%bxy1e117e265537017102655371738552013172811-385542120-830841510--17-655373. 攻击原理的数学推导利用扩展欧几里得算法得到的系数s1、s2我们可以重构原始明文由加密公式c1 ≡ m^e1 mod nc2 ≡ m^e2 mod n计算s1和s2使得e1*s1 e2*s2 1明文恢复公式m ≡ c1^s1 * c2^s2 mod n为什么这个公式有效因为c1^s1 * c2^s2 ≡ (m^e1)^s1 * (m^e2)^s2 mod n ≡ m^(e1*s1 e2*s2) mod n ≡ m^1 mod n ≡ m注意当s1或s2为负数时需要先计算模逆元。例如若s10则计算c1_inv pow(c1, -1, n)然后使用pow(c1_inv, -s1, n)4. 实战中的边界处理实际CTF解题时需要处理以下特殊情况情况1系数为负数if s1 0: c1 pow(c1, -1, n) # 模逆元计算 s1 -s1 elif s2 0: c2 pow(c2, -1, n) s2 -s2情况2大数运算优化# 分段计算避免内存溢出 part1 pow(c1, s1, n) if s1!0 else 1 part2 pow(c2, s2, n) if s2!0 else 1 m (part1 * part2) % n完整攻击脚本示例from Crypto.Util.number import long_to_bytes def common_modulus_attack(n, e1, e2, c1, c2): g, s1, s2 extended_gcd(e1, e2) if s1 0: c1 pow(c1, -1, n) s1 -s1 if s2 0: c2 pow(c2, -1, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return long_to_bytes(m) # BUUCTF-RSA3示例参数 n 0xabcdef... # 实际题目中的模数 e1, e2 11187289, 9647291 c1 0x223220... c2 0x187020... print(common_modulus_attack(n, e1, e2, c1, c2))5. 与传统RSA解密的对比特性共模攻击传统RSA解密所需参数n, e1, e2, c1, c2n, d, c数学基础扩展欧几里得算法欧拉定理是否需要分解n否是需知道φ(n)时间复杂度O(log min(e1,e2))O(√n) 因式分解难度适用条件e1与e2互质任意有效的d6. 防御方案与最佳实践为防止共模攻击系统设计时应遵循密钥生成规范避免同一模数n被多个用户共用为不同用户生成独立的(p,q)对加密策略优化# 安全的使用方式示例 from Crypto.PublicKey import RSA def generate_key_pair(): key RSA.generate(2048) return { n: key.n, e: key.e, d: key.d, p: key.p, q: key.q } # 每个用户拥有独立的密钥对 user1_key generate_key_pair() user2_key generate_key_pair()Padding的必要性始终使用OAEP等填充方案避免裸RSA加密Textbook RSA7. 扩展应用与变种攻击共模攻击思想可延伸至以下场景多组密文情况 当有k组(ei,ci)且gcd(e1,e2,...,ek)1时可通过找到ai使得 Σai*ei 1 则 m ≡ Π ci^ai mod n广播攻击 当相同明文用不同ni加密e较小时可使用中国剩余定理恢复明文。from sympy.ntheory.modular import crt def broadcast_attack(enc_data): # enc_data [(e1, n1, c1), (e2, n2, c2), ...] e enc_data[0][0] # 假设所有e相同 residues [c for _,_,c in enc_data] moduli [n for _,n,_ in enc_data] m_e crt(moduli, residues)[0] # 中国剩余定理 m, exact gmpy2.iroot(m_e, e) return long_to_bytes(m)在真实CTF比赛中遇到这类题目时建议按照以下步骤操作检查是否满足gcd(e1,e2)1实施扩展欧几里得算法求系数处理可能的负指数情况组合计算结果恢复明文将长整数转换为字节串提交flag理解共模攻击不仅能帮助解决CTF挑战更能深化对RSA系统安全边界的认知——密码学方案的强度往往取决于其最薄弱的实现环节。