文章总结： 本文解析RSA奇偶预言机攻击，利用乘法同态性构造密文查询服务器获取明文奇偶性，结合二分搜索算法在约2048次查询内恢复明文。文中提供Python攻击代码实战演示，并强调了采用OAEP填充方案及限制解密请求等防御侧信道攻击的关键措施。 综合评分： 93 文章分类： CTF,漏洞分析
Baby RSA – RSA奇偶预言机攻击深度解析
原创
破镜安全
破镜安全
2026年1月10日 08:02 四川
Baby RSA – RSA奇偶预言机攻击深度解析
一、题目背景与初步分析
1.1 题目信息
本题是一道经典的RSA密码学挑战，题目提供了以下关键信息：
RSA公钥参数：
e = 0x10001
n = 0x0b765daa79117afe1a77da7ff8122872bbcbddb322bb078fe0786dc40c9033fadd639adc48c3f2627fb7cb59bb0658707fe516967464439bdec2d6479fa3745f57c0a5ca255812f0884978b2a8aaeb750e0228cbe28a1e5a63bf0309b32a577eecea66f7610a9a4e720649129e9dc2115db9d4f34dc17f8b0806213c035e22f2c5054ae584b440def00afbccd458d020cae5fd1138be6507bc0b1a10da7e75def484c5fc1fcb13d11be691670cf38b487de9c4bde6c2c689be5adab08b486599b619a0790c0b2d70c9c461346966bcbae53c5007d0146fc520fa6e3106fbfc89905220778870a7119831c17f98628563ca020652d18d72203529a784ca73716db
加密后的密文：
c = 0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0
在线服务：
- 服务器地址：
nc 61.147.171.103 58521 - 服务器功能：接收密文，返回解密后明文的奇偶性
1.2 RSA加密基础
在深入分析之前，我们先回顾RSA加密的基本原理：
加密过程：
c = m^e mod n
解密过程：
m = c^d mod n
其中：
- m 是明文（plaintext）
- c 是密文（ciphertext）
- e 是公钥指数（public exponent）
- n 是模数（modulus），由两个大质数p和q相乘得到
- d 是私钥指数（private exponent）
1.3 常规解题思路的困境
面对这道题，我们首先想到的是常规的RSA破解方法：
方法一：分解n
- 如果能将n分解为p和q，就能计算出私钥d
- 但本题的n是2048位（约617个十进制数字）的大数
- 使用当前的计算能力，分解如此大的数字在合理时间内是不可能的
方法二：寻找数学漏洞
- 检查e和n是否互质：e = 65537，这是标准值
- 检查n是否为特殊形式：经过检查，n没有明显的数学特征
- 尝试常见的RSA攻击（如Wiener攻击、低加密指数攻击等）：均不适用
因此，常规的RSA破解方法在这道题中都行不通。
1.4 关键突破点：在线服务
题目提供的在线服务是解题的关键。让我们先连接服务器看看它的功能：
$ nc 61.147.171.103 58521
----------------------------- baby rsa -----------------------------
Come and Decode your data
If you give me ciphertext, I can tell you whether decoded data is even or odd
You can input ciphertext(hexdecimal) now
服务器明确告诉我们：
- 可以提交密文（十六进制格式）
- 服务器会解密密文
- 服务器会告诉我们解密后的明文是奇数还是偶数
这就是所谓的”奇偶预言机”（Parity Oracle）。
二、RSA同态性质的理解
在深入攻击原理之前，我们需要理解RSA加密的一个重要性质：同态性（Homomorphic Property）。
2.1 什么是同态性
RSA加密具有乘法同态性，这意味着：
如果 c1 = m1^e mod n
c2 = m2^e mod n
那么 c1 * c2 mod n = (m1 * m2)^e mod n
证明：
c1 * c2 mod n
= (m1^e mod n) * (m2^e mod n) mod n
= (m1^e * m2^e) mod n
= (m1 * m2)^e mod n
2.2 同态性的实际应用
这个性质告诉我们：我们可以通过操作密文来控制明文的变化。
具体来说，如果我们想让明文乘以2，只需要：
新密文 = 原密文 * (2^e mod n) mod n
解密后得到的新明文就是：
新明文 = 原明文 * 2 mod n
2.3 验证同态性
让我们通过一个简单的例子来验证这个性质。假设我们提交原始密文c到服务器：
$ echo "0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0" | nc 61.147.171.103 58521
服务器返回：odd（奇数）
这说明原始明文m是奇数。
三、攻击原理：二分搜索的巧妙应用
3.1 核心思想
现在我们有了两个关键工具：
- RSA的同态性：可以让明文乘以2
- 奇偶预言机：可以知道明文的奇偶性
如何利用这两个工具来恢复明文呢？答案是：二分搜索。
3.2 数学原理详解
让我们从数学角度分析这个攻击。
第一步：构造新密文
我们计算：
c' = c * 2^e mod n
第二步：服务器解密
服务器解密c’得到：
m' = (c')^d mod n
= (c * 2^e)^d mod n
= c^d * 2^(e*d) mod n
= m * 2 mod n
第三步：关键推理
现在考虑两种情况：
情况1：如果 m * 2 < n
- 那么 m’ = m * 2（没有发生模运算）
- 因为 m * 2 是偶数，所以 m’ 是偶数
- 这说明 m < n/2
情况2：如果 m * 2 >= n
- 那么 m’ = m * 2 – n（发生了模运算）
- 因为 m * 2 是偶数，n 是奇数（RSA中n总是奇数）
- 所以 m’ = 偶数 – 奇数 = 奇数
- 这说明 m >= n/2
结论： 通过一次查询，我们就能将明文的搜索范围缩小一半！
3.3 迭代过程
我们可以重复这个过程：
第二轮：
- 将第一轮的密文再乘以 2^e mod n
- 相当于让明文再乘以2，即 m * 4 mod n
- 根据奇偶性，继续缩小范围
第三轮：
- 明文变为 m * 8 mod n
- 继续缩小范围
以此类推，每次查询都将搜索空间减半。
3.4 复杂度分析
由于每次查询将搜索空间减半，所需的查询次数为：
查询次数 = log2(n) ≈ n的比特长度
对于本题，n是2048位的大数，因此只需要约2048次查询就能完全恢复明文。
四、攻击实现
4.1 算法流程
完整的攻击算法如下：
1. 初始化搜索区间：lower = 0, upper = n
2. 计算乘数：multiplier = 2^e mod n
3. 设置当前密文：current_c = c
4. 循环 n.bit_length() 次：
a. current_c = current_c * multiplier mod n
b. 发送 current_c 到服务器
c. 接收奇偶性响应
d. 如果是偶数：upper = (lower + upper) / 2
e. 如果是奇数：lower = (lower + upper) / 2
5. 最终 upper 即为明文 m
4.2 Python代码实现
下面是完整的攻击脚本：
#!/usr/bin/env python3
from pwn import *
from Crypto.Util.number import long_to_bytes
from decimal import Decimal, getcontext
# 设置高精度
getcontext().prec = 1024
# 题目参数
e = 0x10001
n = 0x0b765daa79117afe1a77da7ff8122872bbcbddb322bb078fe0786dc40c9033fadd639adc48c3f2627fb7cb59bb0658707fe516967464439bdec2d6479fa3745f57c0a5ca255812f0884978b2a8aaeb750e0228cbe28a1e5a63bf0309b32a577eecea66f7610a9a4e720649129e9dc2115db9d4f34dc17f8b0806213c035e22f2c5054ae584b440def00afbccd458d020cae5fd1138be6507bc0b1a10da7e75def484c5fc1fcb13d11be691670cf38b487de9c4bde6c2c689be5adab08b486599b619a0790c0b2d70c9c461346966bcbae53c5007d0146fc520fa6e3106fbfc89905220778870a7119831c17f98628563ca020652d18d72203529a784ca73716db
c = 0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0
# 查询预言机函数
def query_oracle(ciphertext):
conn = remote('61.147.171.103', 58521, level='error')
conn.recvuntil(b"now\n")
conn.sendline(hex(ciphertext).encode())
response = conn.recvline().decode().strip()
conn.close()
return 'even' in response.lower()
# 攻击主函数
lower = Decimal(0)
upper = Decimal(n)
multiplier = pow(2, e, n)
current_c = c
for i in range(n.bit_length()):
current_c = (current_c * multiplier) % n
is_even = query_oracle(current_c)
mid = (lower + upper) / 2
if is_even:
upper = mid
else:
lower = mid
plaintext = int(upper)
flag = long_to_bytes(plaintext)
print(f"Flag: {flag}")
4.3 代码关键点说明
1. 高精度计算
使用Python的Decimal类型而不是浮点数，因为n是2048位的大数，浮点数会导致精度损失。
2. 每次新建连接
经过测试发现，服务器每次连接只允许查询一次，因此每次查询都需要建立新的连接。
3. 边界更新逻辑
根据奇偶性更新搜索区间：偶数说明明文在下半区间，奇数说明明文在上半区间。
五、实战攻击过程
5.1 算法验证
在进行实际攻击之前，我们先在本地验证算法的正确性。
我们生成一个小的RSA密钥对，使用已知的明文进行加密，然后用我们的算法尝试恢复明文。
验证结果：
原始明文: b'flag{test_message}'
恢复的明文: b'flag{test_message}'
验证结果: 成功!
算法验证完全成功，证明了攻击方法的有效性。
5.2 实际服务器攻击
验证算法正确后，我们连接到实际的CTF服务器进行攻击。
服务器信息：
- 地址：61.147.171.103:58521
- 服务类型：RSA奇偶预言机
攻击过程：
运行攻击脚本后，程序开始执行2048次查询：
[Round 1/2048] 偶
[Round 2/2048] 偶
[Round 3/2048] 偶
...
[Round 1901/2048] 奇
[Round 2001/2048] 偶
[Round 2048/2048] 奇
攻击结果：
经过约13分钟的查询，成功获取flag：
Flag: QCTF{RSA_parity_oracle_is_fun}
5.3 攻击统计
- 总查询次数：2048次
- 攻击耗时：约13分钟
- 成功率：100%
六、防护措施
6.1 为什么这种攻击能成功
这个攻击之所以能成功，是因为：
- 信息泄露：服务器泄露了解密后明文的奇偶性
- RSA同态性：允许我们操作密文来控制明文
- 无限制查询：服务器允许多次查询
6.2 如何防御
使用填充方案
标准的RSA实现应该使用OAEP等填充方案：
- 在加密前对明文进行随机化
- 在解密后验证填充的正确性
- 如果填充验证失败，不返回任何信息
限制解密服务
在实际应用中应该：
- 限制同一密文的解密次数
- 对解密请求进行速率限制
- 不向客户端泄露任何解密失败的详细信息
七、总结
7.1 攻击要点回顾
RSA奇偶预言机攻击的核心要点：
- 利用RSA同态性：通过密文运算控制明文变化
- 信息泄露利用：利用奇偶性信息进行二分搜索
- 高效性：只需O(log n)次查询即可恢复明文
7.2 学习价值
通过这道题，我们学到了：
侧信道攻击的威力
即使只泄露1比特信息，通过巧妙利用也能完全破解加密系统。
密码学实现的重要性
算法本身可能是安全的，但实现不当会导致严重的安全问题。
理论与实践的结合
这个攻击结合了数论、算法和网络编程，是理论密码学与实践安全的完美结合。
7.3 结语
RSA奇偶预言机攻击展示了密码学安全的复杂性。安全不仅仅取决于算法本身，还取决于实现细节、部署方式和使用场景。
在实际应用中，我们应该：
- 使用经过验证的加密库和标准
- 避免泄露任何关于明文的信息
- 对解密服务进行适当的限制和监控
通过学习这个攻击，我们不仅掌握了一种具体的技术，更重要的是理解了密码学安全的本质。
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全《Baby RSA – RSA奇偶预言机攻击深度解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论