Python实战RSA模数分解攻击：从CTF入门题理解密码学实现漏洞

1. 项目概述：从零到一，用Python脚本破解一道RSA题目

如果你刚接触CTF（Capture The Flag，夺旗赛），看到“Crypto”（密码学）和“RSA”这两个词，是不是觉得头大？感觉这玩意儿全是数学，深不可测。别怕，今天我就带你用Python，像拼乐高一样，一步步拆解一道经典的RSA题目。我们的目标不是让你立刻成为密码学专家，而是让你亲手体验一次“破解”的快感，理解RSA在CTF中最常见的攻击面。这次我们实战的靶子是攻防世界（BUUCTF）上的一道入门级题目“cr4-poor-rsa”。题目名字里的“poor”（简陋）已经给了我们提示：它的RSA实现有缺陷。我们的任务就是找到这个缺陷，并用Python脚本把它变成我们想要的Flag。

为什么选择Python？因为它语法简洁，库丰富，是CTF选手和网络安全从业者的“瑞士军刀”。你不需要深厚的数学功底，只要会基本的Python语法，跟着我的思路和代码，就能看懂并复现整个破解过程。这篇文章会假设你是个编程新手，但充满好奇心和动手欲望。我会解释每一个步骤“为什么要这么做”，而不仅仅是“怎么做”。当你成功跑通脚本，拿到Flag的那一刻，你会对RSA有一个截然不同的、非常具体的认识。

2. RSA基础与CTF常见攻击面解析

在动手写脚本之前，我们必须先搞懂我们在对付什么。RSA是一种非对称加密算法，它基于一个简单的数论事实：将两个大质数相乘很容易，但把它们的乘积再分解回原来的两个质数却极其困难。

2.1 RSA加密解密的核心流程

想象一下，RSA就像一把特殊的锁和钥匙。

1. 生成钥匙（密钥对）：

   • 随机选择两个非常大的质数p和q。
   • 计算它们的乘积n = p * q。这个n就是模数，长度（比特数）决定了密钥的强度。
   • 计算欧拉函数φ(n) = (p-1)*(q-1)。
   • 选择一个整数e作为公钥指数，通常取65537。条件是1 < e < φ(n)，且e与φ(n)互质（最大公约数为1）。
   • 计算d作为私钥指数，使得(e * d) % φ(n) = 1。即d是e模φ(n)的乘法逆元。
   • 至此，公钥就是(n, e)，可以公开。私钥是(n, d)或(p, q, d)，必须严格保密。

2. 加密过程： 假设明文是一个数字m（文本信息需要先转换成数字）。用公钥(n, e)加密：c ≡ m^e (mod n)。得到的c就是密文。

3. 解密过程： 用私钥(n, d)解密：m ≡ c^d (mod n)。就能恢复出明文m。

整个安全性的基石在于：攻击者只知道公开的(n, e)和密文c，想要求出私钥d，就必须知道φ(n)；而想知道φ(n)，就必须分解n得到p和q。对于足够大的n（比如2048位以上），分解在现有计算能力下是不可行的。

2.2 CTF中RSA题目的常见“命门”

既然理论上RSA很安全，那CTF题目考我们什么？考的就是实现上的失误或特殊场景的漏洞。对于“cr4-poor-rsa”这类入门题，常见的攻击面有：

1. 模数n过小：这是最经典的“poor”。如果n只有256位或512位，以现代计算机的算力，完全可以在短时间内暴力分解。这就是我们这道题的核心。
2. 共模攻击：如果相同的明文m，用相同的n但不同的e加密，得到两个密文c1和c2，且e1和e2互质，则可以恢复明文。此题不涉及。
3. 低加密指数攻击：如果公钥指数e非常小（比如3），而明文m也很小，可能导致m^e < n。此时加密操作c = m^e mod n实际上没有取模，直接c = m^e，对c开e次方就能得到m。
4. 低解密指数攻击：如果私钥指数d过小，可以通过Wiener攻击等方式破解。此题不涉及。
5. 因数碰撞：如果多个RSA密钥使用了相同的质数p或q，通过计算最大公约数（GCD）可以快速分解它们的n。
6. 已知高位攻击：如果私钥d的部分比特位泄露，可能危及整个密钥安全。

对于我们手头的“cr4-poor-rsa”，题目名字和附件信息已经强烈暗示了第一种情况：模数n太小，可以直接分解。我们的攻击思路因此非常清晰：下载题目附件 -> 提取公钥参数n和e-> 尝试分解n得到p和q-> 计算私钥d-> 用私钥解密给出的密文 -> 得到Flag。

注意：在真实的网络安全领域，攻击一个正确实现且使用足够长密钥（如2048位以上）的RSA系统是极其困难的。CTF题目旨在教育，让我们理解这些算法的边界和错误使用的后果，切勿用于非法用途。

3. 实战环境准备与题目附件分析

工欲善其事，必先利其器。我们不需要复杂的IDE，一个能运行Python的环境和几个关键的库就够了。

3.1 Python环境与必要库安装

首先，确保你的电脑安装了Python 3.6或以上版本。打开命令行（Windows上是CMD或PowerShell，Mac/Linux上是Terminal），输入python --version或python3 --version检查。

我们需要两个核心库：

1. gmpy2：这是一个高性能的数学库，尤其擅长大整数运算和素数相关操作，分解小模数n的速度远快于Python原生整数运算。
2. pycryptodome或Crypto：这是一个功能强大的密码学工具库，我们主要用它来解析RSA公钥文件格式。

安装它们：

pip install gmpy2 pycryptodome

如果安装gmpy2遇到困难（特别是在Windows上），可以去 gmpy2的官方页面 查找对应你Python版本和系统的预编译轮子（.whl文件）进行安装。对于这道题，如果实在装不上gmpy2，用Python原生的大整数运算也可以，只是分解速度会慢一点。

3.2 下载并解构“cr4-poor-rsa”题目附件

从攻防世界（BUUCTF）下载“cr4-poor-rsa”的题目附件。通常附件是一个压缩包，解压后你会看到类似这样的文件：

• public.key- 一个PEM格式的RSA公钥文件。
• flag.enc- 一个二进制文件，里面是用上述公钥加密后的密文。

我们的第一步是读取并解析公钥文件，拿到关键的n和e。

实操步骤1：使用Python解析公钥

from Crypto.PublicKey import RSA # 读取公钥文件 with open('public.key', 'r') as f: key_data = f.read() # 导入公钥 pub_key = RSA.import_key(key_data) # 提取模数n和公钥指数e n = pub_key.n e = pub_key.e print(f"模数 n (hex): {hex(n)}") print(f"模数 n (十进制, 长度): {n} ({n.bit_length()} bits)") print(f"公钥指数 e: {e}")

运行这段代码，你会得到类似下面的输出（数值是示例）：

模数 n (hex): 0xaa...（很长一串十六进制） 模数 n (十进制, 长度): 123456789... (256 bits) 公钥指数 e: 65537

关键点解析：

• n.bit_length()会告诉我们模数的比特长度。如果输出是256或512，那恭喜你，这几乎肯定是可以分解的。如果是1024，可能需要更长时间或更强的算力。2048及以上，对于这道入门题来说基本不可能。
• e是65537，这是RSA中最常用、最安全的标准公钥指数之一，说明出题人没有在e上设置陷阱。

拿到n和e，我们就拿到了打开第一道门的钥匙。接下来，就是最核心的一步：分解n。

4. 核心攻击：分解模数n并计算私钥

这是整个破解过程的“心脏”。我们确认n很小（比如256位），那么就可以利用在线数据库或本地工具进行分解。

4.1 利用在线数据库快速分解

对于非常小的n（通常小于768位），最快的方法不是自己算，而是去“查表”。有一个著名的网站叫FactorDB，它收集了海量已知的因数分解结果。你可以将n的十进制或十六进制值提交上去查询。

操作方法：

1. 将上一步打印出的n的十进制值（那一长串数字）复制。
2. 访问 FactorDB 网站。
3. 在搜索框粘贴n的值，点击查询。
4. 如果幸运，网站会直接返回p和q的值。

为什么能查到？因为这些小的n可能被其他研究者或题目使用过，早已被分解并收录进数据库。这是一种“知识型”攻击，在CTF中非常常见且有效。

4.2 使用Python本地分解

如果在线数据库没有结果，或者你想体验完整的破解流程，就需要本地分解。我们将使用gmpy2库。

实操步骤2：分解模数n

import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long # 假设我们从第一步得到了 n # n = pub_key.n (这里用示例值代替，实际请用你读取到的n) # 示例一个很小的n（仅用于演示，真实题目n会大很多但可分解） # n = 3233 # 实际题目n很大，这里仅为演示流程 print(f"开始尝试分解 {n.bit_length()} 位的模数 n...") # 方法1：使用gmpy2的next_prime和整除试探（适用于小n） # 这不是最优方法，但对于可分解的n通常有效 def factorize_n(n): # 这是一个简单的试除法变种，从2开始找因子 # 对于CTF题目中的小n，gmpy2自带的分解函数可能更快 # 但请注意：对于超过一定位数的n，此方法会极慢或无效 root = gmpy2.isqrt(n) + 1 # 我们尝试从2开始，以2为步长递增（只检查奇数） # 实际上，对于RSA的p和q，它们都是大质数，且相差不会特别大。 # 更高效的方法是使用专门的分解算法，如Pollard's rho。 # 这里为了演示原理，使用一个简单循环。 # 警告：对于真实题目中的n（如256位），这个循环可能永远跑不完。 # 因此，下面我们直接调用gmpy2的分解函数（如果可用）或使用更智能的方法。 # 实际上，对于CTF中的“poor RSA”，n通常小到可以用以下命令快速分解： # 使用 sympy 库： from sympy import factorint; factors = factorint(n) # 或者使用 factordb 在线查询。 # 由于简单循环不现实，我们这里模拟一个已分解成功的情景。 # 假设我们已经通过factordb.com查到了p和q： # 从 factordb 获取的 p 和 q (你需要替换成实际值) p = 123456791 # 示例质数p q = 987654323 # 示例质数q # 验证 p * q 是否等于 n if p * q == n: print(f"分解成功！") print(f"p = {p}") print(f"q = {q}") else: print("错误：提供的 p 和 q 的乘积不等于 n。请检查分解结果。") exit() # 计算欧拉函数 φ(n) = (p-1)*(q-1) phi = (p - 1) * (q - 1) # 计算私钥指数 d，即 e 模 φ(n) 的乘法逆元 # 条件： e * d ≡ 1 (mod φ(n)) d = gmpy2.invert(e, phi) print(f"私钥指数 d 计算完成: {d}")

关键点解析与避坑：

• 分解是瓶颈：对于256位的n，本地分解可能只需几秒到几分钟；对于512位，可能需要更长时间或更多内存。永远不要尝试在本地分解一个1024位或以上的RSA模数，那可能耗费你一生的时间。
• gmpy2.invert(e, phi)：这个函数计算的是模逆元，即满足(e * d) % phi == 1的d。这是恢复私钥的关键一步。
• 验证分解结果：务必检查p * q == n。这是防止后续计算出错的保险丝。

实操心得：在CTF中，遇到RSA题目，第一步永远是print(n.bit_length())。如果n小于等于512位，立刻想到分解。优先去FactorDB等网站查询，这往往是最快的方式。本地分解可以作为备选，但要知道其局限性。

5. 解密密文与Flag提取

现在，我们手握私钥(n, d)，密文文件flag.enc就像上了锁的宝箱，而d就是唯一的钥匙。

5.1 读取并解密密文

密文文件flag.enc通常是二进制格式，里面存储的就是加密后的数字c。我们需要读取它，并将其转换为整数进行处理。

实操步骤3：解密获得明文

# 读取密文文件 with open('flag.enc', 'rb') as f: # 注意是 'rb' 二进制读取 ciphertext = f.read() # 将二进制密文转换为整数 c c = bytes_to_long(ciphertext) print(f"密文 c (整数): {c}") # 使用私钥指数 d 和模数 n 进行解密 # RSA解密公式： m ≡ c^d (mod n) m = pow(c, d, n) # Python的pow函数支持模幂运算，非常高效 print(f"解密后的明文 (整数): {m}") # 将整数明文转换回字节串（即我们可读的文本） plaintext = long_to_bytes(m) print(f"解密后的明文 (字节): {plaintext}")

代码细节解读：

• open('flag.enc', 'rb')：用二进制模式'rb'打开文件，确保读取的字节原封不动。
• bytes_to_long()：这是Crypto.Util.number中的函数，将字节序列转换成一个大整数。因为RSA加密操作的对象是整数。
• pow(c, d, n)：这是Python的内置函数，计算c的d次方再对n取模。它使用了模幂运算优化算法（如平方乘算法），即使c,d,n都非常大，计算速度也很快。千万不要用(c ** d) % n，这会先计算一个天文数字般的中间结果，导致内存溢出。
• long_to_bytes()：将解密得到的整数m转换回字节串。这个字节串很可能就是Flag，或者包含Flag的文本。

5.2 处理解密结果与Flag格式化

运行解密脚本后，plaintext变量里存储的就是解密后的结果。但它不一定就是完美的Flag。

常见情况与处理技巧：

1. 直接输出可读字符串：最理想的情况，plaintext直接就是像flag{this_is_a_sample_flag}这样的字符串。直接print(plaintext.decode())即可。
2. 包含不可见字符或乱码：有时解密出的字节串开头或结尾可能有填充字符（如PKCS#1 v1.5填充）。你可以尝试打印其十六进制形式查看：print(plaintext.hex())。Flag可能藏在中间某段。常见的Flag格式有flag{...}、FLAG{...}、ctf{...}等，你可以用if b'flag{' in plaintext:来搜索。
3. 结果是数字需要进一步转换：极少数情况下，明文m本身可能代表另一个编码（如ASCII码）。如果plaintext看起来像一堆数字，尝试将其作为整数，再转换成字符。

针对“cr4-poor-rsa”的最终脚本整合： 将前面所有步骤整合成一个完整的脚本solve.py：

#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ 攻防世界 cr4-poor-rsa 解题脚本 使用方法：将 public.key 和 flag.enc 放在同目录，运行本脚本。 """ from Crypto.PublicKey import RSA from Crypto.Util.number import long_to_bytes, bytes_to_long import gmpy2 def main(): # 1. 解析公钥，获取 n 和 e print("[*] 正在解析公钥文件...") with open('public.key', 'r') as f: pub_key = RSA.import_key(f.read()) n = pub_key.n e = pub_key.e print(f" [+] n = {n}") print(f" [+] n (比特长度) = {n.bit_length()}") print(f" [+] e = {e}") # 2. 分解 n (此处需要你根据实际情况填入分解得到的p和q) # 通常通过 factordb.com 查询得到 print("[*] 请手动分解n，或从factordb.com获取p和q。") # 示例（你必须替换成题目实际的p和q）: # p = 123456791 # q = 987654323 # 请取消下面三行的注释，并填入正确的p和q # p = 填入你的p # q = 填入你的q # if p * q != n: # print("[-] 错误：p * q != n") # return # 假设我们已经有了正确的 p 和 q # 计算 phi 和 d phi = (p - 1) * (q - 1) d = gmpy2.invert(e, phi) print(f"[+] 私钥指数 d 计算完成") # 3. 读取并解密密文 print("[*] 正在解密密文...") with open('flag.enc', 'rb') as f: c = bytes_to_long(f.read()) m = pow(c, d, n) flag = long_to_bytes(m) # 4. 输出结果 print("[+] 解密完成！") print("=" * 30) try: print(f"明文 (文本): {flag.decode()}") except UnicodeDecodeError: print(f"明文 (字节，可能含不可见字符): {flag}") print(f"明文 (十六进制): {flag.hex()}") print("=" * 30) if __name__ == "__main__": main()

运行这个脚本前，你需要完成最关键的一步：填入从FactorDB或本地分解得到的正确p和q。一旦填入，脚本就会自动完成后续所有计算并输出Flag。

6. 常见问题、调试技巧与扩展思考

即使跟着步骤做，你也可能会遇到一些问题。这里我总结几个常见的坑和解决方法。

6.1 问题排查清单

1. ModuleNotFoundError: No module named 'Crypto'

   • 原因：没有正确安装pycryptodome库。
   • 解决：运行pip install pycryptodome。注意导入时是from Crypto.PublicKey import RSA，但安装的包名是pycryptodome。

2. gmpy2安装失败

   • 原因：gmpy2依赖GMP或MPIR数学库，在某些系统上编译安装较复杂。
   • 解决：
     • Windows：在 这里 下载对应你Python版本和系统架构的.whl文件，然后用pip install 下载的文件名.whl安装。
     • macOS：使用Homebrew先安装GMP：brew install gmp，然后再pip install gmpy2。
     • 放弃gmpy2：如果只是分解很小的n，可以尝试用Python原生整数运算配合sympy库（pip install sympy），使用sympy.factorint(n)进行分解。对于计算模逆元，可以用pow(e, -1, phi)（Python 3.8+ 支持）。

3. 分解n失败或时间过长

   • 原因：n可能比想象中大，或者本地算法效率太低。
   • 解决：
     • 首先确认n.bit_length()。如果是768位以上，可能不是简单的分解题，需要考虑其他攻击方式（如共模、低指数等）。
     • 务必优先使用FactorDB在线查询。
     • 可以尝试其他在线分解工具或本地工具如yafu（速度更快）。

4. 解密出的明文是乱码

   • 原因：
     • p和q填错了，导致计算出错的d。
     • 密文文件flag.enc读取方式不对（比如用了文本模式'r'而不是二进制模式'rb'）。
     • 题目可能对明文进行了额外编码或填充。
   • 解决：
     • 双重检查p * q == n是否严格成立。
     • 检查文件读取代码。
     • 打印plaintext.hex()仔细查看输出。Flag可能以666c61677b（“flag{”的十六进制）开头。尝试搜索b'flag'或b'CTF'等关键字。

5. 脚本运行没报错，但没输出Flag

   • 原因：可能解密出的整数m需要进一步处理。
   • 解决：在解密后，除了转字节，还可以尝试print(m)直接输出整数，看是不是一个很长的数字。这个数字本身可能就是Flag（有些题目Flag是数字格式）。或者尝试将这个整数转换成十六进制hex(m)，看看是否有可读的ASCII字符。

6.2 扩展思考：从这道题能学到什么？

成功破解“cr4-poor-rsa”只是一个开始。通过这个实战，你应该建立起对RSA最基本的攻击直觉：

• 密钥长度是关键：在CTF中，看到小n就想分解。在现实世界中，RSA密钥长度推荐至少2048位，3072或4096位用于更高安全需求。
• 工具链是生产力：熟悉Python、Crypto、gmpy2/sympy、FactorDB这些工具，能极大提升解题效率。
• 理解比套用更重要：你知道为什么分解了n就能算出d吗？因为d依赖于φ(n)，而φ(n) = (p-1)(q-1)。这是RSA安全的根本，也是它最脆弱的环节。
• 下一步学什么：掌握了基础分解，你可以继续探索其他RSA攻击类型，比如：
  • 共模攻击：写脚本实现扩展欧几里得算法恢复明文。
  • 低加密指数攻击：当e=3且明文很小时，直接对密文开三次方。
  • Wiener攻击：当私钥d较小时的一种攻击。
  • 广播攻击：相同的明文，用相同的e但不同的n加密。

最后，别忘了CTF的精神是学习和挑战。这道“简陋的RSA”题目就像一把钥匙，为你打开了密码学挑战的大门。当你下次再看到RSA时，不会只是一头雾水，而是会下意识地去检查n的位数，思考可能的攻击路径。这种主动分析的思维，才是最重要的收获。