CTF RSA入门实战：从公钥分解到明文恢复的完整指南

1. 项目概述：一次典型的CTF RSA入门题实战复盘

最近在带新人入门CTF（Capture The Flag）竞赛的Crypto（密码学）方向，发现很多朋友对RSA这个“老熟人”依然感到头疼。理论公式背得滚瓜烂熟，但一碰到稍微变化一点的题目就无从下手。正好，BJDCTF 2020中的一道名为“easyrsa”的题目，堪称是理解RSA基础攻击手法的绝佳教学案例。它没有复杂的数学变形，也没有刁钻的编码技巧，核心就是考察你对RSA几个最经典漏洞的敏感度和利用能力。这道题在BUU等各大CTF平台上流传甚广，几乎成了密码学新手的“必修课”。今天，我就以这道题为蓝本，带大家完整走一遍RSA基础题的解题思路，不仅告诉你“怎么做”，更重点拆解“为什么这么做”，以及过程中那些容易踩坑的细节。无论你是刚接触CTF的新手，还是想巩固RSA基础的同学，这篇复盘都能让你有所收获。

简单来说，这道“easyrsa”题目的场景非常典型：你拿到了一段加密信息（Ciphertext，密文）和用于加密的RSA公钥（通常包含模数n和指数e），你的目标就是破解这个加密，拿到里面的Flag（通常是一段有特定格式的字符串，如flag{...}）。题目之所以“easy”，是因为出题人故意在密钥生成过程中留下了安全漏洞，我们的任务就是找到并利用这些漏洞。下面，我们就从最基础的准备开始，一步步拆解。

2. 解题环境与核心工具准备

工欲善其事，必先利其器。解决RSA题目，尤其是CTF中的题目，离不开几个关键的工具和库。它们能帮助我们完成大数运算、质因数分解、模逆计算等核心操作。

2.1 Python密码学生态：gmpy2与PyCryptodome

Python是CTF密码学解题的绝对主力，主要依赖两个库：

1. gmpy2：这是我们的“重型武器库”。它是一个Python扩展模块，封装了著名的GMP（GNU Multiple Precision Arithmetic Library）库。为什么它如此重要？因为RSA涉及的数字动辄就是1024位、2048位甚至更长，Python原生的int类型虽然支持大数，但在进行模幂运算（比如计算c^d mod n）、求最大公约数（GCD）、模逆运算时效率远不及gmpy2。gmpy2提供了mpz类型，专门用于高精度数学运算，速度极快。

   • 安装：通常使用pip安装，但因为它依赖C库，在某些系统上可能需要预先安装GMP库的开发文件。在Linux上可以尝试pip install gmpy2，如果失败，可能需要先安装libgmp-dev。在Windows上，通常有预编译的轮子（wheel），安装相对顺利。
   • 核心用法：导入后，我们可以用gmpy2.mpz(123456)将普通整数转换为高精度整数，然后使用gmpy2.powmod(c, d, n)进行快速模幂运算，用gmpy2.gcd(a, b)求最大公约数，用gmpy2.invert(e, phi)求模逆元（即私钥d）。

2. PyCryptodome或Crypto：这是一个功能更全面的密码学工具库。在RSA解题中，我们主要用它来解析各种格式的密钥文件。例如，题目给出的公钥可能是一个PEM格式的文件（-----BEGIN PUBLIC KEY-----...），我们可以用Crypto.PublicKey.RSA.import_key()函数轻松地将其解析，直接提取出n和e。这比手动用正则表达式去解析要可靠得多。

   • 安装：pip install pycryptodome。注意，如果之前安装过旧的pycrypto，可能会有冲突，建议使用pycryptodome作为替代。
   • 一个常见坑点：有时导入时会写from Crypto import ...，但实际安装的包名是pycryptodome。如果导入失败，可以尝试from Cryptodome import ...。在解题时，根据环境灵活调整。

实操心得：建议在个人常用的解题环境（比如虚拟机或容器）中，预先配置好gmpy2和pycryptodome。很多线上CTF平台（如BUU）的题目环境可能已经安装，但自建环境时这一步必不可少。如果gmpy2安装困难，在简单题目中暂时用Python原生大数也可以，但遇到复杂运算会非常慢。

2.2 辅助分析与分解工具

除了编程库，还有一些在线工具和本地工具能极大提升效率：

1. RSACTFTool / RsaCtfTool：这是一个用Python编写的、功能极其强大的RSA攻击套件。它集成了数十种针对RSA的攻击方法，如维纳攻击、低加密指数攻击、共模攻击、费马分解、Pollard‘s p-1分解等。你只需要提供n, e, c等参数，它就能自动尝试各种攻击方式。对于这道“easyrsa”题，虽然我们可以手算，但用这个工具可以快速验证思路。它的强大之处在于“自动化尝试”，当你不确定是哪种漏洞时，让它跑一遍往往能有意外收获。

   • 使用：通常克隆Git仓库后运行python RsaCtfTool.py -n <modulus> -e <exponent> --uncipher <ciphertext>进行自动攻击。

2. factordb.com：这是一个神奇的网站。它收集了海量已知整数的分解结果。当你拿到一个模数n，第一件事就是把它丢到factordb上查一下。如果这个n是出题人用简单随机数生成的，或者是一个已知的、有特殊因子的数，很可能已经被别人分解过并收录在库中。对于“easyrsa”这类入门题，n很可能直接就能在factordb上查到分解。这常常是解题的“捷径”。

   • 技巧：不仅可以通过网页查询，factordb也有API，可以编写脚本进行交互式查询，方便批量解题。

3. yafu：一个本地运行的、功能强大的整数分解工具。当n无法在factordb上直接查到，且规模不大（比如小于512位）时，可以尝试用yafu进行分解。它内部集成了多种先进的分解算法（如SIQS、ECM）。对于CTF中常见的256位、512位RSA，yafu往往能在可接受的时间内完成分解。

准备好这些工具，我们就有了应对RSA题目的“武器库”。接下来，进入核心的解题思路分析环节。

3. 核心思路拆解：RSA的命门在哪里？

面对一道RSA题目，我们不能盲目地直接开始写代码。首先必须像一个侦探一样，审视题目给出的所有信息，寻找可能的突破口。RSA的安全性基于大整数分解的困难性，但这是在“正确使用”的前提下。如果使用不当，就会出现各种漏洞。对于“easyrsa”这类题目，突破口通常集中在以下几个经典场景：

3.1 模数n被分解

这是最直接、最根本的突破口。私钥d的计算依赖于欧拉函数 φ(n) = (p-1)*(q-1)。一旦我们分解n得到p和q，就能计算φ(n)，进而通过公式d = e^(-1) mod φ(n)算出私钥d。然后解密：m = c^d mod n。 所以，解题的第一步永远是：尝试分解模数n。 如何尝试？

1. 直接查询：将n（十进制或十六进制）提交到factordb网站。
2. 检查特殊性：n是否过小（如小于256位）？n是否有明显的规律（如由连续数字组成、是某个著名数字）？n是否可能由多个小素数相乘（光滑数）？这些都可能让分解变容易。
3. 利用历史漏洞：如果n在两个不同的加密中被重复使用（共模攻击不需要分解），或者n可以被分解为多个素数（多素数RSA），思路又会不同。

3.2 加密指数e过小或与φ(n)不互质

标准的RSA中，加密指数e通常取65537（0x10001），这是一个在安全性和加密效率之间取得平衡的值。但出题人有时会设置非常小的e，比如3、17等。这会导致两种攻击：

• 低加密指数攻击：当e很小，且明文m也很小（满足 m^e < n）时，加密过程c = m^e mod n实际上就等于m^e（因为模运算没有起作用）。那么，直接对密文c开e次方根就能得到明文m。在“easyrsa”中，如果发现e=3或e=5，并且n非常大，就要第一时间想到这种可能。
• e与φ(n)不互质：这是RSA正确性的前提。如果gcd(e, φ(n)) != 1，那么模逆元d就不存在，无法正常解密。出题人可能利用这一点构造题目，但这种情况在基础题中较少见。

3.3 解密指数d过小（维纳攻击）

如果私钥d相对于模数n来说太小，那么可以通过连分数展开的方法，在只知道公钥(n, e)的情况下恢复出私钥d。这被称为维纳攻击（Wiener‘s Attack）。在CTF题中，如果题目提示“快速解密”或给出了一个特别大的e，可能就是在暗示d很小。

3.4 共模攻击

如果同一段明文m，用相同的模数n，但不同的加密指数e1和e2进行了两次加密，得到了c1和c2，并且e1和e2互质（gcd(e1, e2)=1），那么就可以在不分解n、不知道私钥的情况下恢复明文。这利用了扩展欧几里得算法。题目如果给了两组或多组(n, e, c)，并且n相同，e不同，就要优先考虑共模攻击。

3.5 其他衍生攻击

此外，还有选择密文攻击、旁道攻击等，但在“easyrsa”这种入门题中，最可能出现的还是前三种：n可分解、低加密指数e、共模攻击。我们的解题流程，就是拿着这些“检查清单”，去一一核对题目给的条件。

4. 针对“easyrsa”的逐步实操与原理详解

由于我无法获取到“buu [BJDCTF2020]easyrsa”题目的实时数据（每次连接的n, e, c可能不同），我将基于这类题目的常见形态，模拟一个完整的解题过程，并阐述每一个步骤背后的原理和可能的变化。假设我们通过连接靶机，获得了以下数据（这是模拟的典型数据）：

• 模数 n:1455925529734358105461406532259911790807347616464991065301847
• 加密指数 e:65537
• 密文 c:0x358072d90058827e4c62e3e08c2c2c24d893f5c8

同时，我们还可能直接下载到一个pub.key公钥文件。下面我们分步骤拆解。

4.1 第一步：信息提取与初步观察

首先，我们需要从给定的信息中提取出n和e。有两种常见情况：

情况A：直接给出n和e的数值。如上所示，直接拿到了十进制或十六进制的n和e。这很简单，直接用于后续计算即可。注意，密文c可能是十六进制字符串，需要转换为整数。

情况B：给出一个PEM格式的公钥文件。这是更常见的形式。文件内容大致如下：

-----BEGIN PUBLIC KEY----- MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJU2FZqS0NxZRVK7jubUvCJqMoP6N5Q ... -----END PUBLIC KEY-----

我们需要解析这个文件来获得n和e。使用Python的PyCryptodome库可以轻松完成：

from Crypto.PublicKey import RSA with open('pub.key', 'r') as f: key_data = f.read() pub_key = RSA.import_key(key_data) n = pub_key.n e = pub_key.e print(f"n = {n}") print(f"e = {e}")

运行后，我们就得到了n和e的整数值。

初步观察要点：

1. 看e：这里e=65537，是标准值，排除了低加密指数攻击的可能性。
2. 看n的长度：我们模拟的n是25位十进制数，大约82比特。这是一个非常非常小的n！在实际的RSA应用中，n至少是1024位（308位十进制数），2048位或更高才是安全的。82比特的n在现代计算机面前，几乎可以瞬间被分解。这强烈提示我们，这道题的突破口就是直接分解n。

4.2 第二步：尝试分解模数n

对于一个小规模的n，我们有多种方法可以分解它。

方法一：使用factordb网站（最快捷）将我们的n1455925529734358105461406532259911790807347616464991065301847粘贴到 factordb.com 的搜索框。很可能得到如下结果：

1455925529734358105461406532259911790807347616464991065301847 = 126781637058993471779 · 11499854316217742903940404534393

（注：这里的因子是随机生成的示例，仅用于演示） 这样，我们就得到了两个质因子p和q。

方法二：使用yafu工具（本地分解）如果factordb上没有记录，我们可以使用yafu。将n保存到一个文件（比如n.txt），里面只包含这个数字。然后在命令行运行：

yafu "factor(1455925529734358105461406532259911790807347616464991065301847)"

或者使用因子分解模式：

yafu-x64.exe "factor(@)" -batchfile n.txt

yafu会自动选择算法，对于小整数，通常很快就能得出结果。

方法三：使用Python脚本尝试简单分解（学习原理）对于特别小的n，我们甚至可以写一个简单的试除法脚本。但请注意，这只适用于极小的数字（比如小于50位），对于稍大的数效率极低。

import gmpy2 import math n = gmpy2.mpz(1455925529734358105461406532259911790807347616464991065301847) # 试除法，仅用于演示，对本题的n不实用 def trial_division(n): i = gmpy2.mpz(2) while i * i <= n: if n % i == 0: return i, n // i i += 1 return None # 更实际的是使用gmpy2自带的next_prime或is_prime进行简单检查，但分解还是依赖专业工具或算法。

在实际解题中，方法一（factordb）通常是首选，因为它最快。如果不行，再考虑方法二（yafu）。

注意事项：分解n是RSA攻击的核心。在CTF中，出题人给出的n如果直接能在factordb上查到，这往往就是预期的解题路径。这考察的是选手对“已知攻击”和“资源利用”的熟悉程度，而不是真的让你去分解一个安全的大整数。

4.3 第三步：计算私钥d并解密

一旦我们得到了p和q，剩下的就是标准的RSA计算流程。让我们用Python来完成。

假设我们从factordb得到：

p = 126781637058993471779 q = 11499854316217742903940404534393

验证：p * q应该等于我们之前的n。

现在开始计算：

import gmpy2 # 给定参数 n = gmpy2.mpz(1455925529734358105461406532259911790807347616464991065301847) e = gmpy2.mpz(65537) c = gmpy2.mpz(0x358072d90058827e4c62e3e08c2c2c24d893f5c8) # 将十六进制密文转为整数 # 分解得到的p和q p = gmpy2.mpz(126781637058993471779) q = gmpy2.mpz(11499854316217742903940404534393) # 1. 计算欧拉函数 φ(n) = (p-1)*(q-1) phi_n = (p - 1) * (q - 1) # 2. 计算私钥d，即e关于φ(n)的模逆元 # d * e ≡ 1 (mod φ(n)) d = gmpy2.invert(e, phi_n) print(f"私钥d = {d}") # 3. 解密密文c，得到明文m m = gmpy2.powmod(c, d, n) # 计算 c^d mod n print(f"解密后的整数m = {m}")

运行这段代码，我们会得到一个很大的整数m。这个m就是加密前的原始数据，但它通常不是可读的字符串，而是字节数据。

4.4 第四步：将整数明文转换为Flag

RSA加密的对象是整数。在实际应用中，待加密的文本（比如Flag）会先通过某种编码方式（如PKCS#1 v1.5填充、OAEP，或简单的字节转换）转换为一个大整数。在CTF的简单题目中，最常见的就是将字符串的每个字符转换为对应的ASCII码（或Unicode码点），然后拼接成一个大的整数。或者更简单地，直接将字符串的字节表示（bytes）转换为整数。

因此，解密得到的整数m，我们需要将其转换回字节，再解码为字符串。在Python中，通常这样做：

# 将整数m转换为字节序列 # 首先将整数转换为十六进制字符串，去掉开头的'0x' hex_str = hex(m)[2:] # 注意：如果十六进制字符串长度是奇数，需要在前面补一个'0'，确保每两个字符对应一个字节 if len(hex_str) % 2 != 0: hex_str = '0' + hex_str # 将十六进制字符串转换为字节 bytes_data = bytes.fromhex(hex_str) print(f"字节数据: {bytes_data}") # 尝试解码为UTF-8字符串（最常用） try: flag = bytes_data.decode('utf-8') print(f"Flag (UTF-8): {flag}") except UnicodeDecodeError: # 如果不是UTF-8，可能是其他编码，或者直接包含不可打印字符 print("无法用UTF-8解码，尝试其他方式或直接输出字节。") # 有时Flag可能被进一步编码（如Base64），需要继续处理 # 或者直接输出字节，看是否有可见字符 print(f"原始字节: {bytes_data}")

对于我们的模拟数据，假设解密后m的十六进制是666c61677b746869735f69735f615f666c61677d，那么bytes.fromhex()后会得到b'flag{this_is_a_flag}'，解码后就是最终的Flag。

一个非常重要的细节：字节序。int.to_bytes()和int.from_bytes()方法需要指定字节序（‘big’ 或 ‘little’）。在RSA和大多数网络协议中，通常使用大端序（big-endian），即最高有效字节在前。所以，更稳健的转换方法是：

# 计算需要多少字节来存储整数m byte_length = (m.bit_length() + 7) // 8 bytes_data = m.to_bytes(byte_length, 'big')

使用to_bytes方法可以避免手动处理十六进制字符串时可能遇到的长度对齐问题。

5. 常见问题、变种与深度排查技巧

在实际解题过程中，尤其是面对“easyrsa”这类题目时，即使按照上述流程，也可能遇到各种意想不到的问题。下面我总结了一些常见坑点和对应的排查技巧。

5.1 问题一：分解n失败怎么办？

症状：将n提交到factordb显示“FF”（完全分解失败），yafu运行很久也没结果。排查思路：

1. 检查n的格式：确认你提交的n是完整的十进制或十六进制数，没有多余的空格、换行或前缀（如‘0x’）。factordb对输入格式比较敏感。
2. 重新获取n：CTF题目有时是动态生成的，确保你从服务器获取的n是正确的，没有复制错位。
3. 考虑其他攻击方式：如果n确实很大（比如超过300位十进制），且e=65537，那么直接分解可能不是预期解。此时需要重新审视题目：
   • 查看题目名称和描述：“easyrsa”可能是一种误导，或者有额外的提示。有时题目会给出多个n、e、c对。
   • 检查是否有共模：如果你有两组或以上的密文，看看它们的n是否相同。如果相同，e不同，则适用共模攻击。
   • 检查e是否很小：如果e=3, 5, 17等，尝试低加密指数攻击（直接开方）。
   • 检查e是否很大：如果e非常大（接近n），可能暗示d很小，考虑维纳攻击。
   • 检查n是否有特殊结构：n是否是一个素数（那么φ(n)=n-1）？这极其不安全，但CTF中可能出现。用gmpy2.is_prime(n)检查一下。
   • n是否由多个素数组成：RSA也可以使用多于两个素数（多素数RSA），此时 φ(n) = (p1-1)(p2-1)...*(pk-1)。如果题目提示“multi-prime”或n能被分解成三个以上的因子，就需要按此处理。

5.2 问题二：解密后得到的明文是乱码或非预期结果

症状：成功计算出m并转换为字节后，得到的是一堆乱码，或者开头不是预期的flag{格式。排查思路：

1. 确认解密过程正确：这是最可能出错的环节。
   • 重新验算：确保p和q的乘积等于n。
   • 验算d：计算(e * d) % phi_n，结果必须等于1。如果不等于1，说明d计算错误。
   • 验算解密：选择一个小的测试数字（比如42），用公钥加密得到c_test，再用你计算的私钥d解密，看是否能恢复42。这是一个很好的完整性检查。

   # 完整性检查 test_m = gmpy2.mpz(42) c_test = gmpy2.powmod(test_m, e, n) m_test = gmpy2.powmod(c_test, d, n) assert test_m == m_test, "加解密验证失败！"

2. 检查编码方式：RSA加密的“明文”是一个整数，这个整数是如何从原始字符串转换来的？除了简单的字节转整数，还有几种常见情况：
   • PKCS#1 v1.5填充：解密后的字节串开头应该是0x00 0x02，后面跟着随机填充符，然后是0x00，最后才是真正的数据。你需要剥离这些填充字节。在CTF中，简单题可能不用填充，但稍微复杂一点的题可能会用到。
   • 明文是数字而非字符串：有时Flag本身就是一个数字，或者经过某种编码（如将字符串的十六进制表示当作数字）。尝试直接将整数m作为十进制或十六进制输出，看看是否有意义。
   • 多层加密/编码：解密得到的字节可能还不是最终的Flag，它可能是Base64、Hex、ROT13等编码后的结果。你需要观察字节的内容，如果看到很多0x41-0x5a（A-Z）、0x61-0x7a（a-z）、0x2f、0x2b、0x3d（Base64字符），可能就是Base64。继续解码。
   • 字节序问题：如前所述，尝试使用m.to_bytes(byte_length, 'little')小端序转换，看看结果是否变得可读。

5.3 问题三：题目提供了多个公钥或密文

症状：题目给了两个pub.key文件，或者在一个文件里给出了多组 (n, e, c)。解题思路：

1. 首先分别提取每一组的n和e。
2. 比较模数n：
   • 如果n相同，e不同：极大概率是共模攻击。使用扩展欧几里得算法，在已知gcd(e1, e2)=1的前提下，找到整数s1和s2使得e1*s1 + e2*s2 = 1，然后计算m = (c1^s1 * c2^s2) mod n即可恢复明文。Python实现如下：

   import gmpy2 # 假设有两组数据： (n, e1, c1), (n, e2, c2) # 检查e1, e2是否互质 assert gmpy2.gcd(e1, e2) == 1 # 使用扩展欧几里得算法求s1, s2 gcd, s1, s2 = gmpy2.gcdext(e1, e2) # 根据公式计算明文m m = (gmpy2.powmod(c1, s1, n) * gmpy2.powmod(c2, s2, n)) % n # 注意：s1或s2可能为负数，负数指数需要先计算模逆元 # 更稳健的写法： if s1 < 0: c1_inv = gmpy2.invert(c1, n) part1 = gmpy2.powmod(c1_inv, -s1, n) else: part1 = gmpy2.powmod(c1, s1, n) if s2 < 0: c2_inv = gmpy2.invert(c2, n) part2 = gmpy2.powmod(c2_inv, -s2, n) else: part2 = gmpy2.powmod(c2, s2, n) m = (part1 * part2) % n

   • 如果n不同，但有关联：检查两个n是否有公因数。计算gcd(n1, n2)，如果不等于1，那么恭喜，你直接找到了一个n的质因子！这是因为如果两个不同的RSA密钥使用了不独立的随机数生成器，可能会产生有公因数的模数。这在历史上是真实发生过的漏洞（如著名的“Mining Your P’s and Q‘s”论文）。找到公因数后，就能分别分解n1和n2。
   • 如果n不同，且无关联：那么可能是两个独立的RSA加密，需要分别破解。但题目给多个，往往意味着它们之间存在某种关系（如共模、共享素数），需要仔细分析。

5.4 问题四：如何系统化地尝试各种攻击？

对于新手，面对一道RSA题可能不知道从何入手。一个系统化的检查清单如下表所示：

对于“easyrsa”这道题，绝大多数情况下，它考察的就是对n大小的敏感性和使用factordb等工具的能力。所以，第一步永远是尝试分解n。

6. 总结与进阶思考

通过这道“easyrsa”的模拟解题，我们完整遍历了CTF中基础RSA题目的核心流程：信息提取、尝试分解、计算私钥、解密、编码转换。这个过程看似简单，却涵盖了RSA最根本的原理和最常见的攻击面。

我个人在带新人和自己解题的过程中，最大的体会是：密码学题目，三分靠算法，七分靠观察和联想。拿到题目，不要急于写代码，先花时间把所有的条件列出来，思考它们之间可能存在的联系。题目名字“easyrsa”本身就是一种提示——它很可能就是最简单直接的攻击方式。

这道题虽然基础，但它是一个重要的起点。它让你熟悉了RSA的“标准破解流程”。在此基础上，你可以去挑战更复杂的变种，比如：

• PEM文件里藏有信息：公钥文件本身可能被修改，在ASN.1结构里隐藏了额外的参数或提示。
• 错误的参数选择：比如e和φ(n)不互质，导致无法解密，需要寻找其他恢复明文的方法。
• 侧信道攻击：题目可能给出加密过程的运行时间、错误信息等，这属于更高级的范畴。

最后，再分享一个实用技巧：建立自己的“密码学解题脚本库”。把今天用到的解析公钥、计算模逆、共模攻击、维纳攻击等代码片段都保存下来，并写好注释。下次遇到类似题目，你就能快速搭建解题框架，把主要精力集中在分析题目特有的“花样”上。CTF密码学的学习就是一个不断积累“模式识别”能力和工具使用经验的过程。从这道“easyrsa”开始，希望你能建立起信心，逐步攻克更强大的密码学堡垒。