CTF密码学实战：用Python从零破解RSA的完整指南
RSA加密算法作为现代密码学的基石，在CTF竞赛中出现的频率极高。但对于刚入门的新手来说，面对一堆数学符号和加密数据往往无从下手。本文将带你用Python一步步拆解RSA加密，从公钥提取到最终解密，完整复现攻防世界Crypto题目的解题过程。
1. 理解RSA加密的基本原理
RSA算法的安全性建立在大整数分解难题之上。简单来说，它利用两个大质数相乘容易，但反过来分解极其困难的特性。加密过程涉及三个关键参数：
- 模数n：两个大质数p和q的乘积（n = p * q）
- 公钥e：通常取65537，与φ(n)互质
- 私钥d：e关于φ(n)的模反元素，满足 e*d ≡ 1 mod φ(n)
其中φ(n)是欧拉函数，对于n=pq的情况，φ(n) = (p-1)(q-1)
提示：在CTF中，RSA题目常通过设置不安全的参数（如过小的p/q）来降低难度，这正是我们破解的突破口。
2. 准备Python密码学环境
在开始破解前，我们需要配置合适的Python环境。推荐使用以下工具链：
pip install pycryptodome gmpy2- pycryptodome：替代已停止维护的PyCrypto，提供完整的密码学工具集
- gmpy2：高性能大整数运算库，加速模逆运算等操作
如果遇到安装问题，可以尝试：
# 对于Linux/macOS用户可能需要先安装依赖 sudo apt-get install libgmp-dev libmpfr-dev libmpc-dev # Ubuntu/Debian brew install gmp mpfr libmpc # macOS3. 提取RSA公钥参数
拿到题目提供的key.pub文件后，第一步是提取其中的n和e。下面是完整的Python代码：
from Crypto.PublicKey import RSA # 读取公钥文件 with open("key.pub", "rb") as pub_file: pub_key = RSA.import_key(pub_file.read()) # 获取关键参数 n = pub_key.n e = pub_key.e print(f"模数n: {n}") print(f"公钥指数e: {e}")运行后会输出类似这样的结果：
模数n: 833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019 公钥指数e: 655374. 分解模数n获取p和q
这是破解RSA最关键的步骤。对于CTF题目，通常n不会太大，可以使用在线工具或本地算法分解：
方法一：使用Factordb在线分解
访问factordb.com，输入n值查询是否已被分解。如果幸运的话，可以直接得到p和q：
p = 863653476616376575308866344984576466644942572246900013156919 q = 965445304326998194798282228842484732438457170595999523426901方法二：本地使用Pollard's Rho算法
对于小型n，可以用Python实现分解：
from math import gcd from random import randint def pollards_rho(n): if n % 2 == 0: return 2 if n % 3 == 0: return 3 while True: c = randint(2, n-1) f = lambda x: (pow(x,2,n)+c) % n x, y, d = 2, 2, 1 while d == 1: x = f(x) y = f(f(y)) d = gcd(abs(x-y), n) if d != n: return d # 示例使用 n = 833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019 p = pollards_rho(n) q = n // p print(f"p = {p}\nq = {q}")5. 计算私钥d
得到p和q后，计算私钥d的完整过程如下：
import gmpy2 p = 863653476616376575308866344984576466644942572246900013156919 q = 965445304326998194798282228842484732438457170595999523426901 e = 65537 # 计算欧拉函数φ(n) phi = (p-1)*(q-1) # 计算模反元素d d = gmpy2.invert(e, phi) print(f"私钥d: {d}")输出结果：
私钥d: 5212506466630563917687643665176186553122753746686924303210646345665335683739699904653130929284555469898329619055783754736. 解密flag密文
最后一步是使用私钥解密题目提供的密文。注意题目中的密文是base64编码的，需要先解码：
from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP import base64 # 准备私钥 priv_key = RSA.construct((n, e, d, p, q)) # 读取并解码密文 with open("flag.b64", "r") as f: cipher = base64.b64decode(f.read().strip()) # 使用PKCS#1 OAEP模式解密 cipher_rsa = PKCS1_OAEP.new(priv_key) flag = cipher_rsa.decrypt(cipher) print(f"解密结果: {flag.decode()}")如果一切顺利，你将看到flag显示：
ALEXCTF{SMALL_PRIMES_ARE_BAD}7. 常见问题与调试技巧
在实际操作中可能会遇到各种问题，这里总结几个常见情况：
导入错误：
No module named 'Crypto'：确认安装的是pycryptodome而非pycryptogmpy2 not found：可能需要先安装系统依赖
解密失败：
- 检查是否使用了正确的填充模式（OAEP或PKCS1_v1_5）
- 确认p和q的正确性，可以验证n == p*q
性能优化：
- 对于大数运算，gmpy2比Python原生整数运算快得多
- 分解大n时，可以尝试yafu等专业工具
# 验证参数正确性的检查代码 assert n == p * q assert (e * d) % phi == 18. 扩展学习与防御思路
理解了攻击方法后，也应该知道如何防御：
- 密钥长度：现代应用至少使用2048位RSA
- 质数选择：p和q应足够大且随机，避免使用相近的质数
- 加密填充：务必使用OAEP等安全填充方案
对于想进一步学习的同学，推荐尝试：
- 攻防世界的其他RSA题目（如"babyRSA"、"hardRSA"）
- 研究Coppersmith攻击等更高级的RSA破解技术
- 了解基于RSA的签名算法和其潜在漏洞
在最近的一次CTF比赛中，我遇到一个n长达1024位的题目，最初以为不可破解，但发现出题人使用了相同的n加密多条消息，最终通过共模攻击成功解密。这种实战经验正是通过不断练习积累的。
