CTF实战：手把手教你用Python脚本破解RSA低加密指数（e=3）的两种场景-洪萨配资

CTF实战：Python脚本破解RSA低加密指数（e=3）的完整指南

在CTF竞赛中，RSA加密算法是最常见的密码学挑战之一。当遇到公钥指数e=3的情况时，往往意味着存在低加密指数攻击的可能。本文将带你深入理解这种攻击的原理，并提供可直接复用的Python解决方案。

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

RSA加密的基本公式是c ≡ m^e mod n，其中c是密文，m是明文，e是公钥指数，n是模数。当e取值过小时（特别是e=3），就可能出现以下两种攻击场景：

1.1 场景一：m^e < n

当明文m的e次方小于模数n时，取模运算实际上不会产生任何效果。此时密文c就等于m^e。这种情况下，我们只需要对密文c开e次方就能直接得到明文m。

数学表达：

c = m^e m = c^(1/e)

1.2 场景二：m^e > n

当m^e大于n时，情况会复杂一些。此时密文c = m^e mod n，我们需要找到满足m^e = kn + c的整数k。通过枚举k值并检查kn + c是否能开e次方，我们就能恢复出明文m。

关键公式：

m^e = kn + c m = (kn + c)^(1/e)

2. 实战环境准备

在开始编写攻击脚本前，我们需要准备以下工具和环境：

Python 3.x：推荐使用最新稳定版
gmpy2库：用于高效的大数运算和开方操作
Crypto.Util.number：提供长整数和字节转换的实用函数

安装依赖：

pip install gmpy2 pycryptodome

注意：在某些系统上可能需要先安装GMP库，例如在Ubuntu上可以运行sudo apt-get install libgmp-dev

3. 攻击脚本实现与解析

3.1 m^e < n场景的Python实现

from gmpy2 import iroot from Crypto.Util.number import long_to_bytes def attack_small_m(n, e, c): """ 处理m^e < n情况的攻击函数 参数: n: RSA模数 e: 公钥指数(通常为3) c: 密文 返回: 解密后的明文 """ # 将输入转换为整数 n = int(n) e = int(e) c = int(c) # 尝试对c开e次方 m, is_perfect_root = iroot(c, e) if is_perfect_root: return long_to_bytes(m) else: raise ValueError("无法直接开方，可能需要考虑m^e > n的情况")

使用示例：

n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793 e = 0x3 c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365 print(attack_small_m(n, e, c))

3.2 m^e > n场景的Python实现

from gmpy2 import iroot from Crypto.Util.number import long_to_bytes def attack_large_m(n, e, c, max_k=1000000): """ 处理m^e > n情况的攻击函数 参数: n: RSA模数 e: 公钥指数(通常为3) c: 密文 max_k: 最大尝试的k值 返回: 解密后的明文 """ n = int(n) e = int(e) c = int(c) for k in range(max_k): # 计算kn + c candidate = k * n + c # 尝试开e次方 m, is_perfect_root = iroot(candidate, e) if is_perfect_root: return long_to_bytes(m) raise ValueError(f"在k<{max_k}范围内未找到解")

使用示例：

n = 0xabcdef1234567890 # 替换为实际的n值 e = 3 c = 0x1234567890abcdef # 替换为实际的c值 print(attack_large_m(n, e, c))

4. 实战技巧与常见问题

4.1 如何判断适用哪种攻击

在实际CTF比赛中，快速判断应该使用哪种攻击方式至关重要。以下是判断流程：

检查e值：确认e=3
估算m^e与n的关系：
- 如果明文m很短（比如只有几个字符），很可能m^e < n
- 如果m较长，或者n相对较小，可能需要考虑m^e > n的情况
尝试顺序：建议先尝试m^e < n的情况（更简单快速），如果不成功再尝试爆破

4.2 性能优化技巧

当处理m^e > n的情况时，爆破k值可能会很耗时。以下是一些优化建议：

多线程处理：将k值范围分割，使用多线程并行计算
提前终止：一旦找到解立即终止计算
合理设置max_k：根据n和c的大小估算合理的k值范围

优化后的多线程版本示例：

import concurrent.futures def threaded_attack(n, e, c, start_k, end_k): for k in range(start_k, end_k): candidate = k * n + c m, is_perfect_root = iroot(candidate, e) if is_perfect_root: return m return None def optimized_attack(n, e, c, max_k=1000000, threads=4): chunk_size = max_k // threads with concurrent.futures.ThreadPoolExecutor() as executor: futures = [] for i in range(threads): start = i * chunk_size end = (i + 1) * chunk_size if i != threads - 1 else max_k futures.append(executor.submit(threaded_attack, n, e, c, start, end)) for future in concurrent.futures.as_completed(futures): result = future.result() if result is not None: return long_to_bytes(result) raise ValueError(f"在k<{max_k}范围内未找到解")

4.3 常见错误与解决方案

错误类型	可能原因	解决方案
开方失败	m^e < n假设不成立	尝试m^e > n的攻击方式
爆破时间过长	k值范围设置过大	合理估算k的最大可能值
编码问题	明文不是有效文本	尝试不同的编码方式或考虑flag格式
数值溢出	数字过大	确保使用gmpy2处理大整数

5. 综合实战案例

让我们通过一个完整的CTF题目示例来演示整个攻击流程：

题目描述：

给定RSA公钥(n, e)，其中e=3
已知密文c=0x5a4d8f1d4f
n=0xabcdef123456

解题步骤：

初步分析：
- e=3，符合低加密指数攻击条件
- 首先尝试m^e < n的情况
尝试直接开方：

n = 0xabcdef123456 e = 3 c = 0x5a4d8f1d4f try: print(attack_small_m(n, e, c)) except ValueError: print("直接开方失败，尝试爆破方式...") print(attack_large_m(n, e, c))