1. 从零吃透RSA为什么它是CTF密码学里的“常驻嘉宾”RSA这个名词只要接触过密码学或者打过CTF的人都不会陌生。它几乎是每场CTF密码学方向必出的题型也是很多新手入门公钥密码学的第一道坎。我刚开始打CTF那会儿看到RSA题目就头疼——一堆大整数、几个模运算、莫名其妙的e和n完全不知道从哪下手。后来刷了几十道题、踩了无数坑之后才慢慢摸清了它的脾气。这篇文章就是把我学习RSA的完整路径和常见CTF题型的解题思路整理出来附带可以直接复用的解题脚本适合刚接触CTF密码学方向的新手也适合想系统梳理RSA攻击手法的老手参考。RSA的核心价值在于它是第一个能同时用于加密和数字签名的公钥密码体制安全性建立在大整数分解难题之上。在CTF比赛中出题人往往会故意削弱RSA的某些参数——比如e取特别小、n可以被分解、模数之间有公因数、私钥d过小等等——从而构造出可解的题目。我们要做的就是识别出题人留下的“后门”用对应的攻击手法把明文m还原出来。整篇文章会从RSA的数学基础讲起然后逐个拆解CTF中常见的几种RSA题型每种题型都配上原理说明、解题步骤和可直接运行的Python脚本。最后我会分享一些实战中总结的排查技巧和避坑经验这些都是文档里不会写的干货。2. RSA数学基础快速过一遍别怕公式其实就三件事2.1 密钥生成的三步走RSA的密钥生成说起来就三步但每一步都藏着CTF的出题点。第一步选两个大素数p和q计算n p * q。这个n就是模数公开出去。第二步计算欧拉函数φ(n) (p-1)(q-1)然后选一个整数e满足1 e φ(n)且gcd(e, φ(n)) 1。这个e就是公钥指数通常取65537。第三步计算私钥d满足e * d ≡ 1 (mod φ(n))也就是d是e在模φ(n)下的乘法逆元。加密的时候密文c m^e mod n。解密的时候明文m c^d mod n。签名就是反过来用私钥加密、公钥验证。这里有个关键点RSA的安全性完全依赖于n难以被分解成p和q。一旦n被分解φ(n)就能算出来d就能求出来整个系统就崩了。CTF题目里大量的攻击手法本质上都是在想办法分解n或者绕过分解直接求d。2.2 模运算和逆元解题的两把钥匙模运算在RSA里无处不在但真正高频用到的就两个操作模幂和模逆。模幂就是算a^b mod nPython里直接用pow(a, b, n)就行底层是快速幂算法效率很高。模逆就是求a在模n下的逆元满足a * x ≡ 1 (mod n)Python 3.8以后可以直接用pow(a, -1, n)老版本用gmpy2.invert(a, n)或者扩展欧几里得算法自己写。我见过很多新手卡在模逆这一步其实只要记住只有当gcd(a, n) 1的时候逆元才存在。如果gcd不等于1说明a和n不互素这时候要么题目出错了要么就需要用更高级的攻击手法比如后面会讲的公因数攻击。2.3 常见参数含义速查为了方便后面讲题的时候不反复解释这里先把RSA题目里常见的参数列个表参数含义在题目中的角色n模数等于p*q公开通常很大e公钥指数公开常见65537或3d私钥指数保密攻击目标p, q两个大素数保密分解n可得c密文公开需要解密m明文最终目标φ(n)欧拉函数值等于(p-1)(q-1)dp, dqd mod (p-1), d mod (q-1)有时会泄露这张表建议截图保存做题的时候对着看能省不少翻资料的时间。3. CTF中RSA题型的分类与识别思路3.1 拿到题目先看什么我拿到一道RSA题第一反应不是急着写脚本而是先做三件事看n的大小、看e的值、看有没有额外泄露的参数。这三件事基本能决定用哪种攻击手法。n特别小比如小于512位直接尝试用factordb或者yafu分解。e特别小比如等于3考虑小公钥指数攻击。题目给了dp、dq或者p、q的高位那就有对应的泄露攻击。如果给了两组以上的n和c而且n之间可能有公因数那就试试公因数攻击。提示做题前先把题目给的所有参数抄到纸上或者记事本里标清楚哪些是已知的、哪些是未知的。这个习惯能帮你快速定位攻击方向。3.2 题型分类总览根据我刷题的经验CTF里的RSA题目大致可以分成以下几类基础分解类n可以直接分解或者通过factordb能查到小公钥指数类e很小明文m也很小导致m^e n直接开方就行低加密指数广播攻击同一个m用不同的n加密e相同且很小公因数攻击多个n之间有公共因子dp/dq泄露类题目给了dp或dq可以推导出p或q共模攻击同一个n不同的e加密同一个mWiener攻击d过小Boneh-Durfee攻击d比Wiener攻击的界限稍大一点Coppersmith相关攻击已知p或q的高位/低位或者明文的高位每一类都有对应的脚本模板下面我会逐个拆解。4. 常见RSA题型实战拆解与脚本实现4.1 基础分解n能直接分解的情况这是最简单的一类题通常出现在新手赛或者签到题里。题目给的n不大可能就几百位用factordb一查就出来了。如果factordb查不到可以用yafu或者sage里的factor()函数分解。我一般先用factordb在线查查不到再用yafu本地跑。yafu的用法很简单命令行输入yafu-x64.exe factor(n)就行。如果n有几百位且没有特殊结构分解可能需要很长时间这时候就要考虑是不是有其他攻击手法。分解出p和q之后直接算d然后解密from Crypto.Util.number import long_to_bytes, inverse n 123456789 # 替换成题目给的n e 65537 c 987654321 # 替换成题目给的c p 12345 # 分解得到的p q 67890 # 分解得到的q phi (p - 1) * (q - 1) d inverse(e, phi) m pow(c, d, n) print(long_to_bytes(m))这段脚本我用了无数次基本是所有RSA题目的起点。注意inverse函数在Python 3.8以后可以直接用pow(e, -1, phi)替代效果一样。4.2 小公钥指数攻击e3且m很小当e取3的时候如果明文m比较小满足m^3 n那么c m^3直接对c开三次方就能得到m。这种情况在CTF里很常见出题人故意把e设成3然后明文就是一个短字符串。判断方法很简单算一下c的立方根如果立方根的立方等于c那就直接开方成功。如果m^3稍微大于n一点点可以尝试c k*n再开方k从0开始遍历。import gmpy2 from Crypto.Util.number import long_to_bytes n 123456789 e 3 c 987654321 for k in range(10000): m, exact gmpy2.iroot(c k * n, e) if exact: print(long_to_bytes(int(m))) break这个脚本的核心是gmpy2.iroot函数它返回一个元组第二个元素表示是否精确开方。k的遍历范围一般设10000就够了如果超过这个范围还没找到说明不是小公钥指数攻击。4.3 低加密指数广播攻击同一明文多个模数这类题目的特征是给了多组(n, c)e相同且很小通常是3而且这些n互素。根据中国剩余定理我们可以把多组同余式合并得到一个在模N n1n2...*nk下的密文然后直接开e次方。攻击的前提是e组密文对应的模数乘积大于m^e。如果e3一般给3组就够了。import gmpy2 from Crypto.Util.number import long_to_bytes from sympy.ntheory.modular import crt ns [n1, n2, n3] # 替换成题目给的多个n cs [c1, c2, c3] # 替换成对应的c e 3 # 中国剩余定理合并 N, C crt(ns, cs) m, exact gmpy2.iroot(C, e) if exact: print(long_to_bytes(int(m)))这里用了sympy的crt函数比自己手写中国剩余定理方便很多。注意crt返回的C可能不是最小的非负解但开方的时候不影响。4.4 公因数攻击多个n共享素因子如果题目给了多个n而且这些n之间可能有公共因子直接两两求gcd就行。这种情况通常出现在出题人偷懒用随机数生成器生成p和q的时候种子相同导致不同n之间共享了p或者q。from math import gcd from Crypto.Util.number import long_to_bytes, inverse ns [n1, n2, n3, n4] # 题目给的多个n e 65537 cs [c1, c2, c3, c4] # 对应的c for i in range(len(ns)): for j in range(i 1, len(ns)): p gcd(ns[i], ns[j]) if p ! 1: q1 ns[i] // p q2 ns[j] // p # 解密第i组 phi1 (p - 1) * (q1 - 1) d1 inverse(e, phi1) m1 pow(cs[i], d1, ns[i]) print(long_to_bytes(m1)) # 解密第j组 phi2 (p - 1) * (q2 - 1) d2 inverse(e, phi2) m2 pow(cs[j], d2, ns[j]) print(long_to_bytes(m2))这个脚本会遍历所有n的组合找到有公因数的那些。实际比赛中n的数量可能很多两两求gcd的复杂度是O(k^2)k一般不超过10完全够用。4.5 dp/dq泄露已知私钥分量有些题目会故意泄露dp d mod (p-1)或者dq d mod (q-1)。这种情况下我们可以利用以下关系恢复p由dp的定义可知e * dp ≡ 1 (mod (p-1))即e * dp - 1 k * (p-1)其中k是某个整数且k e。我们可以遍历k从1到e-1检查(e * dp - 1)是否能被k整除如果能那么p (e * dp - 1) // k 1再验证p是否能整除n。from Crypto.Util.number import long_to_bytes, inverse n 123456789 e 65537 dp 987654321 c 111111111 for k in range(1, e): if (e * dp - 1) % k 0: p (e * dp - 1) // k 1 if n % p 0: q n // p phi (p - 1) * (q - 1) d inverse(e, phi) m pow(c, d, n) print(long_to_bytes(m)) break这个脚本的关键在于k的遍历范围是1到e-1因为e * dp - 1 k * (p-1)且k e。实际跑起来很快e65537的话最多遍历6万多次秒出结果。4.6 共模攻击同一模数不同公钥指数如果题目给了同一个n两个不同的ee1和e2互素以及对应的c1和c2而且明文m相同那么可以用扩展欧几里得算法求出s1和s2使得s1 * e1 s2 * e2 1然后m c1^s1 * c2^s2 mod n。from Crypto.Util.number import long_to_bytes import gmpy2 n 123456789 e1 65537 e2 17 c1 111111111 c2 222222222 g, s1, s2 gmpy2.gcdext(e1, e2) if s1 0: s1 -s1 c1 gmpy2.invert(c1, n) if s2 0: s2 -s2 c2 gmpy2.invert(c2, n) m (pow(c1, s1, n) * pow(c2, s2, n)) % n print(long_to_bytes(m))注意s1和s2可能有一个是负数这时候需要对c求逆元。这个细节很多新手会忽略导致脚本报错。4.7 Wiener攻击私钥d过小当d n^0.25 / 3的时候可以用连分数逼近的方法从e/n的连分数展开中恢复d。Wiener攻击的原理是利用e/n ≈ k/d这个近似关系通过连分数展开找到k/d的收敛子。from Crypto.Util.number import long_to_bytes import gmpy2 def continued_fraction(n, d): cf [] while d: q n // d cf.append(q) n, d d, n - q * d return cf def convergents(cf): convs [] for i in range(len(cf)): if i 0: convs.append((cf[0], 1)) elif i 1: convs.append((cf[1] * cf[0] 1, cf[1])) else: num cf[i] * convs[i-1][0] convs[i-2][0] den cf[i] * convs[i-1][1] convs[i-2][1] convs.append((num, den)) return convs def wiener_attack(n, e): cf continued_fraction(e, n) convs convergents(cf) for k, d in convs: if k 0: continue if (e * d - 1) % k ! 0: continue phi (e * d - 1) // k # 解方程 x^2 - (n - phi 1)x n 0 b n - phi 1 discriminant b * b - 4 * n if discriminant 0: continue sqrt_disc gmpy2.isqrt(discriminant) if sqrt_disc * sqrt_disc ! discriminant: continue p (b sqrt_disc) // 2 q (b - sqrt_disc) // 2 if p * q n: return d return None n 123456789 e 65537 c 111111111 d wiener_attack(n, e) if d: m pow(c, d, n) print(long_to_bytes(m))Wiener攻击的脚本稍微长一点但逻辑很清晰先求e/n的连分数展开然后计算收敛子对每个收敛子检查是否能恢复出正确的p和q。实际比赛中如果看到e特别大接近nd可能就很小优先试Wiener攻击。4.8 Coppersmith攻击已知部分信息Coppersmith攻击是一类利用格基约简的方法可以在已知p或q的部分比特、或者已知明文的部分比特的情况下恢复完整信息。这类攻击通常需要用sage来跑因为sage内置了small_roots函数。比如已知p的高位可以用以下脚本恢复p# 需要在sage环境中运行 n 123456789 e 65537 c 111111111 p_high 12345 # p的高位 kbits 64 # 未知的低位数 PR.x PolynomialRing(Zmod(n)) f p_high * 2^kbits x roots f.small_roots(X2^kbits, beta0.4) if roots: p p_high * 2^kbits int(roots[0]) q n // p phi (p - 1) * (q - 1) d inverse_mod(e, phi) m pow(c, d, n) print(bytes.fromhex(hex(m)[2:]))Coppersmith攻击的难点在于参数beta和X的设置需要根据已知信息的比例来调整。一般来说已知p的高位越多beta可以设得越大攻击越容易成功。5. 实战排查技巧与常见坑点5.1 拿到题目后的排查流程我总结了一个排查流程基本能覆盖90%以上的RSA题目先看n的位数小于512位直接尝试分解看e的值e3优先试小公钥指数攻击看题目给了几组(n, c)多组优先试广播攻击和公因数攻击看有没有dp、dq、p高位、d等额外参数有就试对应的泄露攻击以上都不行试Wiener攻击和Coppersmith攻击这个流程能帮你快速定位攻击方向避免在错误的方向上浪费时间。5.2 常见报错与解决方法报错信息原因解决方法ValueError: base is not invertiblec和n不互素说明c和n有公因数直接gcd(n, c)分解nOverflowError: int too large整数太大用gmpy2替代内置pow开方结果不对k遍历范围不够增大k的遍历范围连分数攻击失败d不够小尝试Boneh-Durfee攻击small_roots返回空beta或X设置不对调整参数重新尝试注意如果c和n不互素这其实是个好消息因为gcd(n, c)直接就是p或者q等于白送一个分解。5.3 脚本复用的经验我建议把常用的RSA攻击脚本整理成一个工具库每个攻击手法写成一个函数用的时候直接调用。比如# rsa_tools.py from Crypto.Util.number import long_to_bytes, inverse import gmpy2 def basic_attack(n, e, c, p, q): phi (p - 1) * (q - 1) d inverse(e, phi) return long_to_bytes(pow(c, d, n)) def small_e_attack(n, e, c, max_k10000): for k in range(max_k): m, exact gmpy2.iroot(c k * n, e) if exact: return long_to_bytes(int(m)) return None def common_factor_attack(n1, n2, e, c1, c2): p gmpy2.gcd(n1, n2) if p 1: return None q1 n1 // p q2 n2 // p phi1 (p - 1) * (q1 - 1) phi2 (p - 1) * (q2 - 1) d1 inverse(e, phi1) d2 inverse(e, phi2) return long_to_bytes(pow(c1, d1, n1)), long_to_bytes(pow(c2, d2, n2))这样每次做题只需要导入这个模块调用对应的函数就行能省很多时间。我个人的习惯是每遇到一种新题型就把脚本补充到工具库里日积月累就成了一本自己的RSA攻击手册。5.4 出题人视角常见陷阱打了这么多比赛我发现出题人最喜欢设的几个陷阱e3但m^3 n这时候直接开方不行需要尝试k*n cn看起来很大但其实是两个相近素数的乘积可以用费马分解给了dp但没给n需要先通过其他方式恢复n多组n但只有一组有公因数需要遍历所有组合明文经过编码解出来之后可能需要hex解码或者base64解码这些陷阱我都踩过最坑的一次是e3但m^3刚好比n大一点点试了k1就出来了当时没想到要遍历k卡了半个多小时。6. 写在最后一些个人体会RSA题目做多了之后我发现它其实是一个“模式识别”的游戏。每种攻击手法都有明显的特征只要见得够多拿到题目基本能秒判用哪种方法。我建议新手从最简单的分解题开始逐步过渡到小公钥指数、公因数、共模攻击最后再啃Wiener和Coppersmith这些硬骨头。另外一定要自己动手写脚本不要直接抄网上的。抄来的脚本你永远不知道里面的参数为什么这么设遇到变种题目就懵了。自己写一遍哪怕写得丑一点理解会深刻很多。最后分享一个小技巧如果比赛的时候卡住了不妨把题目里的所有参数重新抄一遍检查有没有漏掉什么信息。我有好几次都是重新读题的时候发现题目还给了个hint之前完全没注意到。RSA题目有时候就是这样答案就藏在细节里。