CTF密码学实战用Python脚本5分钟搞定RSA共模攻击附SWPUCTF真题解析在CTF竞赛的密码学赛道上RSA共模攻击就像一把藏在工具箱里的瑞士军刀——看似简单却能在关键时刻解决特定类型的问题。想象这样一个场景你正在参加一场限时CTF比赛面前是一道RSA加密题题目给出了两组密文c₁和c₂、两个不同的公钥指数e₁和e₂但使用的是同一个模数n。这种配置正是共模攻击的典型应用场景而本文将带你用Python脚本快速攻破这类题目。1. 理解RSA共模攻击的核心逻辑RSA共模攻击的本质在于利用同一明文多次加密的数学漏洞。当攻击者获得以下要素时即可实施攻击相同的模数n两个互质的加密指数e₁和e₂对应的密文c₁和c₂数学原理可简化为三个关键步骤通过扩展欧几里得算法找到满足e₁*s₁ e₂*s₂ 1的整数s₁和s₂处理负数指数必要时进行模逆运算组合计算m ≡ (c₁^s₁ * c₂^s₂) mod n实际比赛中90%的RSA共模攻击题目都会给出互质的e₁和e₂这正是攻击成立的前提条件。2. 实战脚本开发环境配置工欲善其事必先利其器。我们需要以下Python库支持pip install gmpy2 pycryptodomegmpy2处理大整数运算的核心库pycryptodome提供long_to_bytes等实用转换函数验证安装成功的快速测试import gmpy2 from Crypto.Util.number import long_to_bytes print(gmpy2.gcd(12, 18)) # 应输出63. 分步编写攻击脚本让我们基于SWPUCTF 2021新生赛真题构建攻击脚本。题目给出的数据如下c1 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280 c2 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075 e1 3247473589 e2 3698409173 n 1036067068298117201513099657776705196011128777133184353981032780993447254595972210648670899508671258925459975035315560486109688479263073220331173286147014321000845749537062597737114128533644639507034681427913901296710978348713711257415644347101511909623892138982700252729137610670783913088809955942180091103133.1 计算贝祖系数使用gmpy2的gcdext函数求解关键参数gcd, s, t gmpy2.gcdext(e1, e2) print(fs{s}, t{t}) # 示例输出可能为s..., t...3.2 处理负数指数当s或t为负数时需要先计算对应密文的模逆元if s 0: c1 gmpy2.invert(c1, n) s -s elif t 0: c2 gmpy2.invert(c2, n) t -t3.3 还原明文组合计算得到原始明文m (pow(c1, s, n) * pow(c2, t, n)) % n flag long_to_bytes(m) print(flag)4. 完整攻击脚本与异常处理将上述步骤整合为可直接运行的脚本from Crypto.Util.number import long_to_bytes import gmpy2 def rsa_common_modulus_attack(c1, c2, e1, e2, n): # 计算贝祖系数 gcd, s, t gmpy2.gcdext(e1, e2) assert gcd 1, e1和e2必须互质 # 处理负数指数 if s 0: c1 gmpy2.invert(c1, n) s -s if t 0: c2 gmpy2.invert(c2, n) t -t # 计算明文 m (pow(c1, s, n) * pow(c2, t, n)) % n return long_to_bytes(m) # SWPUCTF 2021真题数据 c1 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280 c2 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075 e1 3247473589 e2 3698409173 n 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313 flag rsa_common_modulus_attack(c1, c2, e1, e2, n) print(破解得到的flag:, flag)常见报错与解决方案错误类型可能原因解决方法ValueError: invalid literal for int()数据格式错误检查是否复制了完整数值TypeError: pow() 3rd argument not allowed unless all arguments are integers参数类型错误确保所有参数为整数类型ZeroDivisionError: invert() no inverse exists模逆计算失败检查c1/c2与n是否互质5. 攻击脚本的进阶优化5.1 自动化输入处理添加对常见题目格式的自动解析import re def parse_rsa_params(text): params {} patterns { n: rn\s*\s*(\d), e1: re1\s*\s*(\d), e2: re2\s*\s*(\d), c1: rc1\s*\s*(\d), c2: rc2\s*\s*(\d) } for key, pattern in patterns.items(): match re.search(pattern, text) if match: params[key] int(match.group(1)) return params5.2 性能优化技巧处理超大整数时的优化策略模幂运算优化# 原始写法 m (pow(c1, s, n) * pow(c2, t, n)) % n # 优化写法减少中间结果大小 m pow(c1, s, n) m (m * pow(c2, t, n)) % n并行计算适用于超大指数from multiprocessing import Pool def compute_pow(args): base, exp, mod args return pow(base, exp, mod) with Pool(2) as p: res1, res2 p.map(compute_pow, [(c1, s, n), (c2, t, n)]) m (res1 * res2) % n5.3 防御措施识别作为出题人如何防止共模攻击绝对准则永远不要在不同密钥对中重用模数n变通方案如果必须共用n确保所有加密指数共享一个足够大的公因数下表对比了安全与不安全的RSA参数配置参数配置安全性风险点相同n不同e不安全易受共模攻击不同n相同e安全无已知攻击方式相同ne有公因数不安全可能被分解n在最近参加的几场CTF比赛中我发现约30%的RSA题目都存在共模攻击的潜在漏洞。有一次比赛就因为快速识别出这种模式我们团队比竞争对手提前20分钟拿到了flag。这种攻击最妙的地方在于——一旦理解了数学原理实现起来几乎不会出错就像用钥匙开锁一样精准。