CTF实战从零破解BUUCTF的RSA共模攻击题第一次参加CTF比赛时看到密码学题目总有种无从下手的感觉。直到遇到那道改变我解题思路的RSA共模攻击题——它像一把钥匙打开了密码学实战的大门。今天我们就以BUUCTF平台上的RSA3题目为例用最直白的语言和可落地的代码带你体验完整的解题过程。1. 题目分析与环境准备拿到题目文件时通常会看到以下几个关键参数n 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801 e1 11187289 c1 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 e2 9647291 c2 187020100451870155565486916423949828356692621472302127313099386752264585552104259724294184492734105353879859310367118542656239050668056657518032691068807467690034789007910995902395139254497488140759040174715855728484735564905654500626647064491284158347879619472662597897859629222387011340797204142284140661930714953046123410529874556159300235368238014992697733571860874527475008406404193650115544211830375056534612867327409837027408226711480456194976671845861236572856040618756539095678223289140653377977334446403515187754876498199782623636172657979828431796308887294072384966509877204287082171152579890078673316983971.1 安装必要的Python库处理大整数运算需要gmpy2库的支持安装时可能会遇到以下问题# 推荐使用conda安装解决常见编译错误 conda install -c conda-forge gmpy2 # 或者使用pip安装预编译版本 pip install gmpy22.0.8 --only-binary :all:常见报错处理Microsoft Visual C 14.0 is required安装Visual Studio Build Toolsgmp.h not foundLinux系统需要先安装开发库sudo apt-get install libgmp-dev2. 共模攻击原理深度解析当两个不同的公钥使用相同的模数n时就可能存在共模攻击漏洞。其数学基础是扩展欧几里得算法的应用核心等式存在整数s₁和s₂使得 e₁s₁ e₂s₂ 1解密过程当s₁为负数时计算 c₁⁻¹ mod n当s₂为负数时计算 c₂⁻¹ mod n明文恢复m (c₁^s₁ × c₂^s₂) mod n为什么这能奏效因为 (c₁^s₁ × c₂^s₂) ≡ m^(e₁s₁ e₂s₂) ≡ m¹ ≡ m (mod n)关键在于e₁和e₂必须互质gcd(e₁,e₂)13. 分步编写攻击脚本让我们从零开始构建完整的攻击脚本import gmpy2 from gmpy2 import mpz, invert import binascii # 题目给出的参数 n mpz(22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801) e1 mpz(11187289) c1 mpz(22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361) e2 mpz(9647291) c2 mpz(18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397) 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 def common_modulus_attack(n, c1, c2, e1, e2): # 计算扩展欧几里得系数 g, s1, s2 extended_gcd(e1, e2) # 确保gcd(e1,e2)1 assert g 1, Exponents e1 and e2 must be coprime # 处理负数指数 if s1 0: s1 -s1 c1 invert(c1, n) if s2 0: s2 -s2 c2 invert(c2, n) # 计算明文 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return m # 执行攻击 m common_modulus_attack(n, c1, c2, e1, e2) print(解密得到的数字明文:, m) # 转换为字节字符串 flag binascii.unhexlify(hex(m)[2:].strip(L)) print(Flag:, flag)3.1 关键代码解析extended_gcd函数递归实现扩展欧几里得算法返回三个值gcd(a,b)以及系数x,y负数指数处理if s1 0: s1 -s1 c1 invert(c1, n)当s₁为负时计算c₁的模逆元因为 c₁^s₁ ≡ (c₁⁻¹)^|s₁| mod n大数运算优化使用gmpy2的mpz类型处理超大整数pow函数的三参数形式实现模幂运算4. 实战调试与问题排查即使有了完整代码实际运行中仍可能遇到各种问题。以下是几个常见坑点4.1 数据类型问题错误现象OverflowError: cannot convert long to mpz without overflow解决方案# 所有大整数都用mpz()包裹 n mpz(227080...)4.2 编码转换问题当得到数字明文后转换为flag时需要注意# 正确做法去掉末尾可能的L字符 hex_str hex(m)[2:].strip(L) # 处理奇数长度情况 if len(hex_str) % 2 ! 0: hex_str 0 hex_str flag binascii.unhexlify(hex_str)4.3 性能优化技巧对于极大的指数运算可以预先计算模数# 使用gmpy2的powmod比pow更快 from gmpy2 import powmod m (powmod(c1, s1, n) * powmod(c2, s2, n)) % n5. 解题后的思考与扩展成功拿到flag后妨思考几个深入问题为什么CTF中经常出现共模攻击题开发者容易重复使用相同的n考察选手对RSA底层数学的理解实际系统中的防御措施绝对不要在不同密钥对间共享模数使用标准库而非自己实现RSA添加随机填充如OAEP变种题目可能形式提供多个2密文和指数隐藏部分参数需要先推导结合其他加密方式嵌套# 扩展练习尝试解以下变种题目 n 123...456 e1, e2, e3 65537, 257, 41 c1, c2, c3 789...012, 345...678, 901...234 # 提示需要组合三个等式求解记住CTF密码学题的核心套路找到数学关系→转化为可计算问题→编写脚本自动化求解。共模攻击只是众多攻击手段中的一种掌握其原理后你会发现很多题目都是类似思路的不同变种。