CTF实战：Python脚本破解RSA低加密指数（e=3）的两种攻击场景剖析

在CTF竞赛的密码学挑战中，RSA低加密指数攻击是最经典的突破口之一。当公钥指数e=3时，看似安全的加密系统实则暗藏玄机。本文将深入解析两种典型攻击场景，并提供可直接用于赛场的Python实战代码。

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

RSA加密的基本公式是$c \equiv m^e \mod n$。当e取值过小时，会出现以下两种脆弱性场景：

场景一：明文立方未溢出模数
当$m^3 < n$时，取模运算实际上不会改变数值。此时密文$c$就是明文$m$的立方值，攻击者只需对$c$开三次方即可还原明文。

数学表达： $$ \begin{cases} c = m^3 \mod n \ m^3 < n \end{cases} \Rightarrow c = m^3 $$

场景二：明文立方超过模数
当$m^3 > n$时，密文$c$是$m^3$除以$n$的余数。此时需要通过爆破技术寻找满足条件的整数$k$，使得$kn + c$为完全立方数。

数学表达： $$ m^3 = kn + c \quad (k \in \mathbb{Z}^+) $$

2. 实战环境准备

在开始攻击前，需要配置Python环境并安装必要的密码学库：

pip install gmpy2 pycryptodome

关键库说明：

• gmpy2 ：提供高精度数学运算支持
• Crypto.Util.number ：处理大整数与字节转换

注意：CTF竞赛中通常给出的是十六进制格式的n、e、c参数，需要先转换为十进制整数

3. 场景一攻击：直接开立方

当满足$m^3 < n$条件时，攻击脚本实现如下：

from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes

n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
e = 0x3
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365

# 十六进制转十进制
n = int(n)
e = int(e)
c = int(c)

# 直接开立方根
m = iroot(c, e)
if m[1]:  # 检查是否为完全立方数
    print("破解成功:", long_to_bytes(m[0]))
else:
    print("不符合m^3 < n条件，需采用场景二攻击")

关键函数说明：

• iroot(c, e) ：计算c的e次方根，返回元组(结果, 是否完全整除)
• long_to_bytes() ：将大整数转换为ASCII字符串

4. 场景二攻击：爆破寻找k值

当$m^3 > n$时，需要实现爆破脚本：

from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes

n = 0xabc123...  # 替换为实际模数
e = 0x3
c = 0xdef456...  # 替换为实际密文

n = int(n)
e = int(e)
c = int(c)

max_k = 1000000  # 设置合理的爆破上限

for k in range(max_k):
    candidate = k * n + c
    m = iroot(candidate, e)
    if m[1]:
        print(f"爆破成功 k={k}:", long_to_bytes(m[0]))
        break
else:
    print(f"在k<{max_k}范围内未找到解")

爆破优化技巧：

1. 并行计算 ：使用多线程加速爆破过程
2. 进度显示 ：每10000次迭代打印当前进度
3. 断点续跑 ：将k值保存到文件，意外中断后可继续

5. 实战调试技巧与常见问题

5.1 判断攻击场景的方法

判断依据	场景一 ($m^3 < n$)	场景二 ($m^3 > n$)
密文长度	通常较短	接近模数长度
测试方法	直接对c开立方	需要爆破k值

5.2 常见报错处理

• gmpy2安装失败 ：尝试使用预编译版本

  pip install gmpy2==2.0.8
  

• 爆破效率低下 ：

  • 优化k值搜索范围（通常k不会太大）
  • 使用PyPy解释器加速循环

• 编码问题 ：

  • 尝试多种编码方式（UTF-8、ASCII等）
  • 检查是否有非打印字符

5.3 性能优化对比

方法	时间复杂度	适用场景
直接开方	O(1)	$m^3 < n$
爆破攻击	O(k)	$m^3 > n$

6. 扩展攻击场景与防御措施

虽然本文聚焦e=3的情况，但类似原理也适用于其他小指数（如e=5）。现代RSA实践中的防御方案包括：

• 使用标准加密指数（通常65537）
• 对明文进行随机填充（OAEP模式）
• 确保明文长度足够大

在CTF比赛中遇到这类题目时，建议首先检查：

1. 公钥指数e的大小
2. 明文与模数的长度关系
3. 是否有特殊编码或填充