1. 从一道解不出的RSA题说起：为什么值得系统整理

刚接触CTF那会儿，我在一道RSA题上卡了整整两天。题目给了一个n、一个e、一个c，看起来干净利落，但试了各种常规分解工具都跑不出结果。后来翻了不少资料才发现，问题根本不在工具，而在于我没搞清楚这道题到底属于哪一类攻击场景——是模数分解、低加密指数、共模攻击，还是其他变体。RSA题目的“外壳”往往长得很像，但内核完全不同，选错了攻击路径，再强的算力也是白费。

这也是我决定系统整理RSA学习和常见CTF题型的原因。RSA作为非对称加密的经典算法，在CTF密码学方向里出现频率极高，几乎每场比赛都会有一到两道。它的题型变化多端，但底层数学原理是固定的。只要把原理吃透，再配合几套可复用的解题脚本，大部分题目都能在短时间内定位到攻击方向。

这篇文章适合两类人：一是刚入门CTF密码学、对RSA还停留在“知道公式但不会做题”阶段的新手；二是做过一些RSA题、但解题思路比较零散、想建立系统方法论的中级选手。我会从RSA的数学基础讲起，然后逐一拆解几种最常见的CTF题型，每种题型都配上可运行的Python脚本和详细的参数说明。所有脚本都是我在实际比赛中反复验证过的，你可以直接拿去改参数用。

需要提前说明的是，本文涉及的数学推导和脚本实现，都是基于公开的密码学教材和CTF社区常见解法整理而成，属于学习研究范畴。实际应用中，RSA的安全性依赖于足够大的密钥长度和正确的实现方式，CTF题目中的“弱RSA”场景是为了教学目的而人为构造的。

2. RSA的数学骨架：不搞懂这些，脚本抄了也白抄

2.1 密钥生成的三步走和背后的数论逻辑

RSA的核心思想其实很朴素：利用“大整数分解困难”这个数学难题来构造单向陷门函数。密钥生成分三步：

第一步，选两个大素数p和q。这两个数必须足够大且随机，通常各取512位或1024位。为什么必须是素数？因为后续的模运算需要在模φ(n)下求逆元，而φ(n)的计算依赖于p和q的素性。

第二步，计算n = p * q和φ(n) = (p-1) * (q-1)。n是公开的模数，φ(n)是欧拉函数值，必须严格保密。这里有个关键点：φ(n)的保密性直接决定了RSA的安全性。如果攻击者能算出φ(n)，就能通过解方程p+q = n - φ(n) + 1和p*q = n来分解n。

第三步，选公钥指数e和计算私钥指数d。e通常取65537，这个值在二进制下只有两个1，加密时计算速度快。d是e在模φ(n)下的乘法逆元，即满足e * d ≡ 1 (mod φ(n))。求逆元用扩展欧几里得算法，Python里一行gmpy2.invert(e, phi)就能搞定。

加密过程是c = m^e mod n，解密是m = c^d mod n。正确性依赖于欧拉定理：当m与n互素时，m^φ(n) ≡ 1 (mod n)，所以m^(e*d) = m^(1 + k*φ(n)) ≡ m (mod n)。

注意：实际CTF题目中，m可能不与n互素，但这种情况概率极低，且不影响解密正确性，因为RSA的正确性证明可以扩展到m与n不互素的情况。

2.2 公钥私钥的表示格式：PEM、DER和CTF里的裸参数

实际比赛中，公钥和私钥可能以多种格式给出。最常见的是PEM格式，以-----BEGIN PUBLIC KEY-----开头，里面是Base64编码的DER数据。解析这种格式可以用Python的Crypto.PublicKey.RSA模块：

from Crypto.PublicKey import RSA with open('public.pem', 'rb') as f: key = RSA.import_key(f.read()) n = key.n e = key.e

但更多CTF题目会直接给出裸参数，比如n = 123456789...、e = 65537、c = 987654321...。这种反而好处理，直接赋值就行。还有一种情况是给出n和e，但n特别大，这时候就要考虑是不是需要分解n。

私钥格式也类似，PEM格式的私钥里包含n、e、d、p、q等参数，可以用RSA.import_key解析后直接取用。如果题目只给了d，那通常意味着需要用d来分解n，这是另一种攻击场景。

2.3 从加密解密到攻击：CTF题目的出题逻辑

CTF里的RSA题目，本质上都是在“人为削弱”RSA的某个环节，让攻击者有机可乘。常见的削弱方式包括：

• n太小，可以直接分解
• e太小，且m也小，导致m^e < n，直接开方即可
• 多组密文共用同一个n，但e不同，可以用共模攻击
• 多组密文共用同一个e，但n不同，且明文相同，可以用低加密指数广播攻击
• p和q太接近，可以用费马分解
• d太小，可以用维纳攻击
• 已知p的高位或低位，可以用Coppersmith攻击

每种攻击对应一套数学工具和脚本。下面我会逐一拆解，每种都给出完整的解题思路和可复用的代码。

3. 模数分解类题型：当n本身就不够硬

3.1 小n直接分解：factordb和yafu的实战取舍

最基础的RSA题目，n只有几十位到一百多位，直接用factordb在线查询或者yafu本地分解就能出结果。factordb是一个在线的整数分解数据库，很多CTF题目的n都是从这里生成的，直接查就能拿到p和q。

但factordb有个问题：如果题目用的是自定义的n，数据库里没有记录，就得靠本地工具。yafu是我用得最多的分解工具，命令行调用很简单：

yafu-x64.exe "factor(123456789012345678901234567890)"

它会自动选择试除法、Pollard rho、二次筛法等算法，对于200位以下的n，通常几秒到几分钟就能出结果。如果n超过300位，yafu可能就跑不动了，这时候要考虑是不是有其他攻击路径。

实操心得：拿到n之后，先别急着上工具。用Python的sympy.factorint试一下，如果n小于50位，基本秒出。如果不行，再上factordb查。最后才用yafu。这个顺序能省不少时间。

3.2 费马分解：p和q挨得太近就是送分题

当p和q非常接近时，n可以表示为((p+q)/2)^2 - ((p-q)/2)^2。因为p和q接近，所以(p-q)/2很小，(p+q)/2约等于sqrt(n)。费马分解就是从ceil(sqrt(n))开始，逐个尝试a，计算a^2 - n是否为完全平方数。

import gmpy2 def fermat_factor(n): a = gmpy2.isqrt(n) + 1 while True: b2 = a * a - n b = gmpy2.isqrt(b2) if b * b == b2: return a - b, a + b a += 1

这个脚本对于p和q相差不超过2^20的情况，通常几秒内就能出结果。但如果差距更大，循环次数会急剧增加。实际比赛中，如果题目暗示p和q接近（比如n的位数是p的两倍但p和q位数相同），优先试费马分解。

3.3 Pollard rho和二次筛法：中等规模n的通用解法

当n在100到250位之间，且p和q差距较大时，Pollard rho算法是比较好的选择。它的核心思想是利用生日悖论，在模n下寻找两个数x和y，使得gcd(|x-y|, n)给出一个非平凡因子。

import random from math import gcd def pollard_rho(n): if n % 2 == 0: return 2 x = random.randint(2, n - 1) y = x c = random.randint(1, n - 1) d = 1 while d == 1: x = (x * x + c) % n y = (y * y + c) % n y = (y * y + c) % n d = gcd(abs(x - y), n) return d

这个脚本对于n有较小因子的情况效果很好，但如果n是两个大素数的乘积，Pollard rho的复杂度是指数级的，跑起来会很慢。这时候就需要二次筛法（QS）或数域筛法（NFS），但这些算法的实现比较复杂，CTF中一般不会要求手写，用yafu或msieve就行。

注意：Pollard rho的随机性很强，同样的n可能跑几次才出结果。如果一次没出，换个随机种子再试。

4. 低加密指数攻击：e太小，明文直接“漏”出来

4.1 小e小m：直接开方就完事了

当e = 3且明文m很小时，m^e可能小于n，这时候c = m^e，直接对c开e次方就能得到m。

import gmpy2 def small_e_attack(c, e): m, exact = gmpy2.iroot(c, e) if exact: return int(m) return None

这个脚本的逻辑很简单：gmpy2.iroot(c, e)返回c的e次方根，如果结果是精确的（exact为True），那m就是我们要的明文。如果m^e略大于n，但m^e < 2n，那c = m^e - n，这时候需要对c + k*n开方，k从0开始尝试。

def small_e_attack_with_k(c, e, n, max_k=1000): for k in range(max_k): m, exact = gmpy2.iroot(c + k * n, e) if exact: return int(m) return None

4.2 低加密指数广播攻击：同一明文，多个n，同一个e

如果同一明文m用相同的e和不同的n加密了多次，得到c1, c2, ..., ck，可以用中国剩余定理（CRT）恢复m^e，再开方。

from sympy.ntheory.modular import crt def broadcast_attack(c_list, n_list, e): # 用CRT求 m^e mod (n1*n2*...*nk) m_e, _ = crt(n_list, c_list) m, exact = gmpy2.iroot(m_e, e) if exact: return int(m) return None

这个攻击的前提是k >= e，且所有n两两互素。如果k < e，CRT恢复出的m^e可能不完整，需要结合其他方法。

实操心得：广播攻击的题目通常会给出至少e组密文和模数。如果只给了两组，但e = 3，那可能还需要配合其他攻击。另外，crt函数返回的是(m_e, modulus)，m_e是m^e mod (n1*n2*...*nk)，如果m^e小于这个乘积，那m_e就是m^e本身。

4.3 低加密指数与部分明文泄露的结合

有时候题目会给出明文的一部分，比如m = flag + padding，其中flag是已知的，padding是未知的。这时候可以用Coppersmith方法，在已知部分明文的情况下恢复完整明文。这个攻击需要用到SageMath，脚本相对复杂，但CTF中出现的频率不低。

# SageMath脚本 def coppersmith_partial_m(n, e, c, known_bits, known_value): R.<x> = PolynomialRing(Zmod(n)) f = (known_value + x)^e - c roots = f.small_roots(X=2^known_bits, beta=1) return roots

这个脚本的核心思想是构造多项式f(x) = (known_value + x)^e - c，然后找f(x) ≡ 0 (mod n)的小根。known_bits是未知部分的位数，known_value是已知部分的数值。

5. 共模攻击与相关变体：同一个n，不同e

5.1 经典共模攻击：gcd(e1, e2) = 1的情况

当同一明文m用同一个n但不同的e1和e2加密，得到c1和c2，且gcd(e1, e2) = 1时，可以用扩展欧几里得算法找到s1和s2，使得s1*e1 + s2*e2 = 1，然后m = c1^s1 * c2^s2 mod n。

import gmpy2 def common_modulus_attack(c1, c2, e1, e2, n): g, s1, s2 = gmpy2.gcdext(e1, e2) if g != 1: return None # 处理s1或s2为负数的情况 if s1 < 0: c1 = gmpy2.invert(c1, n) s1 = -s1 if s2 < 0: c2 = gmpy2.invert(c2, n) s2 = -s2 m = (pow(c1, s1, n) * pow(c2, s2, n)) % n return m

这个脚本的关键在于处理负指数：如果s1或s2是负数，需要对c1或c2求模逆元，然后把指数取正。

5.2 共模攻击的扩展：gcd(e1, e2) > 1的情况

如果gcd(e1, e2) = g > 1，那m^g可以被恢复，但m本身需要开g次方。这时候如果g很小，可以直接开方；如果g较大，可能需要结合其他信息。

def common_modulus_attack_extended(c1, c2, e1, e2, n): g, s1, s2 = gmpy2.gcdext(e1, e2) if s1 < 0: c1 = gmpy2.invert(c1, n) s1 = -s1 if s2 < 0: c2 = gmpy2.invert(c2, n) s2 = -s2 m_g = (pow(c1, s1, n) * pow(c2, s2, n)) % n m, exact = gmpy2.iroot(m_g, g) if exact: return int(m) return None

注意：如果g较大且m^g > n，开方可能不精确，这时候需要尝试m_g + k*n。

5.3 共模攻击的实战注意事项

共模攻击的题目通常会给出两组(e, c)，但有时候会给出更多组。如果有多组，可以两两组合尝试，或者用更通用的方法：把所有e和c配对，找到gcd为1的组合。

另外，共模攻击的前提是n相同。如果题目给了多个n，那可能是广播攻击或其他类型。区分这两种攻击的关键就是看n是否相同。

实操心得：共模攻击的脚本里，gmpy2.gcdext返回的s1和s2可能都是正数，也可能一正一负。处理负指数时，求模逆元是必须的。我见过有人忘了这一步，结果算出来的m是错的。

6. 私钥泄露与低解密指数攻击：d太小也是灾难

6.1 已知d分解n：从d反推p和q

如果题目给出了私钥d，那可以直接用d来分解n。原理是：e*d ≡ 1 (mod φ(n))，所以e*d - 1 = k*φ(n)，其中k是某个整数。通过尝试不同的k，可以找到φ(n)，进而分解n。

def factor_n_with_d(n, e, d): k = e * d - 1 # k = 2^t * r，其中r是奇数 t = 0 while k % 2 == 0: k //= 2 t += 1 r = k for _ in range(100): g = random.randint(2, n - 1) y = pow(g, r, n) if y == 1 or y == n - 1: continue for _ in range(t - 1): x = pow(y, 2, n) if x == 1: p = gcd(y - 1, n) q = n // p return p, q if x == n - 1: break y = x return None

这个脚本的核心是Miller-Rabin素性测试的变体，通过随机选取g，计算g^(r*2^i) mod n，找到非平凡平方根，从而分解n。

6.2 维纳攻击：d太小，连分数来救场

当d < n^0.25 / 3时，可以用维纳攻击。维纳攻击利用连分数逼近e/n，因为e/n ≈ k/d，其中k是某个整数。通过计算e/n的连分数展开，可以找到k/d的近似值，进而恢复d。

def wiener_attack(e, n): def continued_fraction(a, b): cf = [] while b: cf.append(a // b) a, b = b, a % b return cf def convergents(cf): conv = [] for i in range(len(cf)): if i == 0: conv.append((cf[0], 1)) elif i == 1: conv.append((cf[1] * cf[0] + 1, cf[1])) else: num = cf[i] * conv[i-1][0] + conv[i-2][0] den = cf[i] * conv[i-1][1] + conv[i-2][1] conv.append((num, den)) return conv cf = continued_fraction(e, n) conv = convergents(cf) for k, d in conv: if k == 0: continue if (e * d - 1) % k != 0: continue phi = (e * d - 1) // k # 解方程 x^2 - (n - phi + 1)x + n = 0 s = n - phi + 1 discriminant = s * s - 4 * n if discriminant < 0: continue sqrt_disc = gmpy2.isqrt(discriminant) if sqrt_disc * sqrt_disc != discriminant: continue p = (s + sqrt_disc) // 2 q = (s - sqrt_disc) // 2 if p * q == n: return p, q, d return None

这个脚本的连分数展开和渐进分数计算是核心。维纳攻击的题目通常会给出一个特别大的e（接近n），这时候就要考虑d是不是太小了。

6.3 低解密指数的边界条件与误判

维纳攻击的适用条件是d < n^0.25 / 3。如果d稍大一点，维纳攻击可能失败，但可以用Boneh-Durfee攻击，它的边界是d < n^0.292。不过Boneh-Durfee的实现更复杂，需要用到格基约简，CTF中出现的频率较低。

实操心得：维纳攻击的脚本里，连分数展开的精度很重要。如果e/n的连分数展开项数不够，可能找不到正确的k/d。我一般会把所有渐进分数都试一遍，而不是只试前几项。

7. 脚本工具箱：我常用的RSA解题模板

7.1 通用解密脚本：从参数到明文的一站式处理

下面这个脚本是我平时用得最多的RSA解题模板，涵盖了从参数解析到解密的完整流程：

import gmpy2 from Crypto.Util.number import long_to_bytes def rsa_decrypt(n, e, c, p=None, q=None, d=None): if p and q: phi = (p - 1) * (q - 1) d = gmpy2.invert(e, phi) elif d: pass else: raise ValueError("需要提供p和q，或者提供d") m = pow(c, d, n) return long_to_bytes(m) # 示例用法 n = 123456789 e = 65537 c = 987654321 p = 12345 q = 67890 print(rsa_decrypt(n, e, c, p=p, q=q))

这个脚本的优点是灵活：如果你有p和q，它会自动算d；如果你直接有d，它就直接解密。long_to_bytes把整数转成字节串，方便查看flag。

7.2 批量处理脚本：多组密文的自动化攻击

当题目给出多组(n, e, c)时，手动一个个试太慢。下面这个脚本可以自动判断攻击类型：

def auto_attack(data_list): # data_list = [(n, e, c), ...] if len(data_list) == 1: n, e, c = data_list[0] # 尝试小e攻击 m = small_e_attack(c, e) if m: return long_to_bytes(m) # 尝试分解n p, q = fermat_factor(n) if p and q: return rsa_decrypt(n, e, c, p=p, q=q) else: # 检查n是否相同 n_set = set(d[0] for d in data_list) if len(n_set) == 1: # 共模攻击 n = data_list[0][0] for i in range(len(data_list)): for j in range(i+1, len(data_list)): _, e1, c1 = data_list[i] _, e2, c2 = data_list[j] m = common_modulus_attack(c1, c2, e1, e2, n) if m: return long_to_bytes(m) else: # 广播攻击 c_list = [d[2] for d in data_list] n_list = [d[0] for d in data_list] e = data_list[0][1] m = broadcast_attack(c_list, n_list, e) if m: return long_to_bytes(m) return None

这个脚本的逻辑是：先判断数据组数，如果只有一组，尝试小e攻击和费马分解；如果有多组，检查n是否相同，相同则共模攻击，不同则广播攻击。

7.3 脚本调试中的常见坑与修复方法

调试RSA脚本时，最常见的坑有三个：

第一，gmpy2.iroot返回的是(root, exact)，很多人忘了检查exact，结果拿到一个错误的根。正确的做法是：

m, exact = gmpy2.iroot(c, e) if exact: # 正确处理

第二，pow(c, d, n)中的d可能是负数，这时候需要先求c的模逆元：

if d < 0: c = gmpy2.invert(c, n) d = -d m = pow(c, d, n)

第三，long_to_bytes对于大整数可能返回很长的字节串，如果明文是flag格式，可以用bytes.decode()转成字符串查看。

实操心得：我习惯在脚本里加一些print语句，输出中间结果，比如p、q、phi、d等。这样如果最后解密失败，可以快速定位是哪一步出了问题。

8. 从CTF到实际应用：RSA学习的延伸方向

CTF里的RSA题目虽然是为了比赛设计的，但背后的数学原理和攻击方法在实际密码学研究中都有对应。比如费马分解对应的是“弱密钥”问题，共模攻击对应的是“密钥复用”问题，维纳攻击对应的是“小私钥指数”问题。这些在实际系统中如果实现不当，都会导致严重的安全漏洞。

如果你想继续深入，我建议从两个方向入手：一是学习SageMath，它在处理格基约简、多项式求根等问题上比纯Python方便得多；二是研究Coppersmith方法，它在部分明文泄露、高位攻击等场景下非常有用。

另外，RSA的变体也值得关注，比如Rabin密码、Paillier加密等，它们在CTF中也偶尔出现。掌握了RSA的基础，这些变体上手会快很多。

最后分享一个小技巧：平时做题时，把每道题的n、e、c和解题脚本都保存下来，按攻击类型分类整理。时间长了，你就有了一个自己的“RSA题库”，遇到新题时先翻翻旧题，往往能找到相似的解法。我在实际比赛中用这个方法，至少省了一半的思考时间。