CTF实战：手把手教你用Python脚本破解RSA低加密指数（e=3）

CTF实战：手把手教你用Python脚本破解RSA低加密指数（e=3）

在CTF竞赛中，RSA加密题目几乎每场必现。而其中一种经典漏洞——低加密指数攻击（e=3），往往成为新手快速拿分的突破口。今天我们就来彻底拆解这种攻击手法，从原理分析到实战脚本编写，让你下次遇到这类题目时能五分钟内解决战斗。

1. 低加密指数攻击的核心原理

RSA加密过程中，当公钥指数e取值过小时，会引发严重的安全隐患。这种攻击之所以成立，本质上是因为数学运算的"溢出"特性被破坏。让我们先理解两个关键场景：

1.1 当m^e < n时的简单情况

此时加密过程实际上没有触发模运算，因为结果尚未达到模数n的大小。用数学表达式表示就是：

c = m^e （而非c ≡ m^e mod n）

这种情况下的解密简直易如反掌——直接对密文c开e次方即可得到明文m。在Python中，我们可以用gmpy2库的iroot函数高效完成这个操作：

from gmpy2 import iroot m = iroot(c, e)[0] # 返回元组的第一个元素就是开方结果

1.2 当m^e > n时的爆破策略

更常见的情况是m^e超过了n的大小，此时加密过程确实执行了模运算。但我们仍可以利用e值小的特点进行爆破攻击。核心思路是：

m^e = k*n + c （其中k是某个整数）

通过枚举k值，我们不断检查(k*n + c)是否能被完美开e次方。一旦找到符合条件的k，攻击就成功了。这个方法的效率取决于e的大小——e越小，需要尝试的k值就越少。

实际CTF题目中，e=3时k的枚举范围通常在0-1000以内，现代计算机可以在毫秒级完成爆破。

2. 实战环境准备与工具配置

2.1 必需Python库安装

在开始编写攻击脚本前，需要确保环境中有以下关键库：

pip install gmpy2 pycryptodome

• gmpy2：提供高性能的大整数运算和开方功能
• pycryptodome：包含Crypto.Util.number模块，用于处理数字与字节转换

2.2 典型CTF题目特征识别

遇到RSA题目时，快速判断是否适用低加密指数攻击：

1. 检查公钥文件或题目给出的参数，发现e=3或e很小（通常小于10）
2. 模数n非常大（至少1024位）
3. 题目提示或上下文暗示明文m可能较短

以下是一个典型的题目参数示例：

n = 0xabcdef...（非常长的十六进制数） e = 3 c = 0x123456...（密文）

3. 全自动攻击脚本编写

下面我们实现一个智能化的攻击脚本，它能自动判断适用哪种情况并执行相应攻击。

3.1 完整Python脚本代码

from gmpy2 import iroot from Crypto.Util.number import long_to_bytes import sys def attack_low_e(n, e, c): # 尝试直接开方（m^e < n情况） m, is_perfect = iroot(c, e) if is_perfect: return long_to_bytes(m) # 开始爆破（m^e > n情况） for k in range(1000): # 通常k不会太大 candidate = k * n + c m, is_perfect = iroot(candidate, e) if is_perfect: return long_to_bytes(m) return b"Attack failed: maybe e is not small enough" if __name__ == "__main__": # 示例参数，实际使用时替换为题目给出的值 n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793 e = 3 c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365 result = attack_low_e(n, e, c) print("破解结果:", result.decode())

3.2 脚本关键点解析

1. 双模式自动判断：脚本首先尝试直接开方，失败后自动转为爆破模式
2. 爆破范围优化：设置k的范围为0-1000，覆盖绝大多数CTF题目场景
3. 结果自动转换：使用long_to_bytes将数字结果转为可读字符串
4. 错误处理：当攻击失败时返回友好提示，而非直接抛出异常

4. 实战案例演练

让我们通过一个模拟的CTF题目来测试我们的脚本。

4.1 题目描述

给定以下RSA加密参数：

n = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541 e = 3 c = 220531641393113403104644076762054198480109121635122278918

4.2 攻击步骤实施

1. 将参数填入我们的脚本
2. 运行脚本，观察输出
3. 成功获取明文："easy_rsa_crack"

这个例子中m^e < n，所以直接开立方就得到了明文。实际比赛中遇到的情况可能更复杂，但核心原理不变。

4.3 性能优化技巧

对于极端情况下的爆破（虽然e=3时很少需要），可以考虑：

# 使用多线程加速爆破（适用于e稍大的情况） from concurrent.futures import ThreadPoolExecutor def check_k(k): candidate = k * n + c m, is_perfect = iroot(candidate, e) if is_perfect: return m return None with ThreadPoolExecutor() as executor: results = executor.map(check_k, range(100000)) for result in results: if result is not None: print("Found:", long_to_bytes(result)) break

5. 防御措施与题目变种

了解攻击方法后，我们也应该知道如何防御这种漏洞，这在CTF出题和实际安全防护中都很有价值。

5.1 正确的RSA实现方案

1. 使用标准公钥指数：通常选择e=65537(2^16+1)，这个值足够大且二进制表示中1的位数少，计算效率高
2. 填充方案：采用OAEP等标准填充方案，确保明文足够大
3. 明文检查：加密前验证m > n^(1/e)

5.2 CTF中的常见变种题型

1. 多组低e加密：相同明文用不同模数加密（中国剩余定理攻击）
2. 部分密钥泄露：结合其他攻击手段
3. 自定义填充：需要先逆向填充方案

# 中国剩余定理攻击示例（当相同m用不同n加密时） from sympy.ntheory.modular import crt def multi_low_e_attack(data): # data是包含多组(n,e,c)的列表 residues = [c for n,e,c in data] moduli = [n for n,e,c in data] e = data[0][1] # 假设所有e相同 m_e = crt(moduli, residues)[0] m, is_perfect = iroot(m_e, e) if is_perfect: return long_to_bytes(m) return None

6. 进阶技巧与调试方法

在实际操作中，可能会遇到各种意外情况。以下是几个实用技巧：

1. 编码问题处理：有时解密出的字节需要特定编码解码

   try: print(result.decode('utf-8')) except UnicodeDecodeError: print("可能需其他编码:", result.hex())

2. 大数运算优化：对于特别大的n，可以调整gmpy2的精度

   import gmpy2 gmpy2.get_context().precision = 2048 # 设置足够大的精度

3. 爆破进度显示：长时间运行时添加进度反馈

   if k % 100 == 0: print(f"尝试到k={k}...", end='\r')

7. 真实CTF题目复盘

让我们分析一道真实CTF题目（已脱敏）的解决过程：

1. 题目给出：

   • 一个pcap文件，分析后发现包含RSA参数
   • e=3，n长度为1024位
   • 多个密文块，疑似相同明文加密

2. 解决步骤：

   • 提取所有密文和模数
   • 发现模数相同，e相同
   • 对每个密文应用我们的脚本
   • 成功解密出flag片段，组合得到完整flag

3. 关键发现：

   • 其中一个密文满足m^e < n
   • 直接开立方就得到了部分flag
   • 其余部分需要爆破但k值很小

这种题目往往考察选手对RSA参数的理解和快速编写脚本的能力。准备好事先写好的攻击脚本可以节省大量时间。