CTF新手必看：用Python脚本5分钟搞定BUUCTF的RSAROLL密码题

第一次参加CTF比赛时，看到Crypto题目总有种莫名的恐惧——那些数学公式和加密算法看起来高深莫测。直到我遇到了BUUCTF的RSAROLL这道题，才发现原来RSA解密可以如此直观有趣。本文将带你用Python脚本快速破解这道经典题目，即使你是刚接触CTF的新手也能轻松上手。

1. 题目分析与数据准备

打开题目附件，通常会看到两个txt文件。第一个文件 rsa_roll.txt 内容如下：

RSA roll！roll！roll！ Only number and a-z （don’t use editor which MS provide）

{920139713,19}

第二个文件 data.txt 则是一长串数字：

704796792 752211152 274704164 18414022 368270835 483295235 263072905 459788476 483295235 459788476 663551792 475206804 459788476 428313374 475206804 459788476 425392137 704796792 458265677 341524652 483295235 534149509 425392137 428313374 425392137 341524652 458265677 263072905 483295235 828509797 341524652 425392137 475206804 428313374 483295235 475206804 459788476 306220148

关键识别点 ：

• 第一个文件中的 {920139713,19} 明显是RSA的公钥对(n,e)
• 第二个文件中的数字序列就是需要解密的密文c
• 题目提示"ROLL"暗示需要将解密后的结果拼接起来

2. 环境配置与工具准备

在开始编写解密脚本前，需要确保Python环境已安装必要的库：

pip install pycryptodome libnum

如果遇到安装问题，可以尝试以下替代方案：

• 使用清华镜像源加速安装： pip install -i https://pypi.tuna.tsinghua.edu.cn/simple pycryptodome libnum
• 对于Python 3.10+用户，可能需要先安装 setuptools_rust

注意：在CTF竞赛环境中，通常会限制网络访问，建议提前在本地配置好这些依赖。

3. RSA解密核心原理

虽然题目已经给出了p和q，但理解背后的数学原理很重要：

1. 计算模数n = p × q = 18443 × 49891 = 920139713
2. 计算欧拉函数φ(n) = (p-1)(q-1) = 18442 × 49890 = 920071380
3. 已知公钥指数e=19，求私钥指数d ≡ e⁻¹ mod φ(n)
4. 对每个密文c，计算明文m ≡ cᵈ mod n

关键参数对比表 ：

参数	值	说明
p	18443	第一个质因数
q	49891	第二个质因数
n	920139713	模数(p×q)
e	19	公钥指数
φ(n)	920071380	欧拉函数值
d	193802719	私钥指数

4. 完整Python解密脚本

下面是经过优化的解密脚本，添加了详细的注释和错误处理：

import libnum
from Crypto.Util.number import long_to_bytes

# 密文数组
ciphertexts = [
    704796792, 752211152, 274704164, 18414022, 368270835, 483295235,
    263072905, 459788476, 483295235, 459788476, 663551792, 475206804,
    459788476, 428313374, 475206804, 459788476, 425392137, 704796792,
    458265677, 341524652, 483295235, 534149509, 425392137, 428313374,
    425392137, 341524652, 458265677, 263072905, 483295235, 828509797,
    341524652, 425392137, 475206804, 428313374, 483295235, 475206804,
    459788476, 306220148
]

# RSA参数
n = 920139713
p = 18443
q = 49891
e = 19

# 计算私钥d
phi = (p - 1) * (q - 1)
d = libnum.invmod(e, phi)  # 计算模反元素

flag = ""
for c in ciphertexts:
    # RSA解密：m = c^d mod n
    m = pow(c, d, n)
    
    # 将数字转换为ASCII字符
    char = long_to_bytes(m).decode('ascii')
    flag += char

print("解密结果:", flag)

常见问题解决方案 ：

1. ModuleNotFoundError 错误：

   • 确保已正确安装 pycryptodome 而非 pycrypto
   • 尝试使用 from Cryptodome.Util.number import long_to_bytes

2. 解密结果乱码：

   • 检查n、p、q的值是否正确
   • 确认密文数组是否完整复制

3. 性能优化：

   • 对于大型密文数组，可以预先计算d值
   • 使用多线程加速解密过程

5. 进阶技巧与变种题目

掌握基础解密后，可以尝试以下变种练习：

1. 已知n和e，但需要分解n获取p和q

import libnum

n = 920139713
e = 19

# 使用Fermat分解法（适用于p和q接近的情况）
def fermat_factor(n):
    a = libnum.sqrt(n) + 1
    b2 = a*a - n
    while not libnum.sqrt(b2)**2 == b2:
        a += 1
        b2 = a*a - n
    p = a - libnum.sqrt(b2)
    q = a + libnum.sqrt(b2)
    return int(p), int(q)

p, q = fermat_factor(n)
print(f"分解结果: p={p}, q={q}")

2. 多段密文拼接技巧

当flag被分割成多个密文段时，解密后需要注意：

• 保持密文顺序不变
• 处理可能存在的填充字符
• 注意字符编码一致性

3. 常见RSA题目变种对比

题目类型	已知条件	解题关键
标准RSA	n,e,c	分解n得到p,q
Wiener攻击	e很大	连分数展开
共模攻击	多组(n,e,c)	中国剩余定理
低加密指数	e=3	直接开立方

6. 实战演练与调试技巧

在实际比赛中，可能会遇到各种意外情况。以下是几个实用的调试技巧：

1. 分段验证 ：先解密前几个密文，确认输出是否符合预期
2. 中间值打印 ：在关键步骤打印中间结果

   print(f"解密过程: c={c}, m={m}, char={char}")
   

3. 边界检查 ：确保解密后的字符在可打印ASCII范围内
4. 时间优化 ：对于大型n，使用 gmpy2 库加速大数运算

# 使用gmpy2加速的版本
import gmpy2
from gmpy2 import mpz

n = mpz(920139713)
p = mpz(18443)
q = mpz(49891)
e = mpz(19)

phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)

for c in ciphertexts:
    m = pow(mpz(c), d, n)
    print(long_to_bytes(int(m)).decode(), end='')
print()

7. 安全注意事项与最佳实践

虽然我们在这里直接使用了给定的p和q，但在实际CTF比赛中：

1. 不要硬编码敏感参数 ：将关键参数作为脚本输入更符合实际场景
2. 参数验证 ：添加对p和q是否为质数的检查

   assert libnum.prime_test(p)
   assert libnum.prime_test(q)
   assert n == p * q
   

3. 错误处理 ：增加对异常输入的处理逻辑
4. 代码封装 ：将解密逻辑封装为函数，提高复用性

def rsa_decrypt(ciphertexts, n, p, q, e):
    phi = (p - 1) * (q - 1)
    try:
        d = libnum.invmod(e, phi)
    except ValueError:
        print("Error: e and phi(n) must be coprime")
        return None
    
    result = []
    for c in ciphertexts:
        m = pow(c, d, n)
        try:
            char = long_to_bytes(m).decode('ascii')
            result.append(char)
        except UnicodeDecodeError:
            print(f"Warning: Cannot decode {m}")
            continue
    
    return ''.join(result)

通过这道RSAROLL题目的实战，相信你已经掌握了RSA解密的基本流程。下次遇到类似题目时，可以按照这个思路快速解决：识别参数→准备环境→编写脚本→解密拼接。CTF的乐趣就在于这种从迷茫到豁然开朗的过程，当你看到flag终于呈现的那一刻，所有的努力都会变得值得。