当前位置：首页 > news >正文

从BUUCTF RSAROLL看RSA多密文拼接攻击实战

news 2026/6/20 9:01:24

1. 初识RSAROLL：CTF中的RSA变体挑战

第一次看到BUUCTF的RSAROLL题目时，我和大多数CTF新手一样有点懵。题目附件里只有两个txt文件，一个写着"RSA roll！roll！roll！"，另一个则是一串数字：{920139713,19}开头，后面跟着几十个看似随机的长数字。这种题目形式在传统RSA密码学题目中并不常见，后来我才明白这就是典型的"多密文拼接"题型。

这类题目的核心特征非常明显：使用同一组RSA公钥参数(n,e)加密多个明文块。在RSAROLL这个具体案例中，flag被拆分成单个字符（或小段）分别加密，每个密文对应flag的一个片段。这种设计就像把flag切成碎片后分别用同一个保险箱上锁，解题者需要先破解保险箱密码，再把所有碎片拼回原样。

与传统RSA题目相比，这类题型有三个显著特点：

密文数组：会给出多个密文而非常见的单个密文
明文关联：每个密文对应的明文之间存在逻辑关联（如flag的连续字符）
参数复用：所有加密操作使用相同的n和e参数

我第一次做这道题时犯了个典型错误——试图用常规RSA解题思路处理。直到发现数字列表前两个是n和e，后面全是密文数组时才恍然大悟。这种"Roll"式加密在CTF中其实很常见，比如2022年HGAME的Easy RSA也采用了类似手法，只是具体实现略有不同。

2. 解剖RSAROLL：题目结构与密码学原理

让我们仔细拆解这道题的具体结构。题目给出的数据可以分为三个部分：

{n,e} = {920139713,19} 密文数组 = [704796792, 752211152, ..., 306220148]

在传统RSA中，加密过程可以表示为：c ≡ m^e mod n。这道题的特殊之处在于：

同一个n和e被用于加密多个明文块
每个明文块m_i对应flag的一个片段
所有密文c_i按照固定顺序排列

关键突破点在于分解n。题目中的n=920139713看起来不大，用yafu等工具可以快速分解：

p = 18443 q = 49891 n = p*q = 920139713

有了p和q，我们就能计算出私钥参数d：

φ(n) = (p-1)*(q-1) = 18442*49890 = 920071380 d ≡ e^-1 mod φ(n) => d = 19^-1 mod 920071380

使用Python的libnum库可以轻松计算模逆：

import libnum d = libnum.invmod(e, (p-1)*(q-1))

这个d值就是我们的"万能钥匙"，可以解密所有用同一对(n,e)加密的密文。这也是多密文RSA题目最显著的特征——一旦破解一个密文，就等于破解了所有密文。

3. 解密实战：从密文到明文的完整过程

拿到私钥参数d后，解密过程就变得直接了当。对于密文数组中的每个c_i，我们计算：

m_i = pow(c_i, d, n)

但在实际操作中，有几个细节需要注意：

数据类型转换：CTF中的flag通常是ASCII字符串，所以需要将数字转换为字节
解密顺序：密文数组的顺序就是flag片段的原始顺序，不能打乱
异常处理：有时解密结果可能包含非打印字符，需要适当处理

完整的解密脚本如下：

import libnum from Crypto.Util.number import long_to_bytes n = 920139713 e = 19 p = 18443 q = 49891 ciphertexts = [704796792, 752211152, ..., 306220148] # 完整密文数组 # 计算私钥 phi = (p-1)*(q-1) d = libnum.invmod(e, phi) flag = "" for c in ciphertexts: m = pow(c, d, n) flag += long_to_bytes(m).decode('latin-1') # 处理可能的非ASCII字符 print("Flag:", flag)

这个脚本的运行结果就是拼接好的完整flag。值得注意的是，**long_to_bytes().decode()**这一步很关键，它确保了数字到字符串的正确转换。有时候解密出的字节可能不在标准ASCII范围内，使用'latin-1'编码可以避免解码错误。

4. 同类题型扩展与防御思路

RSAROLL这类题目在CTF竞赛中非常典型，类似的变体还有：

分块加密：将flag分成固定大小的块（如16字节）分别加密
参数复用：不同题目使用相同的n但不同的e（共模攻击）
部分泄露：故意泄露部分明文或密钥信息

以HGAME 2022的Easy RSA为例，它采用了分块加密策略，每个块单独用RSA加密。解题思路与RSAROLL类似，但需要额外注意块大小的处理。

对于这类题目，出题人通常会设置一些陷阱：

使用特别大的n（需要更高效的分解算法）
在密文数组中混入干扰项
采用非标准的编码方式

防御性编程建议：

始终检查n是否可分解（使用factordb或yafu）
注意密文与明文的对应关系
准备好处理各种编码转换（ASCII、UTF-8、Base64等）

在实际比赛中，我建议准备一个RSA解题工具包，包含以下功能：

自动分解小整数n
计算模逆
批量解密功能
常用编码转换工具

5. 从解题到出题：多密文RSA的设计艺术

理解了这类题目的解题方法后，反过来思考如何设计这类题目也很有意义。一个好的RSAROLL类题目应该具备：

清晰的难度梯度：让解题者能逐步发现规律
合理的提示：如题目名称中的"Roll"暗示拼接操作
适当的挑战性：比如加入少量干扰密文

设计题目时可以参考以下流程：

# 伪代码：RSAROLL题目生成器 def generate_rsaroll_challenge(flag): p, q = generate_primes() # 生成合适的素数 n = p * q e = 65537 # 常见公钥指数 ciphertexts = [] for char in flag: m = ord(char) # 字符转ASCII码 c = pow(m, e, n) ciphertexts.append(c) return { 'n': n, 'e': e, 'ciphertexts': ciphertexts }

这种题目设计模式可以灵活变化，比如：