从‘共享素数’到‘共模’：一次搞懂RSA在CTF中的两种‘非典型’攻击套路

从‘共享素数’到‘共模’：RSA在CTF中的两种非典型攻击模式深度解析

当你已经能够熟练完成RSA的基础加解密，却在CTF赛题中反复遭遇那些看似"违反常规"的题目时，是否曾感到困惑？本文将带你深入剖析两种常令参赛者头疼的攻击方式——共模攻击与模不互素攻击（共享素数攻击）。不同于教科书式的并列讲解，我们将从攻击逻辑的本质差异出发，构建一套完整的"攻击模式识别"框架。

1. 攻击模式的核心差异图谱

在CTF的Crypto类题目中，这两种攻击常被混淆，但它们的触发条件和数学原理截然不同。让我们先通过一个对比表格建立直观认知：

关键洞察：共模攻击利用的是加密指数的线性组合，而模不互素攻击则利用素数生成过程中的缺陷。

2. 共模攻击的数学原理与实战

2.1 攻击成立的条件链

共模攻击需要满足以下条件闭环：

1. 同一明文m使用相同模数N加密
2. 两组加密指数e₁和e₂互质（gcd(e₁,e₂)=1）
3. 攻击者能够获取两组密文c₁和c₂

攻击的核心在于利用扩展欧几里得算法重构明文。具体推导过程如下：

# 数学推导关键步骤伪代码 给定: c₁ ≡ m^e₁ mod N, c₂ ≡ m^e₂ mod N 通过扩展欧几里得找到s,t使得: e₁*s + e₂*t = 1 则: m ≡ c₁^s * c₂^t mod N

2.2 实战中的边界处理

在实际解题时，需要注意两个技术细节：

1. 负数指数处理：当s或t为负数时，需要先计算模逆元
2. 大数运算优化：使用gmpy2库提升计算效率

以下是一个典型题目的完整解题脚本：

from Crypto.Util.number import long_to_bytes import gmpy2 def common_modulus_attack(c1, c2, e1, e2, n): gcd, s, t = gmpy2.gcdext(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 新生赛]crypto2 实例 c1 = 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280 c2 = 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075 e1, e2 = 3247473589, 3698409173 n = 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313 print(common_modulus_attack(c1, c2, e1, e2, n))

3. 模不互素攻击的深入剖析

3.1 素数共享的脆弱性

当两个RSA模数N₁和N₂共享同一个素数因子时，系统安全性将彻底崩溃。攻击流程可分为三个关键步骤：

1. 素数提取：计算gcd(N₁,N₂)得到公共素数q
2. 模数分解：p₁ = N₁/q，p₂ = N₂/q
3. 私钥重构：分别计算φ(N₁)和φ(N₂)后求私钥d

3.2 典型攻击场景还原

以[羊城杯 2021]Bigrsa为例，题目设置了双重加密的陷阱：

m → c₁ = m^e mod N₁ → c₂ = c₁^e mod N₂

解题时需要逆向操作：

from math import gcd from Crypto.Util.number import inverse, long_to_bytes def shared_prime_attack(n1, n2, e, c): q = gcd(n1, n2) p1 = n1 // q p2 = n2 // q d1 = inverse(e, (p1-1)*(q-1)) d2 = inverse(e, (p2-1)*(q-1)) m = pow(pow(c, d2, n2), d1, n1) return long_to_bytes(m) # 题目数据 n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061 n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073 e = 65537 c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264 print(shared_prime_attack(n1, n2, e, c))

4. 防御方案与出题套路识别

4.1 出题者的常见陷阱设置

• 共模攻击题目特征：

  • 提供多组加密结果
  • 强调"相同消息不同加密"
  • 可能隐藏模数N相同的信息

• 模不互素攻击题目特征：

  • 提供多个公钥
  • 出现"双重加密"描述
  • 模数N具有相似位数

4.2 实际应用中的防护建议

对于开发者而言，需要建立以下安全实践：

1. 密钥生成规范：
   • 确保每次加密使用独立随机数
   • 使用强随机数生成素数
2. 系统架构检查：
   • 禁止模数重复使用
   • 定期检查密钥对之间的gcd关系
3. 加密方案选择：
   • 对相同消息采用OAEP等填充方案
   • 考虑结合AES的混合加密方案

在CTF比赛中遇到RSA异常情况时，建议按照以下流程快速诊断：

1. 检查所有可用模数N之间的关系
2. 验证是否存在相同模数不同指数的情况
3. 计算关键参数之间的gcd
4. 尝试标准攻击脚本的变种