从CTF实战出发：手把手教你用Python脚本破解RSA共模攻击（附完整代码）

从零构建RSA共模攻击实战框架数学原理与Python自动化破解1. 密码学竞赛中的RSA共模攻击场景还原在CTF密码学挑战中RSA共模攻击Common Modulus Attack是高频考点。当两组密文使用相同模数N但不同公钥指数e1、e2加密时若gcd(e1,e2)1则存在高效恢复明文的数学方法。这种攻击不依赖N的分解仅需两组密文和对应公钥即可实施。典型攻击场景特征给定参数(N, e1, c1)和(N, e2, c2)满足条件gcd(e1, e2) 1攻击目标恢复原始明文m2. 贝祖定理的密码学实践攻击核心在于贝祖定理Bézouts Identity的应用。该定理保证当gcd(e1,e2)1时存在整数s1、s2满足s1*e1 s2*e2 1通过扩展欧几里得算法可快速求解s1、s2。值得注意的是s1或s2可能为负数此时需计算模逆元import gmpy2 e1, e2 35422, 1033 g, s1, s2 gmpy2.gcdext(e1, e2) print(fs1{s1}, s2{s2}) # 示例输出s1233, s2-79933. 密文组合的数学魔法利用求得的系数可通过以下公式组合密文恢复明文m ≡ (c1^s1 * c2^s2) mod N推导过程由加密定义c1 ≡ m^e1 mod Nc2 ≡ m^e2 mod N对密文进行指数运算c1^s1 ≡ m^(e1*s1) mod Nc2^s2 ≡ m^(e2*s2) mod N乘积性质c1^s1 * c2^s2 ≡ m^(e1*s1 e2*s2) ≡ m^1 ≡ m mod N4. Python自动化攻击实现以下为完整攻击脚本包含异常处理和实战技巧from Crypto.Util.number import long_to_bytes import gmpy2 def common_modulus_attack(N, e1, c1, e2, c2): # 验证公钥指数是否互质 g, s1, s2 gmpy2.gcdext(e1, e2) if g ! 1: raise ValueError(e1和e2不互质无法执行标准共模攻击) # 处理负指数计算模逆元 if s1 0: c1 gmpy2.invert(c1, N) s1 -s1 if s2 0: c2 gmpy2.invert(c2, N) s2 -s2 # 组合密文恢复明文 m (pow(c1, s1, N) * pow(c2, s2, N)) % N return m # 实战数据示例 N 162178605357818616394571566923155907889899677780239882906511996614607940884142045197452389471499799373787832649318837814454679970724845203557871078001956378966434166323827984964942729898095347038272003371167123553368531662277059263517900162297903110415768403265100411543878859321181606008503516896600638590699 e1, c1 35422, 153249315480380808558746807096025628082875635601515291525075274335055878390662930254941118045696231628008256877302589689883059616503108946971165183674522403835250738176157466145855833767128209866527507862726083268576304163200171600023472544755768741118904892489037291247455823396160705615280802805803254323033 e2, c2 1033, 5823189490163315770684717059899864988806118565674660089157163486577056500243194221873916232616081138765317598078910078375360361118674333149663483360677725162911935082290640547407140413703664960164356579153623498735889314476063673352676918268911309402784919521792079943937126634436658784515914270266106683548 try: m common_modulus_attack(N, e1, c1, e2, c2) flag long_to_bytes(m) print(f[] 破解成功: {flag.decode()}) except Exception as e: print(f[-] 攻击失败: {e})5. 防御方案与攻击变种有效防御措施避免在不同密钥对中重用相同模数使用标准公钥指数如65537添加随机填充如OAEP攻击变种扩展多组密文攻击当存在多组(ei,ci)且gcd(e1,e2,...,en)1时可推广攻击方法非互质场景若gcd(e1,e2)d1在满足特定条件时仍可实施攻击结合中国剩余定理当获得多组(Ni,ci)时可能组合攻击提示实际CTF比赛中需注意密文编码Base64/Hex和整数转换的边界处理这是90%解题错误的根源。