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

1. 初识RSAROLLCTF中的RSA变体挑战第一次看到BUUCTF的RSAROLL题目时我和大多数CTF新手一样有点懵。题目附件里只有两个txt文件一个写着RSA rollrollroll另一个则是一串数字{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。题目中的n920139713看起来不大用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 }这种题目设计模式可以灵活变化比如对flag进行Base64编码后再分块加密使用多个n但相同的e在密文序列中加入随机干扰项理解出题思路不仅能帮助我们更好地解题也能提升密码学的整体认知。在最近的一次校内CTF中我就借鉴了RSAROLL的思路设计了一道密码学题目收到了不错的反馈。