企业官网建设流程全解析

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 n，Python里直接用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题目里常见的参数列个表：

这张表建议截图保存，做题的时候对着看，能省不少翻资料的时间。

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加密同一个m
• Wiener攻击：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 小公钥指数攻击：e=3且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。如果e=3，一般给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。实际跑起来很快，e=65537的话最多遍历6万多次，秒出结果。

4.6 共模攻击：同一模数不同公钥指数

如果题目给了同一个n，两个不同的e（e1和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特别大（接近n），d可能就很小，优先试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(X=2^kbits, beta=0.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题目：

1. 先看n的位数，小于512位直接尝试分解
2. 看e的值，e=3优先试小公钥指数攻击
3. 看题目给了几组(n, c)，多组优先试广播攻击和公因数攻击
4. 看有没有dp、dq、p高位、d等额外参数，有就试对应的泄露攻击
5. 以上都不行，试Wiener攻击和Coppersmith攻击

这个流程能帮你快速定位攻击方向，避免在错误的方向上浪费时间。

5.2 常见报错与解决方法

注意：如果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_k=10000): 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 出题人视角：常见陷阱

打了这么多比赛，我发现出题人最喜欢设的几个陷阱：

• e=3但m^3 > n：这时候直接开方不行，需要尝试k*n + c
• n看起来很大但其实是两个相近素数的乘积：可以用费马分解
• 给了dp但没给n：需要先通过其他方式恢复n
• 多组n但只有一组有公因数：需要遍历所有组合
• 明文经过编码：解出来之后可能需要hex解码或者base64解码

这些陷阱我都踩过，最坑的一次是e=3但m^3刚好比n大一点点，试了k=1就出来了，当时没想到要遍历k，卡了半个多小时。

6. 写在最后：一些个人体会

RSA题目做多了之后，我发现它其实是一个“模式识别”的游戏。每种攻击手法都有明显的特征，只要见得够多，拿到题目基本能秒判用哪种方法。我建议新手从最简单的分解题开始，逐步过渡到小公钥指数、公因数、共模攻击，最后再啃Wiener和Coppersmith这些硬骨头。

另外，一定要自己动手写脚本，不要直接抄网上的。抄来的脚本你永远不知道里面的参数为什么这么设，遇到变种题目就懵了。自己写一遍，哪怕写得丑一点，理解会深刻很多。

最后分享一个小技巧：如果比赛的时候卡住了，不妨把题目里的所有参数重新抄一遍，检查有没有漏掉什么信息。我有好几次都是重新读题的时候发现题目还给了个hint，之前完全没注意到。RSA题目有时候就是这样，答案就藏在细节里。