CTF小白也能懂：手把手教你用Python脚本破解RSA（附攻防世界Crypto cr4-poor-rsa实战）

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 # macOS

3. 提取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: 65537

4. 分解模数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: 521250646663056391768764366517618655312275374668692430321064634566533568373969990465313092928455546989832961905578375473

6. 解密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. 常见问题与调试技巧

在实际操作中可能会遇到各种问题，这里总结几个常见情况：

1. 导入错误：

   • No module named 'Crypto'：确认安装的是pycryptodome而非pycrypto
   • gmpy2 not found：可能需要先安装系统依赖

2. 解密失败：

   • 检查是否使用了正确的填充模式（OAEP或PKCS1_v1_5）
   • 确认p和q的正确性，可以验证n == p*q

3. 性能优化：

   • 对于大数运算，gmpy2比Python原生整数运算快得多
   • 分解大n时，可以尝试yafu等专业工具

# 验证参数正确性的检查代码 assert n == p * q assert (e * d) % phi == 1

8. 扩展学习与防御思路

理解了攻击方法后，也应该知道如何防御：

• 密钥长度：现代应用至少使用2048位RSA
• 质数选择：p和q应足够大且随机，避免使用相近的质数
• 加密填充：务必使用OAEP等安全填充方案

对于想进一步学习的同学，推荐尝试：

1. 攻防世界的其他RSA题目（如"babyRSA"、"hardRSA"）
2. 研究Coppersmith攻击等更高级的RSA破解技术
3. 了解基于RSA的签名算法和其潜在漏洞

在最近的一次CTF比赛中，我遇到一个n长达1024位的题目，最初以为不可破解，但发现出题人使用了相同的n加密多条消息，最终通过共模攻击成功解密。这种实战经验正是通过不断练习积累的。