RsaCtfTool

是什么

RsaCtfTool 是一款专门用于 RSA 密码学攻击的 Python 工具，集成了多种已知的 RSA 攻击方法。它能够自动检测 RSA 参数的弱点并尝试各种攻击来恢复私钥或明文。在 CTF 密码学题目中，RsaCtfTool 是处理 RSA 相关题目最常用的自动化工具之一。

核心功能：

• 自动攻击：自动检测并尝试多种攻击方法
• Wiener 攻击：小私钥指数攻击
• Boneh-Durfee 攻击：更强大的小私钥指数攻击
• Fermat 分解：当 p 和 q 接近时
• Pollard p-1：当 p-1 光滑时
• Pollard rho：通用分解算法
• Hastad 攻击：小公钥指数广播攻击
• LSB/MSB 攻击：已知明文部分比特
• Coppersmith 攻击：小根攻击
• 自定义攻击：支持用户自定义攻击方法

安装与配置

安装方法

# 方法一：从 GitHub 克隆（推荐）
git clone https://github.com/RsaCtfTool/RsaCtfTool.git
cd RsaCtfTool
pip3 install -r requirements.txt

# 方法二：使用 pip
pip3 install RsaCtfTool

# 验证安装
python3 RsaCtfTool.py --help

依赖安装

# 安装依赖库
pip3 install gmpy2
pip3 install sympy
pip3 install pycryptodome
pip3 install sage  # 可选，用于某些高级攻击

# 或使用 requirements.txt
pip3 install -r requirements.txt

环境配置

# 基本配置
# RsaCtfTool 无需额外配置，直接使用即可

# 如需使用 SageMath 攻击，确保 Sage 已安装
sage --version

基本用法

自动攻击模式

# 使用公钥文件攻击
python3 RsaCtfTool.py --publickey public.pem --private

# 使用 n 和 e 值攻击
python3 RsaCtfTool.py --publickey public.pem --private

# 攻击并解密密文
python3 RsaCtfTool.py --publickey public.pem --uncipherfile cipher.txt

# 指定输出私钥文件
python3 RsaCtfTool.py --publickey public.pem --private --output private.pem

查看支持的攻击方法

# 列出所有攻击方法
python3 RsaCtfTool.py --list

# 查看特定攻击的详细信息
python3 RsaCtfTool.py --attack wiener --help

指定攻击方法

# 使用特定攻击
python3 RsaCtfTool.py --publickey public.pem --attack wiener
python3 RsaCtfTool.py --publickey public.pem --attack fermat
python3 RsaCtfTool.py --publickey public.pem --attack hastad

# 使用多个攻击
python3 RsaCtfTool.py --publickey public.pem --attack wiener,fermat

直接使用 n 和 e

# 直接指定 n 和 e
python3 RsaCtfTool.py --createkey 123456789 65537 --private

# 使用十进制值
python3 RsaCtfTool.py --publickey <(echo "-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA1234567890...
-----END PUBLIC KEY-----")

CTF常用技巧

常见 RSA 攻击场景

场景 1：Wiener 攻击（小私钥指数）

# 当 d 较小时（d < n^0.25）
python3 RsaCtfTool.py --publickey public.pem --attack wiener --private

原理：当私钥 d 足够小时，可以使用连分数展开恢复 d。

场景 2：Fermat 分解（p 和 q 接近）

# 当 |p - q| 较小时
python3 RsaCtfTool.py --publickey public.pem --attack fermat --private

原理：当 p 和 q 接近时，n 可以表示为两个接近的数的乘积，使用 Fermat 分解方法。

场景 3：Pollard p-1（p-1 光滑）

# 当 p-1 只有小素因子时
python3 RsaCtfTool.py --publickey public.pem --attack pollard_p_1 --private

原理：利用 p-1 的光滑性，使用 Pollard p-1 算法分解 n。

场景 4：Hastad 攻击（小公钥指数广播）

# 当 e=3 且有多个密文时
python3 RsaCtfTool.py --publickey key1.pem key2.pem key3.pem --attack hastad --uncipherfile cipher1.txt cipher2.txt cipher3.txt

原理：当使用小公钥指数 e 对相同明文加密多次时，可以使用中国剩余定理恢复明文。

场景 5：共模攻击（相同 n 不同 e）

# 当使用相同 n 但不同 e 加密时
python3 RsaCtfTool.py --publickey key1.pem key2.pem --attack same_n_huge_e --uncipherfile cipher1.txt cipher2.txt

原理：如果 gcd(e1, e2) = 1，可以使用扩展欧几里得算法恢复明文。

场景 6：已知 p 或 q

# 当已知一个素因子时
python3 RsaCtfTool.py --publickey public.pem --attack known_factors --private --p 123456789

场景 7：部分私钥泄露

# 当 d 的部分比特已知时
python3 RsaCtfTool.py --publickey public.pem --attack partial_d --private

批量攻击

# 批量处理多个公钥
for key in keys/*.pem; do
    python3 RsaCtfTool.py --publickey "$key" --private --output "private_$(basename $key)"
done

自定义攻击

# RsaCtfTool 支持自定义攻击脚本
# 在 attacks/ 目录下创建新的攻击模块

# 示例：自定义攻击模板
class CustomAttack:
    def __init__(self, n, e):
        self.n = n
        self.e = e
    
    def attack(self):
        # 实现攻击逻辑
        # 返回 (p, q, d) 或 None
        pass

配合其他工具使用

# 使用 openssl 生成公钥
openssl rsa -pubin -in public.pem -text -noout

# 使用 RsaCtfTool 攻击
python3 RsaCtfTool.py --publickey public.pem --private

# 使用私钥解密
openssl rsautl -decrypt -inkey private.pem -in cipher.bin

# 或使用 Python
from Crypto.PublicKey import RSA
key = RSA.import_key(open('private.pem').read())

处理不同格式的密钥

# PEM 格式
python3 RsaCtfTool.py --publickey public.pem --private

# DER 格式
python3 RsaCtfTool.py --publickey public.der --private

# 直接使用 n 和 e
python3 RsaCtfTool.py --createkey <n> <e> --private

解密文件

# 攻击并解密
python3 RsaCtfTool.py --publickey public.pem --uncipherfile cipher.txt

# 使用私钥解密
python3 RsaCtfTool.py --key private.pem --uncipherfile cipher.txt

# 输出明文
python3 RsaCtfTool.py --publickey public.pem --uncipherfile cipher.txt --decrypt

常见 RSA 攻击原理总结

1. Wiener 攻击
   条件：d < n^0.25
   原理：连分数展开
   
2. Fermat 分解
   条件：|p - q| < n^0.25
   原理：n = ((p+q)/2)^2 - ((p-q)/2)^2
   
3. Pollard p-1
   条件：p-1 光滑
   原理：费马小定理
   
4. Hastad 攻击
   条件：e=3，多个密文
   原理：中国剩余定理
   
5. 共模攻击
   条件：相同 n，不同 e
   原理：扩展欧几里得算法
   
6. 低加密指数攻击
   条件：e=3，单个密文
   原理：m^3 < n 时直接开立方

验证攻击结果

# 使用 Python 验证
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

# 加载私钥
with open('private.pem', 'r') as f:
    key = RSA.import_key(f.read())

# 解密
cipher = PKCS1_OAEP.new(key)
plaintext = cipher.decrypt(ciphertext)
print(plaintext.decode())

常见问题

攻击失败

原因：RSA 参数没有已知的弱点。

解决：

1. 尝试所有攻击方法：--attack all
2. 检查输入的公钥格式是否正确
3. 确认 n 和 e 的值是否正确
4. 考虑是否需要其他攻击方法

依赖库缺失

解决：

pip3 install -r requirements.txt

# 特别是 gmpy2
pip3 install gmpy2

# 如有编译错误，安装系统依赖
sudo apt install libgmp-dev libmpfr-dev libmpc-dev

公钥格式错误

解决：

# 检查公钥格式
openssl rsa -pubin -in public.pem -text -noout

# 转换 DER 到 PEM
openssl rsa -pubin -inform DER -in public.der -outform PEM -out public.pem

# 从 n 和 e 创建公钥
python3 -c "
from Crypto.PublicKey import RSA
n = 123456789
e = 65537
key = RSA.construct((n, e))
print(key.export_key().decode())
"

攻击速度慢

原因：某些攻击（如 Pollard rho）对大数分解较慢。

解决：

1. 先尝试快速攻击（Wiener、Fermat）
2. 使用更强的计算资源
3. 尝试其他工具（如 yafu、msieve）

解密结果乱码

原因：填充方式不匹配或解密失败。

解决：

1. 确认加密时使用的填充方式
2. 尝试不同的解密方法
3. 检查明文是否经过编码

无法识别公钥格式

解决：

# 手动提取 n 和 e
python3 -c "
from Crypto.PublicKey import RSA
with open('public.pem', 'r') as f:
    key = RSA.import_key(f.read())
print(f'n = {key.n}')
print(f'e = {key.e}')
"

# 使用 n 和 e 直接攻击
python3 RsaCtfTool.py --createkey <n> <e> --private

多个公钥攻击失败

原因：公钥之间没有数学关系。

解决：

1. 确认公钥是否使用了相同的 n
2. 检查是否满足特定攻击的条件
3. 尝试手动构造攻击

内存不足

解决：

# 增加 Python 内存限制
# 或使用更高效的算法
# 或分批处理