CTF RSA密码题从入门到实战：常见题型与解题脚本全解析

1. 从零吃透RSA：为什么它成了CTF密码题的“常驻嘉宾”

如果你打过几场CTF，大概率会有这样的体验：签到题做完，翻到Crypto分类，十道题里有六七道都跟RSA沾边。有时候给三个参数n、e、c让你求明文，有时候给一堆公钥文件让你找规律，还有时候参数长得离谱，一看就知道出题人埋了坑。RSA之所以成为密码学赛题的“钉子户”，核心原因有两个：一是它的数学原理足够经典，二是它的参数组合方式极其丰富，稍微变一下就能衍生出一种新题型。

这篇文章面向的是刚接触CTF密码方向、或者对RSA只停留在“知道大数分解”层面的朋友。我会从RSA的底层数学逻辑讲起，把我在实际比赛中遇到过的几种高频题型逐一拆解，每种题型配上可直接复用的解题脚本和参数推导过程。读完你至少能做到：看到一道RSA题，能快速判断它属于哪类攻击场景，知道该调用哪个脚本、改哪些参数。

先说清楚一件事：RSA的安全性建立在“大整数分解困难”这个假设上。公钥是(n, e)，私钥是(n, d)，其中n = p × q，p和q是两个大素数。加密就是c = m^e mod n，解密就是m = c^d mod n。看起来简单，但出题人可以在p、q的生成方式、e的取值、d的大小、甚至多组n之间的关系上做文章。每一种“不正常”的参数设置，都对应着一种攻击方法。

我在学习RSA的过程中踩过不少坑。最开始只会暴力分解小n，遇到稍微大一点的数就束手无策。后来才明白，CTF里的RSA题考的不是让你去分解一个2048位的n，而是考你能不能发现参数之间的“破绽”。比如两个模数共享了一个素因子，比如e取得特别小导致明文可以直接开方，比如d小到可以用连分数逼近。这些才是解题的钥匙。

下面我会按照“基础原理→常见题型→脚本实现→避坑经验”的顺序展开，每一部分都尽量给出完整的推导和可运行的代码。代码统一用Python 3编写，依赖的库主要是gmpy2、sympy和pycryptodome，这些在CTF环境里基本是标配。

2. RSA核心原理快速回顾：不搞数学竞赛，但要够用

2.1 密钥生成与加解密流程

RSA的密钥生成分四步走。第一步，随机选两个大素数p和q，计算n = p × q。第二步，计算欧拉函数φ(n) = (p-1)(q-1)。第三步，选一个整数e，满足1 < e < φ(n)且gcd(e, φ(n)) = 1，通常e取65537。第四步，计算d = e^(-1) mod φ(n)，也就是e在模φ(n)下的乘法逆元。公钥是(n, e)，私钥是(n, d)。

加密过程：把明文m转成整数（通常用bytes_to_long），要求m < n，然后计算c = pow(m, e, n)。解密过程：m = pow(c, d, n)，再把整数转回字节。

这里有个细节很多人一开始会忽略：m必须小于n。如果明文比n还大，就需要分块加密，但CTF题里一般不会这么设计，因为分块会让题目变得复杂且容易出问题。所以当你发现解出来的m转成字节后是乱码，第一反应应该是检查是不是m >= n导致取模丢失了信息。

2.2 为什么e通常取65537

e取65537不是随便定的。首先65537是素数，满足gcd(e, φ(n)) = 1的概率很高。其次65537的二进制是10000000000000001，只有两个1，做模幂运算时需要的乘法次数很少，加密速度快。如果e取3，虽然更快，但会带来小指数攻击的风险——当明文m比较小时，m^3可能直接小于n，那么c = m^3，直接开三次方就能还原m。所以现代实践中e几乎固定为65537。

但在CTF里，出题人偏偏喜欢把e设成3、5、17这种小值，目的就是引导你去尝试小指数攻击。看到e=3的时候，先别急着套脚本，先算一下m^3是否小于n，如果小于，直接开方就完事了。

2.3 中国剩余定理在RSA中的应用

中国剩余定理（CRT）在RSA里有两个用途。一个是加速解密：把模n的运算拆成模p和模q的两组运算，最后合并。另一个是在攻击中：当你已知m mod p和m mod q时，可以用CRT还原m mod n。

CRT的公式：如果p和q互素，那么对于任意a和b，存在唯一的x mod (p×q)满足x ≡ a (mod p)且x ≡ b (mod q)。计算方法是x = a + p × ((b - a) × p^(-1) mod q)。

在CTF中，CRT常用于“已知部分明文”或“多组同余方程”的题型。比如题目给了你m mod p和m mod q的值，你就能直接还原m。或者题目给了你多组(c_i, n_i)且明文相同，也可以用CRT扩展攻击。

3. 常见CTF题型逐一拆解：从签到题到压轴题

3.1 小模数直接分解：最基础的入门题

这是RSA题里最简单的一类。题目给的n很小，可能只有几十位到一百多位十进制数，用工具直接分解就行。我常用的方法是先用sympy的factorint试一下，如果太慢就换yafu或者在线分解网站。

from sympy import factorint from Crypto.Util.number import long_to_bytes n = 1234567890123456789012345678901234567890 # 题目给的n e = 65537 c = 987654321098765432109876543210987654321 factors = factorint(n) p, q = list(factors.keys()) phi = (p - 1) * (q - 1) d = pow(e, -1, phi) m = pow(c, d, n) print(long_to_bytes(m))

这类题的关键是判断n到底有多小。一般来说，如果n的十进制位数在60位以下，factorint几秒钟就能出结果。如果到了100位左右，可能需要几分钟。超过150位，基本就别指望直接分解了，得换思路。

注意：factorint返回的是一个字典，键是素因子，值是指数。如果n是多个素数的乘积，需要把所有素因子都取出来。但标准RSA题里n通常只有两个素因子。

3.2 共享素因子攻击：两个n之间的秘密

这类题的特征是给了你两个或更多的n值。如果这些n之间共享了素因子，那么直接求最大公约数就能分解。

from math import gcd from Crypto.Util.number import long_to_bytes n1 = ... n2 = ... e = 65537 c1 = ... c2 = ... p = gcd(n1, n2) if p != 1: q1 = n1 // p q2 = n2 // p phi1 = (p - 1) * (q1 - 1) d1 = pow(e, -1, phi1) m1 = pow(c1, d1, n1) print(long_to_bytes(m1))

这个攻击的原理很简单：如果n1 = p × q1，n2 = p × q2，那么gcd(n1, n2) = p。一旦拿到p，两个n就都分解了。

我在实际比赛中遇到过变种：题目给了三组n，其中两组共享素因子，第三组是干扰项。这时候需要对所有n两两求gcd，找到非1的那个组合。写脚本的时候直接双重循环遍历就行。

实操心得：有些题目的n看起来很大，但出题人为了构造共享素因子，会故意用同一个随机数生成器。这种情况下，gcd几乎一定能出结果。如果两两求gcd都是1，那说明不是这个题型，得换方向。

3.3 小指数攻击：e=3时的开方与爆破

当e取3时，如果明文m比较小，满足m^3 < n，那么c = m^3，直接对c开三次方即可。但更多时候，出题人会加一个k×n的偏移，即c = m^3 + k×n。这时候需要爆破k，对c + k×n开三次方，直到结果能转成有意义的字节。

import gmpy2 from Crypto.Util.number import long_to_bytes n = ... e = 3 c = ... for k in range(100000): m, exact = gmpy2.iroot(c + k * n, e) if exact: print(long_to_bytes(int(m))) break

gmpy2.iroot返回一个元组，第一个元素是整数根，第二个元素是布尔值表示是否精确。这个函数比用pow(c, 1/3)靠谱得多，因为浮点数精度不够。

如果e=3且明文比较大，m^3 > n，但出题人可能把明文分成了三块，每块都小于n的三次方根。这种情况下需要更复杂的处理，但CTF里少见。

注意：爆破k的上限要根据题目给的c和n的大小关系来估计。如果c远大于n，k可能很大；如果c和n差不多大，k通常很小。我一般从0开始爆到100000，绝大多数题都能出结果。

3.4 低解密指数攻击：d小到可以用连分数逼近

这类题的特征是e特别大，几乎和n一样大。这是因为d很小，而e × d ≡ 1 mod φ(n)，所以e ≈ φ(n) / d。当d < n^0.25时，可以用Wiener攻击，通过连分数逼近e/n来恢复d。

from fractions import Fraction 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)): num, den = 1, 0 for j in range(i, -1, -1): num, den = cf[j] * num + den, num convs.append(Fraction(num, den)) return convs def wiener_attack(e, n): cf = continued_fraction(e, n) for frac in convergents(cf): k, d = frac.numerator, frac.denominator if k == 0: continue phi = (e * d - 1) // k if (e * d - 1) % k != 0: continue s = n - phi + 1 discriminant = s * s - 4 * n if discriminant < 0: continue sqrt_disc = gmpy2.isqrt(discriminant) if sqrt_disc * sqrt_disc == discriminant: p = (s + sqrt_disc) // 2 q = (s - sqrt_disc) // 2 if p * q == n: return d return None

Wiener攻击的数学推导稍微复杂一点，但核心思想是：e/n的连分数展开中，某个收敛项的分母就是d。实际写脚本的时候，直接用现成的库或者抄一份经过验证的代码就行，不需要自己从头推导。

实操心得：Wiener攻击的适用条件是d < n^0.25 / 3。如果d稍微大一点，Wiener可能失败，这时候可以尝试Boneh-Durfee攻击，但那个实现起来复杂得多，CTF里出现频率也低。

3.5 共模攻击：同一n下多组密文

如果题目给了同一个n、同一个e，但有两组不同的(c1, e1)和(c2, e2)，且gcd(e1, e2) = 1，那么可以用扩展欧几里得算法求出s1和s2使得e1×s1 + e2×s2 = 1，然后m = c1^s1 × c2^s2 mod n。

from math import gcd def egcd(a, b): if b == 0: return a, 1, 0 g, x, y = egcd(b, a % b) return g, y, x - (a // b) * y n = ... e1, e2 = ... c1, c2 = ... g, s1, s2 = egcd(e1, e2) if g == 1: if s1 < 0: s1 = -s1 c1 = pow(c1, -1, n) if s2 < 0: s2 = -s2 c2 = pow(c2, -1, n) m = (pow(c1, s1, n) * pow(c2, s2, n)) % n print(long_to_bytes(m))

这个攻击的前提是e1和e2互素。如果它们不互素，比如都是偶数，那就没法直接用了。但出题人一般会保证互素，否则题目就没法解。

3.6 广播攻击：同一明文多组密文

如果题目给了多组(n_i, e_i, c_i)，且明文m相同，e_i都比较小（比如都是3），那么可以用中国剩余定理把c_i合并，然后开方。

from sympy.ntheory.modular import crt ns = [...] cs = [...] e = 3 # 用CRT合并 m_e, _ = crt(ns, cs) m, exact = gmpy2.iroot(int(m_e), e) if exact: print(long_to_bytes(int(m)))

广播攻击的条件是：明文相同、e相同且较小、n两两互素。如果n不互素，那就退化成共享素因子攻击了，反而更好解。

注意：CRT合并后的结果可能不是精确的e次方，因为c_i = m^e mod n_i，合并后得到的是m^e mod (n_1×n_2×...×n_k)。如果m^e小于所有n的乘积，那么合并结果就是m^e本身，直接开方即可。如果m^e大于乘积，就需要爆破。

4. 进阶题型与组合攻击：出题人开始上强度了

4.1 已知高位攻击：Coppersmith方法入门

这类题会给你p的高位或者m的高位，让你恢复完整的p或m。核心工具是Coppersmith方法，它可以在已知部分信息的情况下求解模多项式的小根。

# 需要安装sage环境，这里给出伪代码思路 # 假设已知p的高位p_high，未知低位有k位 # 构造多项式f(x) = p_high + x，在模p下求小根 # 使用sage的small_roots方法

Coppersmith方法在CTF里属于进阶内容，通常出现在压轴题里。它的数学基础是格基约简，实现起来需要sage环境。如果你只是偶尔打CTF，可以先把现成的脚本收集好，遇到题目直接改参数。

实操心得：已知高位攻击的关键是确定未知位的数量。如果未知位太多，Coppersmith会失败。一般来说，未知位数不能超过n的位数的1/4。比如n是1024位，未知位不能超过256位。

4.2 相关消息攻击：线性关系下的明文恢复

如果两个明文之间存在线性关系，比如m2 = a×m1 + b，且用同一个n和e加密，那么可以通过构造多项式来恢复m1。这类题在CTF里出现频率不高，但一旦出现就是难题。

4.3 模数不互素的变种：多组n的gcd分析

前面讲过两组n共享素因子的情况，但有时候题目会给很多组n，其中只有两组共享。这时候需要写脚本遍历所有组合，找到gcd不为1的那一对。

from math import gcd ns = [...] # 题目给的所有n for i in range(len(ns)): for j in range(i + 1, len(ns)): p = gcd(ns[i], ns[j]) if p != 1: print(f"Found shared factor between n[{i}] and n[{j}]: {p}")

这个脚本的时间复杂度是O(k^2)，k是n的个数。如果k很大（比如100个），可能需要优化，但CTF里k通常不超过10。

4.4 e与φ(n)不互素：当解密指数不存在时

标准RSA要求gcd(e, φ(n)) = 1，这样d才存在。但有些题目故意让e和φ(n)不互素，这时候解密就不是唯一的，需要额外处理。

假设gcd(e, φ(n)) = g > 1，那么e×d ≡ 1 mod φ(n)无解。但可以转化为求解m^e ≡ c mod n，这等价于在模p和模q下分别求解，然后用CRT合并。具体方法是：在模p下，m^e ≡ c mod p，由于e和p-1可能不互素，解可能有多个。需要遍历所有可能的解，再结合题目给的提示（比如明文是ASCII）来筛选。

# 伪代码思路 # 在模p下求解m^e ≡ c mod p # 如果g = gcd(e, p-1)，则有g个解 # 对每个解，在模q下也求解，然后CRT合并 # 最后筛选出可打印的明文

这类题在CTF里属于中等难度，关键是理解“解密不唯一”这个概念。我第一次遇到的时候卡了很久，后来才想明白需要在模p和模q下分别求解。

5. 解题脚本工具箱：我常用的几个模板

5.1 通用解密脚本框架

import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long def rsa_decrypt(n, e, c, p=None, q=None, d=None): if d is None: if p is None or q is None: raise ValueError("Need either d or both p and q") phi = (p - 1) * (q - 1) d = pow(e, -1, phi) m = pow(c, d, n) return long_to_bytes(m) # 使用示例 n = ... e = 65537 c = ... p = ... q = ... print(rsa_decrypt(n, e, c, p, q))

这个框架覆盖了最常见的解密场景。如果你已经有了p和q，直接传进去就行；如果只有d，也可以直接传d。

5.2 小指数爆破脚本

import gmpy2 from Crypto.Util.number import long_to_bytes def small_e_attack(n, e, c, max_k=100000): for k in range(max_k): m, exact = gmpy2.iroot(c + k * n, e) if exact: return long_to_bytes(int(m)) return None

这个脚本适用于e=3、5、7等小指数的情况。max_k可以根据c和n的大小关系调整。

5.3 共享素因子批量检测脚本

from math import gcd from Crypto.Util.number import long_to_bytes def shared_factor_attack(ns, es, cs): for i in range(len(ns)): for j in range(i + 1, len(ns)): p = gcd(ns[i], ns[j]) if p != 1: q = ns[i] // p phi = (p - 1) * (q - 1) d = pow(es[i], -1, phi) m = pow(cs[i], d, ns[i]) return long_to_bytes(m) return None

这个脚本会遍历所有n的组合，找到共享素因子的那一对，然后解密。

5.4 常用工具库速查表

注意：gmpy2在Windows上安装可能需要编译环境，建议用Linux或者WSL。如果实在装不上，可以用Python内置的pow和math模块替代，但大数运算会慢很多。

6. 踩坑实录与避坑指南：那些年我调脚本调到头秃

6.1 字节转换的坑：long_to_bytes的边界情况

long_to_bytes在转换时，如果整数是0，会返回空字节串。如果整数是负数，会报错。我在实际比赛中遇到过解出来的m是负数的情况，原因是计算过程中出现了减法。这时候需要先对m取模n，确保它是正数。

另外，long_to_bytes默认不补前导零。如果明文是b'\x00abc'，转换后可能变成b'abc'。这在大多数情况下不影响，但如果题目要求精确匹配，就需要注意。

6.2 开方的精度问题：为什么不能用pow(c, 1/3)

Python的浮点数精度有限，对于大整数开方，pow(c, 1/3)会丢失精度。比如c = 10^30，c的立方根是10^10，但浮点数可能算出来是9999999999.999999，取整后变成9999999999，差1就全错了。所以必须用gmpy2.iroot或者sympy.integer_nthroot。

6.3 爆破范围的确定：k到底要爆到多少

小指数攻击里，k的上限取决于m^e和n的关系。如果m^e < n，k=0就够了。如果m^e稍微大于n，k可能只有1或2。如果m^e远大于n，k可能很大。我一般先算一下c的位数和n的位数，如果c的位数和n差不多，k从0爆到1000就够了；如果c的位数比n大很多，可能需要爆到100000甚至更多。

6.4 多解情况的筛选：如何从多个候选中找到正确明文

当e和φ(n)不互素时，解密会有多个解。这时候需要根据题目给的提示来筛选。常见的筛选条件包括：明文是ASCII可打印字符、明文包含特定格式（如flag{...}）、明文的长度符合预期。我一般会写一个循环，把所有解都转成字节，然后打印出来人工看。

6.5 脚本调试技巧：打印中间变量

调试RSA脚本时，最有效的方法是在关键步骤打印中间变量。比如分解出p和q后，先验证p×q是否等于n；算出d后，验证e×d mod φ(n)是否等于1；解密出m后，验证pow(m, e, n)是否等于c。这些验证步骤能帮你快速定位问题。

实操心得：我习惯在脚本里加一个verify函数，每一步都验证一下。虽然多写几行代码，但能省下大量调试时间。

7. 从CTF到实战：RSA学习的延伸方向

打完CTF里的RSA题，你可能会想：这些攻击方法在真实场景里有用吗？答案是：部分有用，但真实场景的RSA实现要复杂得多。真实系统里会用到OAEP填充、CRT加速、盲签名等技术，参数生成也有严格的随机性要求。CTF里的攻击大多针对的是“参数配置错误”或“实现漏洞”，这些在规范实现中是不存在的。

但学习CTF的RSA攻击仍然有价值。它能帮你理解RSA的数学本质，知道哪些参数是敏感的，哪些操作是危险的。比如你现在肯定明白了：e不能取太小、d不能太小、p和q不能太接近、不同用户的n不能共享素因子。这些直觉在代码审计和渗透测试中非常有用。

如果你想继续深入，我建议的方向是：学习Coppersmith方法的数学原理、了解格基约简在密码分析中的应用、研究RSA填充方案的攻击（如Bleichenbacher攻击）。这些内容在CTF里属于高阶题型，在真实场景里也有对应的安全影响。

最后分享一个我个人的习惯：每次打完比赛，把遇到的RSA题和解题脚本整理到一个文件夹里，按题型分类。下次遇到类似的题，直接翻文件夹改参数就行。这个习惯让我在比赛中的解题速度快了很多，也避免了很多重复劳动。