文章总结： 该CTF题目解析了babyRSA1，一种将RSA迁移到GF(2)多项式环的变体加密系统。由于多项式分解远比整数分解容易，系统存在严重安全漏洞。解题方法包括分解多项式n，计算s=(2^deg(p)-1)*(2^deg(q)-1)，求私钥d解密获取flag。最终flag提示保持N为整数，强调传统RSA的安全性基础。 综合评分： 100 文章分类： CTF,漏洞分析,密码学
babyRSA1 CTF题目深度技术解析
原创
破镜安全
破镜安全
2025年12月20日 08:00 四川
babyRSA1 CTF题目深度技术解析
一、题目概述
babyRSA1是一道密码学题目，考察的是RSA算法在非传统代数结构上的实现。与我们熟悉的在整数环上运算的RSA不同，本题将RSA迁移到了有限域GF(2)上的多项式环中。这种变体在理论上是可行的，但在安全性上存在严重缺陷，正是这个缺陷为我们的破解提供了可能。
二、题目附件分析
题目提供了三个关键文件：
2.1 加密脚本 rsa.sage
#!/usr/bin/env sage
# coding=utf-8
from pubkey import P, n, e
from secret import flag
from os import urandom
R.<a> = GF(2^2049)
def encrypt(m):
global n
assert len(m) <= 256
m_int = Integer(m.encode('hex'), 16)
m_poly = P(R.fetch_int(m_int))
c_poly = pow(m_poly, e, n)
c_int = R(c_poly).integer_representation()
c = format(c_int, '0256x').decode('hex')
return c
if __name__ == '__main__':
ptext = flag + os.urandom(256-len(flag))
ctext = encrypt(ptext)
with open('flag.enc', 'wb') as f:
f.write(ctext)
这个脚本展示了加密的完整流程：
- 定义有限域 GF(2^2049)
- 将明文转换为整数
- 将整数转换为GF(2^2049)中的元素
- 将该元素表示为多项式环P中的多项式
- 执行RSA加密：c_poly = m_poly^e mod n
- 将结果转回字节并保存
2.2 公钥文件 pubkey.py
from sage.all import GF, PolynomialRing
P=PolynomialRing(GF(2),'x')
e = 31337
n = P('x^2048 + x^2046 + x^2043 + ... + x^3 + 1')
公钥包含三个关键信息：
- P: 定义在GF(2)上的多项式环，变量为x
- e: 公钥指数，值为31337
- n: 一个2048次的多项式，系数只能是0或1
这个n相当于传统RSA中的模数，但这里它是一个多项式而非整数。
2.3 加密文件 flag.enc
这是一个256字节的二进制文件，包含加密后的flag。
三、传统RSA快速回顾
在深入多项式RSA之前，我们先回顾传统RSA的核心原理：
3.1 密钥生成
- 选择两个大素数 p 和 q
- 计算模数 n = p × q
- 计算欧拉函数 φ(n) = (p-1)(q-1)
- 选择公钥指数 e，满足 gcd(e, φ(n)) = 1
- 计算私钥指数 d = e^(-1) mod φ(n)
3.2 加密与解密
- 加密：c = m^e mod n
- 解密：m = c^d mod n
3.3 安全性基础
RSA的安全性建立在大整数分解的困难性上。已知n，如果无法分解得到p和q，就无法计算φ(n)，进而无法得到私钥d。
四、多项式RSA的理论基础
4.1 什么是GF(2)上的多项式环
GF(2) 是只包含两个元素{0, 1}的有限域，其运算规则为：
- 加法：0+0=0, 0+1=1, 1+0=1, 1+1=0（相当于XOR）
- 乘法：0×0=0, 0×1=0, 1×0=0, 1×1=1（相当于AND）
PolynomialRing(GF(2), ‘x’) 表示系数在GF(2)中的多项式环。例如：
- x^3 + x + 1 是一个合法的多项式（系数都是1）
- 2x^2 + x 不合法（系数2不在GF(2)中）
在这个环中：
- 多项式加法：对应项系数相加（在GF(2)中）
- 多项式乘法：标准的多项式乘法，但系数运算在GF(2)中
4.2 GF(2^2049)的含义
GF(2^2049)是一个包含2^2049个元素的有限域。这个域的每个元素可以表示为一个次数小于2049的多项式，系数在GF(2)中。
在SageMath中定义 R.<a> = GF(2^2049) 时：
- R是这个有限域
- a是这个域的生成元
- 该域的元素可以表示为 a0 + a1×a + a2×a^2 + … + a2048×a^2048，其中ai∈{0,1}
4.3 多项式环中的RSA如何工作
在多项式环上实现RSA时，需要找到对应的”欧拉函数”。理论研究表明，当n是两个不可约多项式p和q的乘积时：
关键公式：s = (2^deg(p) – 1) × (2^deg(q) – 1)
这里：
- deg(p)表示多项式p的次数
- s就是多项式环RSA中的”欧拉函数值”
- 私钥d满足：d = e^(-1) mod s
为什么是这个公式？
这源于有限域的乘法群结构。对于GF(2)上次数为k的不可约多项式f，商环GF(2)[x]/(f)构成一个有2^k个元素的有限域，其乘法群有2^k-1个元素。
当n=p×q时，根据中国剩余定理，存在环同构： GF(2)[x]/(n) ≅ GF(2)[x]/(p) × GF(2)[x]/(q)
因此，可逆元的个数为 (2^deg(p)-1) × (2^deg(q)-1)。
五、题目加密机制深度剖析
现在我们逐行分析加密过程，理解每一步的数学含义。
5.1 第一步：明文到整数
m_int = Integer(m.encode('hex'), 16)
这一步将字节串转换为一个大整数。例如，字符串”flag”：
- 字节表示：[0x66, 0x6c, 0x61, 0x67]
- 十六进制：”666c6167″
- 整数：1718578535
5.2 第二步：整数到有限域元素
m_poly = P(R.fetch_int(m_int))
这是最关键也最复杂的一步，实际上包含两个子步骤：
步骤A：R.fetch_int(m_int)
这个方法将整数转换为GF(2^2049)中的元素。具体做法是：
- 将整数m_int看作二进制表示
- 将二进制的每一位对应到多项式的系数
例如，整数13的二进制是1101，对应多项式 x^3 + x^2 + 1
步骤B：P(...)
将GF(2^2049)中的元素转换为多项式环P中的多项式表示。这个多项式的系数在GF(2)中，次数小于2049。
5.3 第三步：RSA加密
c_poly = pow(m_poly, e, n)
这是标准的模幂运算，但在多项式环中进行：
- 计算 m_poly 的 e 次方
- 结果对 n 取模（多项式除法的余数）
这完全类似于传统RSA的 c = m^e mod n，只是操作对象从整数变成了多项式。
5.4 第四步：结果转回字节
c_int = R(c_poly).integer_representation()
c = format(c_int, '0256x').decode('hex')
这是加密过程的逆向：
- 将多项式转回GF(2^2049)中的元素
- 将该元素转换为整数
- 将整数格式化为十六进制字符串
- 转换为字节串
六、寻找突破口：多项式分解
6.1 传统RSA的困难
在传统RSA中，分解大整数n是计算上不可行的。例如，分解一个2048位的整数，即使用当前最强的计算机和算法，也需要数百年时间。
6.2 多项式分解的区别
然而，在GF(2)上分解多项式的情况完全不同：
- 算法成熟：存在高效的多项式因式分解算法，如Berlekamp算法、Cantor-Zassenhaus算法
- 复杂度较低：多项式分解的复杂度远低于大整数分解
- 工具支持：SageMath等数学软件内置了高效的多项式分解功能
这就是本题的核心漏洞！
出题者将RSA迁移到多项式环，虽然保持了算法结构的一致性，但破坏了安全性的基础——”分解困难”这一前提不再成立。
七、解题思路与步骤
基于以上分析，我们的解题策略是：
7.1 整体思路
- 分解多项式n，得到p和q
- 计算s = (2^deg(p) – 1) × (2^deg(q) – 1)
- 计算私钥d = e^(-1) mod s
- 实现解密函数，计算m = c^d mod n
- 解密flag.enc获取明文
7.2 为什么这个思路可行
- 分解可行性：n只有2048次，在多项式环中这是可以快速分解的规模
- 理论正确性：s的计算公式已经过数学证明
- 实现简单：SageMath提供了所有需要的工具
八、编写解密脚本
8.1 导入必要的模块
#!/usr/bin/env sage
# coding=utf-8
from pubkey import P, n, e
R.<a> = GF(2^2049)
这里我们导入公钥参数，并定义与加密时相同的有限域。
8.2 实现解密函数
解密函数是加密函数的逆过程：
def decrypt(c, d):
"""解密函数"""
# 步骤1：bytes -> 整数
if isinstance(c, bytes):
c_int = Integer(c.hex(), 16)
else:
c_int = Integer(c.encode('hex'), 16)
# 步骤2：整数 -> GF(2^2049) 元素 -> 多项式
c_elem = R.from_integer(c_int)
c_poly = P(c_elem)
# 步骤3：RSA 解密
m_poly = pow(c_poly, d, n)
# 步骤4：多项式 -> GF(2^2049) 元素 -> 整数
m_elem = R(m_poly)
m_int = m_elem.to_integer()
# 步骤5：整数 -> bytes
m_hex = format(m_int, '0256x')
m = bytes.fromhex(m_hex)
return m
注意版本兼容性问题：
- 题目的加密脚本使用了
R.fetch_int()和integer_representation() - 这些方法在旧版本SageMath中存在，但在新版本（10.7+）中已改名
- 新版本使用
R.from_integer()和to_integer() - 解密时需要根据实际使用的SageMath版本调整方法名
8.3 主程序：分解、计算、解密
if __name__ == '__main__':
# 步骤1：分解多项式n
print("[*] 开始分解多项式 n...")
factors = n.factor()
print("[+] 分解结果:")
print(factors)
# 步骤2：获取两个素因子
p, q = factors[0][0], factors[1][0]
print(f"\n[+] p 的次数: {p.degree()}")
print(f"[+] q 的次数: {q.degree()}")
# 步骤3：计算 s (类似欧拉函数)
s = (2^p.degree() - 1) * (2^q.degree() - 1)
print(f"\n[*] 计算 s = (2^{p.degree()} - 1) * (2^{q.degree()} - 1)")
print(f"[+] s = {s}")
# 步骤4：计算私钥 d
print(f"\n[*] 计算私钥 d = inverse_mod({e}, s)")
d = inverse_mod(e, s)
print(f"[+] d = {d}")
# 步骤5：读取并解密 flag
print("\n[*] 读取加密的 flag...")
with open('flag.enc', 'rb') as f:
ctext = f.read()
print("[*] 解密中...")
plaintext = decrypt(ctext, d)
print("\n[+] 解密结果:")
print(plaintext)
8.4 脚本关键点说明
因式分解：n.factor() 返回的是一个因式分解列表，每个元素是 (因子, 幂次) 的元组。对于本题，n分解为两个不可约多项式p和q，幂次都是1。
次数检验：分解后应验证 deg(p) + deg(q) = deg(n)，确保分解正确。
大数运算：s 和 d 都是非常大的整数（数百位），SageMath使用任意精度整数，可以正确处理。
九、运行脚本并分析结果
将完整的解密脚本保存为 decrypt.sage，然后运行：
sage decrypt.sage
9.1 分解结果
[*] 开始分解多项式 n...
[+] 分解结果:
(x^821 + x^820 + ... + x + 1) * (x^1227 + x^1226 + ... + x + 1)
分解成功！我们得到：
- p：821次不可约多项式
- q：1227次不可约多项式
- 验证：821 + 1227 = 2048 = deg(n)
这个分解在现代计算机上只需要几秒钟，这证实了多项式分解相比整数分解的巨大差异。
9.2 密钥计算
[+] p 的次数: 821
[+] q 的次数: 1227
[*] 计算 s = (2^821 - 1) * (2^1227 - 1)
[+] s = 323170060713110073007148766886699519604441026697154840321303454275246551...
s 是一个大约 600 位的十进制整数。
[*] 计算私钥 d = inverse_mod(31337, s)
[+] d = 283713550763582066518801088994479065763722662841542802823479571451201706...
成功计算出私钥d！这个d也是一个数百位的大整数。
9.3 解密结果
[*] 读取加密的 flag...
[*] 解密中...
[+] 解密结果:
b'flag{P1ea5e_k33p_N_as_A_inTegeR~~~~~~}jI\xc6\xb2\xa0\x8d\n\xf7k...'
解密成功！我们得到了flag：
flag{P1ea5e_k33p_N_as_A_inTegeR~~~~~~}
后面的乱码是因为加密脚本在flag后填充了随机字节：
ptext = flag + os.urandom(256-len(flag))
十、深入理解与思考
10.1 Flag的含义
flag的内容是：P1ea5e_k33p_N_as_A_inTegeR（请保持N为整数）
这其实是出题者的提示和警告：RSA应该在整数环上实现，而不应该迁移到其他代数结构。这个flag本身就是在告诉我们本题的核心漏洞所在。
10.2 为什么多项式RSA不安全
从理论到实践，我们总结多项式RSA的安全性问题：
1. 分解难度的差异
| 问题 | 最佳已知算法 | 实际复杂度 | | — | — | — | | 整数分解 | 数域筛法(GNFS) | 2048位整数：数百年 | | 多项式分解 | Berlekamp等 | 2048次多项式：数秒 |
2. 数学结构的差异
- 整数环：没有高效的分解算法
- 多项式环：存在多项式时间的分解算法
3. 有限域的特殊性
GF(2)上的运算有特殊性质（如加法即XOR），这为某些攻击提供了额外的工具。
10.3 抽象代数视角
从抽象代数的角度，RSA可以在任何唯一因式分解整环(UFD)上实现。但安全性不仅需要数学上的正确性，更需要计算上的困难性。
多项式环虽然是UFD，满足数学要求，但不满足”分解困难”这一安全前提。
10.4 实际密码学启示
这道题目给我们的启示：
- 安全性与可行性的区别：算法在数学上可行≠在密码学上安全
- 计算复杂性的重要性：密码学安全依赖于某些问题的计算困难性
- 代数结构的选择：不同的代数结构有不同的计算性质
- 实践的谨慎性：不要随意修改已被验证的密码方案
十一、相关知识拓展
11.1 类似的密码系统
NTRU (N-th degree TRUncated polynomial ring)
NTRU是一种基于多项式环的公钥密码系统，但它：
- 使用不同的数学结构（格理论）
- 不依赖分解困难性
- 被认为可以抵抗量子计算攻击
环上的签名方案
某些数字签名方案在多项式环上实现，如Ring-LWE签名，这些方案的安全性基于完全不同的困难问题（格问题）。
11.2 学习建议
要完全理解本题，建议学习：
- 抽象代数基础
- 群、环、域的概念
- 多项式环的性质
- 有限域理论
- 密码学原理
- RSA的数学基础
- 计算复杂性理论
- 公钥密码学的安全性定义
- SageMath使用
- 多项式运算
- 有限域操作
- 数论函数
十二、完整解密脚本
以下是经过测试可以成功运行的完整脚本：
#!/usr/bin/env sage
# coding=utf-8
from pubkey import P, n, e
R.<a> = GF(2^2049)
def decrypt(c, d):
"""解密函数"""
# Python 3 兼容处理 - 将bytes转换为整数
if isinstance(c, bytes):
c_int = Integer(c.hex(), 16)
else:
c_int = Integer(c.encode('hex'), 16)
# 整数 -> GF(2^2049) 元素 -> 多项式
c_elem = R.from_integer(c_int)
c_poly = P(c_elem)
# RSA解密：m_poly = c_poly^d mod n
m_poly = pow(c_poly, d, n)
# 多项式 -> GF(2^2049) 元素 -> 整数
m_elem = R(m_poly)
m_int = m_elem.to_integer()
# 整数 -> bytes
m_hex = format(m_int, '0256x')
m = bytes.fromhex(m_hex)
return m
if __name__ == '__main__':
print("[*] 开始分解多项式 n...")
factors = n.factor()
print("[+] 分解结果:")
print(factors)
# 获取两个素因子
p, q = factors[0][0], factors[1][0]
print(f"\n[+] p 的次数: {p.degree()}")
print(f"[+] q 的次数: {q.degree()}")
# 计算 s (类似欧拉函数)
s = (2^p.degree() - 1) * (2^q.degree() - 1)
print(f"\n[*] 计算 s = (2^{p.degree()} - 1) * (2^{q.degree()} - 1)")
print(f"[+] s = {s}")
# 计算私钥 d
print(f"\n[*] 计算私钥 d = inverse_mod({e}, s)")
d = inverse_mod(e, s)
print(f"[+] d = {d}")
# 读取并解密 flag
print("\n[*] 读取加密的 flag...")
with open('flag.enc', 'rb') as f:
ctext = f.read()
print("[*] 解密中...")
plaintext = decrypt(ctext, d)
print("\n[+] 解密结果:")
print(plaintext)
十三、总结
babyRSA1是一道优秀的密码学教学题目，它通过将RSA迁移到多项式环这一创新设计，深刻揭示了密码学中的几个重要原则：
- 安全性依赖于计算复杂性：数学上正确的算法未必是安全的密码系统
- 不要修改经过验证的方案：RSA在整数环上是安全的，迁移到其他结构可能破坏安全性
- 理论与实践的结合：需要同时理解数学原理和计算难度
- 代数结构很重要：不同的代数结构有不同的计算性质
通过解决这道题目，我们不仅学会了多项式RSA的攻击方法，更重要的是理解了密码学设计的基本原则。这种理解对于今后学习更高级的密码学知识，以及评估密码系统的安全性，都有重要意义。
最后，题目的flag P1ea5e_k33p_N_as_A_inTegeR 再次提醒我们：在密码学中，坚持使用经过充分研究和验证的方案，比盲目创新更为重要。
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式详见页面底部说明板块。
本文转载自：破镜安全 破镜安全《babyRSA1 CTF题目深度技术解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论