从‘共享素数’到‘共模’RSA在CTF中的两种非典型攻击模式深度解析当你已经能够熟练完成RSA的基础加解密却在CTF赛题中反复遭遇那些看似违反常规的题目时是否曾感到困惑本文将带你深入剖析两种常令参赛者头疼的攻击方式——共模攻击与模不互素攻击共享素数攻击。不同于教科书式的并列讲解我们将从攻击逻辑的本质差异出发构建一套完整的攻击模式识别框架。1. 攻击模式的核心差异图谱在CTF的Crypto类题目中这两种攻击常被混淆但它们的触发条件和数学原理截然不同。让我们先通过一个对比表格建立直观认知特征维度共模攻击模不互素攻击触发条件相同N不同e不同N之间存在非1公约数数学基础扩展欧几里得算法最大公约数(GCD)分解攻击目标直接恢复明文m分解N获取私钥典型题目特征提供两组(e,c)对相同m加密提供两个不同N的公钥防御措施避免重复使用模数确保不同密钥对的素数完全独立关键洞察共模攻击利用的是加密指数的线性组合而模不互素攻击则利用素数生成过程中的缺陷。2. 共模攻击的数学原理与实战2.1 攻击成立的条件链共模攻击需要满足以下条件闭环同一明文m使用相同模数N加密两组加密指数e₁和e₂互质gcd(e₁,e₂)1攻击者能够获取两组密文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 N2.2 实战中的边界处理在实际解题时需要注意两个技术细节负数指数处理当s或t为负数时需要先计算模逆元大数运算优化使用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₂共享同一个素数因子时系统安全性将彻底崩溃。攻击流程可分为三个关键步骤素数提取计算gcd(N₁,N₂)得到公共素数q模数分解p₁ N₁/qp₂ N₂/q私钥重构分别计算φ(N₁)和φ(N₂)后求私钥d3.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 实际应用中的防护建议对于开发者而言需要建立以下安全实践密钥生成规范确保每次加密使用独立随机数使用强随机数生成素数系统架构检查禁止模数重复使用定期检查密钥对之间的gcd关系加密方案选择对相同消息采用OAEP等填充方案考虑结合AES的混合加密方案在CTF比赛中遇到RSA异常情况时建议按照以下流程快速诊断检查所有可用模数N之间的关系验证是否存在相同模数不同指数的情况计算关键参数之间的gcd尝试标准攻击脚本的变种
