文章总结： 这篇文章详细解析了一道名为RSA-Buffet的CTF密码学题目，系统介绍了四种不同的RSA攻击技术：共因子攻击、Wiener攻击、Fermat分解和小素数攻击，结合Shamir秘密共享方案和混合加密系统的工作原理。文章从题目环境分析开始，逐步深入到加密方案解析、密钥破解实战和秘密恢复，最后提供了技术要点深度解析、防御建议和最佳实践。通过完整的技术解析和代码示例，读者可以学习到密码学安全缺陷的识别方法和系统化分析复杂问题的思路。 综合评分： 100 文章分类： CTF,密码学,漏洞分析,实战经验,WEB安全
RSA-Buffet：一道综合性RSA密码学题目的完整技术解析
原创
破镜安全
破镜安全
2025年12月22日 08:03 四川
RSA-Buffet：一道综合性RSA密码学题目的完整技术解析
前言
本文将详细分析一道名为RSA-Buffet的CTF密码学题目。这道题目设计精妙，涵盖了RSA密码系统的多个经典漏洞和攻击技术，同时结合了Shamir秘密共享方案，是一道非常好的密码学综合练习题。
通过本文，你将学习到：
- 如何系统性地分析密码学题目
- 四种不同的RSA攻击技术及其原理
- 混合加密系统的工作原理
- Shamir秘密共享的实际应用
- 密码学安全缺陷的识别方法
一、题目环境与初步观察
1.1 题目文件清单
拿到题目后，首先查看提供的文件：
$ ls -la
得到以下文件列表：
- 10个RSA公钥文件：key-0.pem 到 key-9.pem
- 5个密文文件：ciphertext-1.bin 到 ciphertext-5.bin
- 1个加密脚本：encrypt.py
- 1个明文生成脚本：generate-plaintexts.py
初步判断：
- 题目涉及RSA加密，有多个密钥可供选择
- 需要找到正确的密钥来解密密文
- 加密和明文生成脚本提供了算法细节
- 可能需要破解部分RSA私钥
1.2 为什么要先看这些文件
在密码学题目中，理解算法的实现细节至关重要。任何安全系统的弱点往往隐藏在实现细节中，而不是算法本身。因此，我们的第一步是深入分析提供的脚本。
二、加密方案深度分析
2.1 混合加密架构
打开encrypt.py，分析核心加密函数：
def encrypt(public_key, message):
# 步骤1：生成32字节随机对称密钥
symmetric_key = get_rand_bytes(32)
# 步骤2：使用RSA-OAEP加密对称密钥
msg_header = PKCS1_OAEP.new(public_key).encrypt(symmetric_key)
assert len(msg_header) == 512 # 4096位RSA加密后为512字节
# 步骤3：生成16字节随机IV
msg_iv = get_rand_bytes(16)
# 步骤4：使用AES-CFB模式加密消息
msg_body = AES.new(symmetric_key,
mode=AES.MODE_CFB,
IV=msg_iv).encrypt(message)
# 步骤5：拼接所有部分
return msg_header + msg_iv + msg_body
这是一个标准的混合加密方案，原理如下：
- 为什么不直接用RSA加密全部数据？
- RSA加密速度慢，只能加密有限长度的数据
- 4096位RSA最多只能加密约500字节数据
- 对于大数据，RSA效率极低
- 为什么采用混合加密？
- 使用AES（对称加密）加密实际数据，速度快
- 使用RSA（非对称加密）加密AES密钥，解决密钥分发问题
- 这是TLS/SSL等协议的标准做法
- 密文结构分析：
[512字节RSA加密的AES密钥] + [16字节IV] + [AES加密的消息]
| | | | | |
| 只能用RSA私钥解密 | | 明文传输 | | 需要AES密钥解密 |
安全性分析的关键点：
- 整个系统的安全性取决于RSA部分
- 如果能破解RSA私钥，就能解密AES密钥
- 一旦获得AES密钥，就能解密整个消息
- 因此，攻击目标应该是RSA密钥
2.2 秘密共享方案分析
打开generate-plaintexts.py，分析明文生成逻辑：
# 读取第一个消息，直接复制到所有明文
with open('message1.txt', 'r') as f:
PLAINTEXTS = [f.read()] * 5
# 对message2到message5使用不同门限的秘密共享
for i in range(2, 6):
with open('message' + str(i) + '.txt', 'r') as f:
msg = f.read()
# 使用i-out-of-5的门限方案
shares = SS.split_secret(msg, i, 5)
for j in range(5):
PLAINTEXTS[j] += shares[j] + '\n'
Shamir秘密共享原理：
Shamir秘密共享是一种将秘密分成多个分片的方案，具有以下特性：
- 数学基础：多项式插值
- 对于t-out-of-n门限方案，构造一个t-1次多项式
- 多项式的常数项是秘密S
- 生成n个点作为分片：(1, f(1)), (2, f(2)), …, (n, f(n))
- 门限特性：
- 任意t个分片可以通过拉格朗日插值恢复多项式
- 少于t个分片无法获得任何关于秘密的信息（完美安全）
- 本题的门限设置：
- Message1：不使用秘密共享，直接复制
- Message2：2-out-of-5（需要2个分片）
- Message3：3-out-of-5（需要3个分片）
- Message4：4-out-of-5（需要4个分片）
- Message5：5-out-of-5（需要全部5个分片）
解题策略推导：
- 有5个密文，如果全部解密，可以恢复所有秘密
- 如果只能解密3个密文，可以恢复Message1、Message2、Message3
- Flag很可能在Message3中（3是”magic number”）
- 因此，我们需要破解至少3个RSA私钥
三、RSA密钥漏洞识别
3.1 为什么要分析公钥参数
RSA密钥的安全性依赖于大整数分解的困难性。但如果密钥生成不当，会出现可被快速攻破的弱点。我们需要检查：
- 公钥指数e是否异常（太大或太小）
- 不同密钥的模数n是否有公共因子
- 素因子p和q的关系（是否过于接近）
- 是否使用了小素数
3.2 批量分析公钥参数
编写脚本提取所有公钥的参数：
from Crypto.PublicKey import RSA
for i in range(10):
key = RSA.import_key(open(f'key-{i}.pem').read())
print(f'Key-{i}:')
print(f' n位长度: {key.n.bit_length()}')
print(f' e位长度: {key.e.bit_length()}')
if key.e != 65537: # 65537是标准值
print(f' [!] e值异常: {key.e}')
运行结果分析：
Key-0: n=4096位, e=65537 ← 正常
Key-1: n=4096位, e=65537 ← 正常
Key-2: n=4096位, e=65537 ← 正常
Key-3: n=4096位, e=4094位 ← 异常！e值巨大
Key-4到Key-9: n=4096位, e=65537 ← 正常
第一个发现：Key-3的e值异常
在RSA中，公钥指数e通常选择65537，这是一个平衡安全性和效率的标准值。Key-3的e却有4094位，几乎和n一样大。
为什么这是一个问题？
RSA的密钥关系：e × d ≡ 1 (mod φ(n))
- 如果e很大，那么d必然很小（因为它们的乘积约等于φ(n)）
- 小的d会使密钥容易受到Wiener攻击
- 这是一个严重的安全缺陷
3.3 检测共同因子
编写脚本检查所有密钥对的最大公约数：
from math import gcd
# 读取所有密钥的n值
keys = []
for i in range(10):
key = RSA.import_key(open(f'key-{i}.pem').read())
keys.append((i, key.n))
# 检查任意两个密钥是否有公共因子
for i in range(len(keys)):
for j in range(i+1, len(keys)):
g = gcd(keys[i][1], keys[j][1])
if g > 1 and g != keys[i][1]:
print(f'发现共因子: key-{keys[i][0]} 和 key-{keys[j][0]}')
print(f' gcd位长度: {g.bit_length()}位')
运行结果：
发现共因子: key-0 和 key-6
gcd位长度: 2048位
第二个发现：Key-0和Key-6共享一个2048位的因子
为什么这是致命的？
RSA的安全性基于：n = p × q，其中p和q是保密的大素数
- 如果两个密钥n1和n2共享相同的p，那么gcd(n1, n2) = p
- 一旦知道p，就可以计算q = n / p
- 知道p和q后，就能轻易计算私钥d
这通常是由于：
- 随机数生成器故障
- 密钥生成时重用了随机数
- 故意构造的题目漏洞
3.4 攻击向量总结
基于以上分析，我们识别出以下攻击路径：
| 密钥 | 漏洞类型 | 攻击方法 | 难度 | | — | — | — | — | | Key-0 | 共享因子 | GCD攻击 | 极易 | | Key-3 | 大e小d | Wiener攻击 | 中等 | | Key-6 | 共享因子 | GCD攻击 | 极易 | | 其他 | 待分析 | Fermat分解/小素数 | 未知 |
我们已经可以确定攻破Key-0、Key-3、Key-6，但还需要分析其他密钥。
四、RSA密钥破解实战
4.1 攻击一：共因子攻击（Key-0和Key-6）
攻击原理详解：
假设两个RSA模数为：
- n1 = p × q1
- n2 = p × q2
如果它们共享素因子p，那么：
- gcd(n1, n2) = p
为什么gcd能找到公因子？
最大公约数（GCD）算法会找到两个数的最大公共因子。如果n1和n2都包含p作为因子，gcd就会返回p。
实现代码：
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse
# 欧几里得算法计算最大公约数
def gcd(a, b):
while b:
a, b = b, a % b
return a
# 读取两个密钥
key0 = RSA.import_key(open('key-0.pem').read())
key6 = RSA.import_key(open('key-6.pem').read())
n0, e0 = key0.n, key0.e
n6, e6 = key6.n, key6.e
# 计算最大公约数，得到共享的素因子p
p = gcd(n0, n6)
print(f'找到共享素因子p:')
print(f' p的位长度: {p.bit_length()}')
# 计算另一个素因子q
q0 = n0 // p
q6 = n6 // p
# 验证分解是否正确
assert p * q0 == n0, "n0分解错误"
assert p * q6 == n6, "n6分解错误"
print('验证通过！开始计算私钥...')
# 计算欧拉函数φ(n) = (p-1)(q-1)
phi0 = (p - 1) * (q0 - 1)
phi6 = (p - 1) * (q6 - 1)
# 计算私钥指数d = e^(-1) mod φ(n)
d0 = inverse(e0, phi0)
d6 = inverse(e6, phi6)
# 构造完整的私钥对象
private_key0 = RSA.construct((n0, e0, d0, p, q0))
private_key6 = RSA.construct((n6, e6, d6, p, q6))
# 保存私钥
with open('key-0-private.pem', 'wb') as f:
f.write(private_key0.export_key())
with open('key-6-private.pem', 'wb') as f:
f.write(private_key6.export_key())
print('私钥已成功生成并保存！')
关键知识点：
- 欧几里得算法：计算gcd的高效算法，时间复杂度O(log n)
- 模逆运算：d = e^(-1) mod φ(n)表示找到一个数d，使得e×d除以φ(n)余1
- RSA私钥构造：完整的私钥包含(n, e, d, p, q)五个参数
攻击成功！ 在不到1秒的时间内破解了两个密钥。
4.2 攻击二：Wiener攻击（Key-3）
攻击背景：为什么d小是个问题？
RSA解密时需要计算：m = c^d mod n
如果d很小，这个计算会很快，但安全性会大幅降低。Michael Wiener在1990年证明：如果d < n^(1/4) / 3，则可以通过连分数方法在多项式时间内恢复d。
攻击原理：连分数展开
从RSA密钥关系出发：
e × d = 1 + k × φ(n)
变形得：
e/φ(n) = k/d + 1/(d×φ(n))
当d很小时，1/(d×φ(n))非常小，因此：
e/φ(n) ≈ k/d
又因为φ(n) = (p-1)(q-1)接近n（对于大素数p和q），所以：
e/n ≈ k/d
关键洞察：
- k/d是e/n的一个很好的有理逼近
- 在e/n的连分数展开中，k/d必然是某个渐近分数
- 我们可以枚举所有渐近分数，测试哪个是正确的k/d
实现步骤：
步骤1：连分数展开
def continued_fraction(n, d):
"""
计算n/d的连分数展开
例如：19/7 = 2 + 1/(1 + 1/(2 + 1/2))
返回：[2, 1, 2, 2]
"""
cf = []
while d:
q = n // d # 整数部分
cf.append(q)
n, d = d, n - q * d # 继续处理余数
return cf
步骤2：计算渐近分数
def convergents(cf):
"""
计算连分数的所有渐近分数
渐近分数是连分数的"部分和"，逐渐逼近真实值
"""
convs = []
n0, d0 = 1, 0
n1, d1 = cf[0], 1
convs.append((n1, d1))
for i in range(1, len(cf)):
# 递推公式
n2 = cf[i] * n1 + n0
d2 = cf[i] * d1 + d0
convs.append((n2, d2))
n0, d0 = n1, d1
n1, d1 = n2, d2
return convs
步骤3：整数平方根
def isqrt(n):
"""
计算整数平方根（避免浮点数溢出）
使用牛顿迭代法
"""
if n == 0:
return 0
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
步骤4：Wiener攻击主函数
def wiener_attack(key_path):
key = RSA.import_key(open(key_path).read())
n, e = key.n, key.e
print(f'对Key-3执行Wiener攻击...')
print(f' n: {n.bit_length()}位')
print(f' e: {e.bit_length()}位')
# 1. 计算e/n的连分数展开
cf = continued_fraction(e, n)
print(f' 连分数项数: {len(cf)}')
# 2. 计算所有渐近分数
convs = convergents(cf)
print(f' 渐近分数个数: {len(convs)}')
print(f' 开始测试每个渐近分数...')
# 3. 测试每个渐近分数k/d
for idx, (k, d) in enumerate(convs):
if k == 0:
continue
# 根据e×d = 1 + k×φ(n)，计算φ(n)
if (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
# 4. 从φ(n)恢复p和q
# 我们知道：
# p + q = n - φ(n) + 1
# p × q = n
# 这是一个二次方程，解为：
# p, q = [s ± sqrt(s² - 4n)] / 2
# 其中s = p + q
s = n - phi + 1
discriminant = s * s - 4 * n
if discriminant < 0:
continue
# 计算判别式的平方根
sqrt_d = isqrt(discriminant)
if sqrt_d * sqrt_d != discriminant:
continue
# 求解p和q
p = (s + sqrt_d) // 2
q = (s - sqrt_d) // 2
# 5. 验证
if p * q == n:
print(f' [成功] 在第{idx+1}个渐近分数找到解')
print(f' p: {p.bit_length()}位')
print(f' q: {q.bit_length()}位')
print(f' d: {d.bit_length()}位')
# 构造私钥
private_key = RSA.construct((n, e, d, p, q))
with open('key-3-private.pem', 'wb') as f:
f.write(private_key.export_key())
print(' 私钥已保存到 key-3-private.pem')
return True
return False
# 执行攻击
wiener_attack('key-3.pem')
运行结果：
对Key-3执行Wiener攻击...
n: 4096位
e: 4094位
连分数项数: 1804
渐近分数个数: 1804
开始测试每个渐近分数...
[成功] 在第298个渐近分数找到解
p: 2048位
q: 2048位
d: 128位 ← d确实很小！
私钥已保存到 key-3-private.pem
关键理解：
- 为什么要用连分数？ 连分数提供了有理数逼近的最优解，如果k/d是e/n的好逼近，它一定出现在渐近分数中
- 时间复杂度？ 连分数展开和渐近分数计算都是O(log n)，总体复杂度为O(log² n)，非常高效
- 成功条件？ d < n^(1/4) / 3。在本题中，d只有128位，远小于4096^(1/4) ≈ 2^32
攻击成功！ 在约30秒内破解了Key-3。
4.3 攻击三：Fermat分解（Key-1）
问题：如何破解剩余的密钥？
Key-0和Key-3已破解，但我们需要至少3个密钥。对于其他密钥，尝试Fermat分解。
Fermat分解原理：
如果两个素因子p和q比较接近，可以利用平方差公式快速分解。
设p > q，令：
- a = (p + q) / 2
- b = (p – q) / 2
则：
n = p × q = (a+b)(a-b) = a² - b²
因此：
b² = a² - n
算法思路：
- 从a = ⌈√n⌉开始（刚好大于√n）
- 递增a，计算b² = a² – n
- 检查b²是否是完全平方数
- 如果是，则p = a+b, q = a-b
为什么这个方法有效？
如果p和q很接近，那么a = (p+q)/2 ≈ √n，b = (p-q)/2很小，只需要很少的迭代就能找到。
实现代码：
def fermat_factor(n, max_iterations=1000000):
"""
Fermat因子分解
参数：
n: 要分解的数
max_iterations: 最大迭代次数
返回：
(p, q): 两个因子，如果失败则返回(None, None)
"""
# 从√n向上取整开始
a = isqrt(n) + 1
b2 = a * a - n
for i in range(max_iterations):
# 检查b²是否是完全平方数
b = isqrt(b2)
if b * b == b2:
# 找到了！计算p和q
p = a + b
q = a - b
# 验证
if p * q == n:
return p, q
# 继续下一个a
a += 1
b2 = a * a - n
# 进度提示（每10万次）
if i % 100000 == 0 and i > 0:
print(f' 已测试{i}次...')
return None, None
# 对所有未破解的密钥尝试Fermat分解
for i in [1, 2, 4, 5, 7, 8, 9]:
key = RSA.import_key(open(f'key-{i}.pem').read())
n = key.n
e = key.e
print(f'\\n尝试Fermat分解 key-{i}...')
p, q = fermat_factor(n)
if p and q:
print(f' [成功] 找到因子')
print(f' p: {p.bit_length()}位')
print(f' q: {q.bit_length()}位')
print(f' |p-q|: {abs(p-q).bit_length()}位')
# 生成私钥
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
private_key = RSA.construct((n, e, d, p, q))
with open(f'key-{i}-private.pem', 'wb') as f:
f.write(private_key.export_key())
print(f' 私钥已保存')
else:
print(f' [失败] 超出最大迭代次数')
运行结果：
尝试Fermat分解 key-1...
已测试100000次...
[成功] 找到因子
p: 2048位
q: 2048位
|p-q|: 2041位 ← p和q确实比较接近
私钥已保存
尝试Fermat分解 key-2...
已测试100000次...
已测试200000次...
[失败] 超出最大迭代次数
（其他密钥类似失败）
分析：
- Key-1成功破解！p和q只相差约2041位
- Key-2失败，说明p和q相差很大，需要其他方法
攻击成功！ Key-1被Fermat分解破解。
4.4 攻击四：小素数与Factordb（Key-2）
问题：Key-2用什么方法破解？
常规方法都失败了，考虑两种可能：
- 使用了小素数（容易被试除法找到）
- 这个模数已经被别人分解过（可查询在线数据库）
FactorDB介绍：
FactorDB (factordb.com) 是一个收录已知整数分解的数据库，包含：
- 研究者提交的分解结果
- 自动分解的数值
- CTF题目中使用过的数值
查询策略：
通过HTTP API查询：
import requests
import json
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse
def query_factordb(n):
"""
查询FactorDB数据库
API返回格式：
{
"id": "...",
"status": "FF", # FF表示完全分解
"factors": [
["因子1", 重数],
["因子2", 重数]
]
}
"""
print(' 正在查询FactorDB...')
url = f"http://factordb.com/api?query={n}"
try:
response = requests.get(url, timeout=30)
data = response.json()
return data
except Exception as e:
print(f' 查询失败: {e}')
return None
# 查询Key-2
key2 = RSA.import_key(open('key-2.pem').read())
n2, e2 = key2.n, key2.e
print('\\n尝试FactorDB查询 key-2...')
print(f' n的位长度: {n2.bit_length()}')
result = query_factordb(n2)
if result:
print(f' 查询状态: {result.get("status")}')
if result.get('status') == 'FF': # Fully Factored
print(' [成功] 找到完整因子分解！')
factors = result.get('factors', [])
print(f' 因子数量: {len(factors)}')
if len(factors) == 2:
# 提取两个因子
p = int(factors[0][0])
q = int(factors[1][0])
print(f'\\n 因子详情：')
print(f' p = {p}')
print(f' p的位长度: {p.bit_length()}位')
print(f' q的位长度: {q.bit_length()}位')
# 验证
if p * q == n2:
print(' [验证通过]')
# 生成私钥
phi2 = (p - 1) * (q - 1)
d2 = inverse(e2, phi2)
private_key2 = RSA.construct((n2, e2, d2, p, q))
with open('key-2-private.pem', 'wb') as f:
f.write(private_key2.export_key())
print(' 私钥已保存到 key-2-private.pem')
else:
print(' [验证失败] p×q ≠ n')
运行结果：
尝试FactorDB查询 key-2...
n的位长度: 4096
正在查询FactorDB...
查询状态: FF
[成功] 找到完整因子分解！
因子数量: 2
因子详情：
p = 2758599203
p的位长度: 32位 ← 极小的素数！
q的位长度: 4064位
[验证通过]
私钥已保存到 key-2-private.pem
震惊的发现：Key-2使用了32位小素数！
这是一个极其严重的安全漏洞：
- 小素数的危害：
- p只有2758599203，可以在几秒内通过试除法找到
- 即使q有4064位，整个密钥依然脆弱
- RSA的安全性取决于最弱的因子
- 为什么会出现这种情况？
- 密钥生成代码错误
- 使用了不当的随机数源
- 故意构造的CTF题目漏洞
- 如何检测小素数？
# 生成前100万个素数
primes = generate_primes(1000000)
# 试除法
for p in primes:
if n % p == 0:
print(f'找到小素数因子: {p}')
q = n // p
break
攻击成功！ 通过FactorDB找到了Key-2的极小素因子。
4.5 破解总结
至此，我们已经成功破解了4个RSA私钥：
| 密钥 | 攻击方法 | 关键漏洞 | 用时 | | — | — | — | — | | Key-0 | 共因子攻击 | 与Key-6共享2048位因子p | <1秒 | | Key-1 | Fermat分解 | p和q相差较小 | ~10秒 | | Key-2 | FactorDB/小素数 | p仅32位 | ~5秒 | | Key-3 | Wiener攻击 | e巨大导致d极小(128位) | ~30秒 |
关键洞察：
- 我们有Key-1, Key-2, Key-3三个私钥
- 根据秘密共享的门限，这足以恢复Message3
- 现在需要找到正确的密钥-密文配对
五、密文解密
5.1 解密函数实现
根据encrypt.py的加密逻辑，实现对应的解密函数：
from Crypto.Cipher import AES, PKCS1_OAEP
from Crypto.PublicKey import RSA
def decrypt(private_key, ciphertext):
"""
解密函数
参数：
private_key: RSA私钥对象
ciphertext: 密文字节串
返回：
明文字节串，失败则返回None
"""
# 检查密文长度（至少包含头部和IV）
if len(ciphertext) < 512 + 16:
return None
# 分离密文的三个部分
msg_header = ciphertext[:512] # RSA加密的AES密钥
msg_iv = ciphertext[512:512+16] # AES的IV
msg_body = ciphertext[512+16:] # AES加密的消息体
try:
# 步骤1：使用RSA私钥解密AES密钥
symmetric_key = PKCS1_OAEP.new(private_key).decrypt(msg_header)
except ValueError as e:
# RSA解密失败（密钥不匹配）
return None
# 步骤2：验证AES密钥长度
if len(symmetric_key) != 32:
return None
# 步骤3：使用AES密钥解密消息体
plaintext = AES.new(symmetric_key,
mode=AES.MODE_CFB,
IV=msg_iv).decrypt(msg_body)
return plaintext
代码解析：
- 为什么要检查长度？ 防止无效输入导致程序崩溃
- 为什么要捕获异常？ RSA解密失败会抛出ValueError
- 为什么要验证密钥长度？ 确保解密出的数据是有效的AES密钥
5.2 暴力测试所有组合
由于不知道哪个密钥对应哪个密文，需要暴力测试：
import os
# 读取所有私钥
private_keys = []
for i in range(10):
key_file = f'key-{i}-private.pem'
if os.path.exists(key_file):
try:
k = RSA.importKey(open(key_file, 'r').read())
private_keys.append((i, k))
print(f'加载私钥: key-{i}')
except:
pass
print(f'\\n共加载{len(private_keys)}个私钥\\n')
# 测试所有密钥-密文组合
print('=' * 60)
print('开始暴力测试所有密钥-密文组合')
print('=' * 60)
for i in range(1, 6):
ciphertext = open(f'ciphertext-{i}.bin', 'rb').read()
print(f'\\n测试 ciphertext-{i}.bin ({len(ciphertext)}字节)')
found = False
for key_idx, key in private_keys:
result = decrypt(key, ciphertext)
if result:
print(f' [匹配] key-{key_idx} 成功解密')
# 显示前100个字符
preview = result[:100].decode('utf-8', errors='ignore')
print(f' 预览: {preview}...')
# 保存完整解密结果
with open(f'decrypted-{i}.txt', 'w') as f:
f.write(result.decode('utf-8', errors='ignore'))
print(f' 已保存到 decrypted-{i}.txt')
found = True
break
if not found:
print(f' [失败] 无匹配的私钥')
运行结果：
加载私钥: key-0
加载私钥: key-1
加载私钥: key-2
加载私钥: key-3
加载私钥: key-6
共加载5个私钥
============================================================
开始暴力测试所有密钥-密文组合
============================================================
测试 ciphertext-1.bin (1139字节)
[匹配] key-2 成功解密
预览: Congratulations, you decrypted a ciphertext! One down, two to go :)
1-32a1cd9f414f14cff668587...
已保存到 decrypted-1.txt
测试 ciphertext-2.bin (1139字节)
[失败] 无匹配的私钥
测试 ciphertext-3.bin (1139字节)
[匹配] key-0 成功解密
预览: Congratulations, you decrypted a ciphertext! One down, two to go :)
3-17e568ddc3ed3e6fe330ca...
已保存到 decrypted-3.txt
测试 ciphertext-4.bin (1140字节)
[匹配] key-3 成功解密
预览: Congratulations, you decrypted a ciphertext! One down, two to go :)
4-4a87367d053c533fd99503...
已保存到 decrypted-4.txt
测试 ciphertext-5.bin (1139字节)
[匹配] key-1 成功解密
预览: Congratulations, you decrypted a ciphertext! One down, two to go :)
5-7d29041c468b680fcff93c...
已保存到 decrypted-5.txt
密钥-密文配对结果：
| 密钥 | 密文 | 攻击方法 | | — | — | — | | Key-1 | Ciphertext-5 | Fermat分解 | | Key-2 | Ciphertext-1 | 小素数/FactorDB | | Key-3 | Ciphertext-4 | Wiener攻击 |
重要发现：
- 成功解密了3个密文（1, 4, 5）
- 每个解密文件包含4行秘密分片
- 这足以恢复门限为2和3的秘密
5.3 解密文件结构分析
查看任一解密文件：
第1行: Congratulations, you decrypted a ciphertext! One down, two to go :)
第2行: 1-32a1cd9f414f14cff6685879444acbe41e5dba6574a072cace6e8d0eb338ad64...
第3行: 1-e0c113fa1ebea9318dd413bf28308707fd660a5d1417fbc7da72416c8baaa5bf...
第4行: 1-1b8b6c4e3145a96b1b0031f63521c8df58713c4d6d737039b0f1c0750e16e157...
第5行: 1-c332b8b93a914532a2dab045ea52b86d4d3950a990b5fc5e041dce9be1fd3912...
格式分析：
- 第1行：祝贺消息
- 第2-5行：Shamir秘密共享的分片
- 格式：
序号-十六进制字符串 - 序号对应密文编号
与generate-plaintexts.py对应：
- 第2行：Message2的一个分片（2-out-of-5门限）
- 第3行：Message3的一个分片（3-out-of-5门限）
- 第4行：Message4的一个分片（4-out-of-5门限）
- 第5行：Message5的一个分片（5-out-of-5门限）
六、Shamir秘密共享恢复
6.1 门限分析
我们有3个解密文件（1, 4, 5），因此每个秘密我们有3个分片：
| 秘密 | 门限 | 可用分片 | 能否恢复 | | — | — | — | — | | Message2 | 2-out-of-5 | 3个 | 可以（超过门限） | | Message3 | 3-out-of-5 | 3个 | 可以（达到门限） | | Message4 | 4-out-of-5 | 3个 | 不可以（少于门限） | | Message5 | 5-out-of-5 | 3个 | 不可以（少于门限） |
关键理解：
- 为什么3个分片能恢复2-out-of-5？
- 门限2表示”至少需要2个分片”
- 3个分片多于2个，完全足够
- 为什么3个分片恰好能恢复3-out-of-5？
- 门限3表示”至少需要3个分片”
- 我们刚好有3个，达到最低要求
- 为什么3个分片不能恢复4-out-of-5？
- 门限4表示”至少需要4个分片”
- 3个少于4个，无法恢复
数学原理：
- t-out-of-n方案使用t-1次多项式
- 需要t个点才能唯一确定t-1次多项式
- 少于t个点时，有无穷多个可能的多项式
6.2 秘密恢复实现
from secretsharing import PlaintextToHexSecretSharer as SS
# 读取3个解密文件
files = ["decrypted-1.txt", "decrypted-4.txt", "decrypted-5.txt"]
secrets = []
print('读取解密文件...')
for fn in files:
with open(fn, "r") as f:
lines = f.readlines()
# 跳过第一行祝贺消息
lines = lines[1:]
# 去除换行符和空行
lines = [line.strip() for line in lines if line.strip()]
secrets.append(lines)
print(f' {fn}: {len(lines)}个分片')
print(f'\\n共有{len(secrets[0])}个秘密需要恢复')
print('=' * 60)
# 恢复每个秘密
for i in range(len(secrets[0])):
# 收集当前秘密的所有分片
shares = [secrets[0][i], secrets[1][i], secrets[2][i]]
threshold = i + 2 # Message2门限为2，Message3门限为3，依此类推
print(f'\\nMessage{threshold}:')
print(f' 门限: {threshold}-out-of-5')
print(f' 可用分片: {len(shares)}个')
print(f' 分片示例: {shares[0][:50]}...')
if threshold <= len(shares):
try:
# 使用Shamir秘密共享库恢复秘密
recovered = SS.recover_secret(shares)
print(f' [成功] 秘密已恢复')
print(f' 内容: {recovered}')
print(f' 长度: {len(recovered)}字符')
except Exception as e:
print(f' [失败] 恢复出错: {e}')
else:
print(f' [失败] 分片数不足（需要{threshold}个，只有{len(shares)}个）')
print('\\n' + '=' * 60)
print('秘密恢复完成！')
运行结果：
读取解密文件...
decrypted-1.txt: 4个分片
decrypted-4.txt: 4个分片
decrypted-5.txt: 4个分片
共有4个秘密需要恢复
============================================================
Message2:
门限: 2-out-of-5
可用分片: 3个
分片示例: 1-32a1cd9f414f14cff6685879444acbe41e5dba6574a07...
[成功] 秘密已恢复
内容: And another one's down, and another one's down, and another one bites the dust!
长度: 86字符
Message3:
门限: 3-out-of-5
可用分片: 3个
分片示例: 1-e0c113fa1ebea9318dd413bf28308707fd660a5d1417f...
[成功] 秘密已恢复
内容: Three's the magic number! FLAG{ndQzjRpnSP60NgWET6jX}
长度: 63字符
Message4:
门限: 4-out-of-5
可用分片: 3个
分片示例: 1-1b8b6c4e3145a96b1b0031f63521c8df58713c4d6d73...
[失败] 分片数不足（需要4个，只有3个）
Message5:
门限: 5-out-of-5
可用分片: 3个
分片示例: 1-c332b8b93a914532a2dab045ea52b86d4d3950a990b5...
[失败] 分片数不足（需要5个，只有3个）
============================================================
秘密恢复完成！
成功获得Flag：FLAG{ndQzjRpnSP60NgWET6jX}
有趣的发现：
- Message2包含歌词：”And another one’s down…”（来自Queen的Another One Bites the Dust）
- Message3：”Three’s the magic number!”暗示了需要3个分片
- Flag格式：FLAG{随机字符串}
七、技术要点深度解析
7.1 四种RSA攻击技术对比
1. 共因子攻击（GCD Attack）
适用场景：
- 多个RSA模数共享公因子
- 密钥生成器存在随机性缺陷
数学原理：
如果 n1 = p × q1, n2 = p × q2
则 gcd(n1, n2) = p
优势：
- 时间复杂度O(log n)，极快
- 一次计算可破解两个密钥
- 不需要任何先验知识
防御方法：
- 使用密码学安全的随机数生成器（CSPRNG）
- 确保每个密钥使用独立的素数
- 定期审计密钥生成流程
真实案例：2012年研究人员扫描互联网上的RSA公钥，发现0.2%的密钥存在共因子问题，主要原因是嵌入式设备的随机数生成器在启动时熵不足。
2. Wiener攻击
适用场景：
- 私钥d相对较小（d < n^0.25 / 3）
- 公钥指数e异常大
数学原理：基于连分数理论，如果d很小，则k/d是e/n的良好有理逼近，必然出现在e/n的连分数展开的渐近分数中。
优势：
- 时间复杂度O(log² n)
- 不需要分解n
- 算法确定性强
局限性：
- 仅对d < n^0.25 / 3有效
- 实际应用中很少有人使用如此小的d
防御方法：
- 使用标准的公钥指数（如65537）
- 确保d足够大（至少n的一半长度）
- 使用PKCS#1标准的密钥生成
扩展：Boneh-Durfee攻击可以将范围扩展到d < n^0.292，但计算复杂度更高。
3. Fermat分解
适用场景：
- 两个素因子p和q比较接近
- |p – q| 相对于n较小
数学原理：利用平方差公式：n = a² – b²，其中a = (p+q)/2, b = (p-q)/2
优势：
- 当p和q接近时非常高效
- 实现简单
- 适合快速测试
局限性：
- 效率高度依赖|p-q|
- 如果p和q差距大，效率极低
防御方法：
- 确保p和q有足够大的差距
- 标准做法：p和q的位长度相同，但数值相差较大
- 使用强素数（strong primes）
优化技巧：可以结合Hart’s variant或其他优化算法加速搜索。
4. 小素数攻击
适用场景：
- RSA使用了小素因子
- 密钥生成存在严重缺陷
攻击方法：
- 试除法：测试n能否被前N个素数整除
- Pollard’s p-1算法：对特殊形式的素数有效
- FactorDB查询：利用已知分解数据库
优势：
- 对小素数极其快速
- FactorDB查询几乎瞬时完成
防御方法：
- 强制要求p和q都足够大（至少1024位）
- 在密钥生成时检查素数大小
- 使用标准库生成密钥，避免自己实现
真实案例：台湾公民电子证书系统在2003年被发现使用了包含小素因子的RSA密钥，导致大规模安全危机。
7.2 混合加密系统的设计哲学
为什么需要混合加密？
这是工程与数学的完美结合：
| 加密类型 | 优势 | 劣势 | 适用场景 | | — | — | — | — | | 对称加密(AES) | 速度快，适合大数据 | 密钥分发困难 | 数据加密 | | 非对称加密(RSA) | 可安全交换密钥 | 速度慢，数据量限制 | 密钥交换 |
混合加密工作流程：
发送方：
1. 生成随机AES密钥K
2. 用AES密钥K加密消息M → C_data
3. 用RSA公钥加密AES密钥K → C_key
4. 发送 [C_key || C_data]
接收方：
1. 用RSA私钥解密C_key → K
2. 用AES密钥K解密C_data → M
安全性分析：
- 机密性保护：
- 即使攻击者截获密文，没有RSA私钥无法获得AES密钥
- 没有AES密钥无法解密数据
- 性能优势：
- RSA只需加密32字节（AES密钥）
- 大量数据由高效的AES处理
- 弱点：
- 整个系统的安全性等于最弱环节
- RSA漏洞会导致整个系统沦陷
- 需要正确的填充方案（OAEP）防止选择密文攻击
实际应用：
- TLS/SSL协议
- PGP/GPG加密邮件
- SSH密钥交换
- VPN加密隧道
7.3 Shamir秘密共享的优雅数学
核心思想：
一个t-1次多项式由t个点唯一确定。
具体构造（t-out-of-n方案）：
- 秘密编码： 将秘密S作为多项式的常数项
- 构造多项式：
f(x) = S + a₁x + a₂x² + ... + a_{t-1}x^{t-1}
其中a₁, …, a_{t-1}是随机系数
- 生成分片： 计算n个点
分片1: (1, f(1))
分片2: (2, f(2))
...
分片n: (n, f(n))
- 秘密恢复： 任意t个分片(x_i, y_i)，使用拉格朗日插值：
f(x) = Σ y_i × L_i(x)
其中 L_i(x) = Π_{j≠i} (x - x_j) / (x_i - x_j)
然后计算f(0) = S
完美安全性证明：
对于少于t个分片，有无穷多个可能的多项式通过这些点，因此无法获得关于S的任何信息（信息论安全）。
实际应用：
- 密钥备份：
- 将主密钥分成5片，分别保存在不同地点
- 任意3片可恢复密钥
- 防止单点故障
- 多方签名：
- 公司重要交易需要3/5董事签字
- 每个董事持有一个分片
- 至少3人同意才能执行
- 分布式密钥管理：
- 密钥管理系统(KMS)
- 云存储加密
- 区块链钱包
7.4 密码学安全的核心原则
通过这道题，我们学到了密码学系统的关键安全原则：
1. 最小权限原则
- 只给予完成任务所需的最小权限
- 在秘密共享中体现为门限设置
2. 深度防御
- 不依赖单一安全机制
- 混合加密结合了RSA和AES的优势
3. 默认安全
- 使用经过验证的标准算法
- 不要自己实现密码学原语
4. 透明性原则（Kerckhoffs原则）
- 算法可以公开，安全性只依赖于密钥
- 本题提供了完整的加密代码，但这不影响安全性
5. 最弱环节定律
- 整个系统的安全性等于最弱的部分
- 即使AES-256无法破解，RSA的弱点也会导致全盘皆输
八、防御建议与最佳实践
8.1 RSA密钥生成的正确方法
使用标准库：
from Crypto.PublicKey import RSA
# 正确的方式
key = RSA.generate(4096) # 使用4096位
private_key = key.export_key()
public_key = key.publickey().export_key()
标准库会自动处理：
- 生成足够大的随机素数p和q
- 确保p和q有足够的差距
- 使用标准的公钥指数e=65537
- 验证生成的密钥满足安全要求
不要做的事：
- 不要自己生成素数
- 不要使用小素数
- 不要重复使用素数
- 不要使用极大或极小的e值
8.2 密钥管理最佳实践
生成阶段：
- 使用密码学安全的随机数生成器（/dev/urandom, CryptGenRandom）
- 确保系统有足够的熵
- 生成后立即测试密钥
存储阶段：
- 私钥必须加密存储
- 使用硬件安全模块（HSM）存储关键密钥
- 实施严格的访问控制
使用阶段：
- 定期轮换密钥
- 记录所有密钥使用
- 使用密钥派生函数（KDF）而非直接使用主密钥
销毁阶段：
- 安全删除（多次覆写）
- 记录销毁时间和原因
- 更新所有使用该密钥的系统
8.3 代码审查检查清单
在审查密码学代码时，检查以下方面：
密钥生成：
- [ ] 是否使用标准库生成密钥？
- [ ] 密钥长度是否足够（RSA ≥ 2048位）？
- [ ] 是否检查素数大小？
- [ ] 是否使用CSPRNG？
加密实现：
- [ ] 是否使用安全的填充方案（OAEP, PSS）？
- [ ] IV是否每次都随机生成？
- [ ] 是否正确处理异常？
- [ ] 是否有重放攻击防护？
密钥管理：
- [ ] 私钥是否加密存储？
- [ ] 是否有密钥轮换机制？
- [ ] 是否记录密钥使用日志？
- [ ] 是否有密钥恢复机制？
九、解题流程回顾与思维模式
9.1 系统化的分析流程
这道题展示了密码学题目的标准分析流程：
1. 信息收集
↓
2. 算法分析（理解加密方案）
↓
3. 漏洞识别（寻找弱点）
↓
4. 攻击选择（选择合适的攻击方法）
↓
5. 工具准备（编写或使用工具）
↓
6. 执行攻击（实施攻击并验证）
↓
7. 数据处理（解密和秘密恢复）
↓
8. 验证结果（确认flag）
9.2 关键决策点
决策1：先分析算法还是先尝试攻击？
- 答案：先分析算法
- 原因：理解系统才能找到弱点
决策2：如何选择攻击方法？
- 基于漏洞特征选择
- 从简单到复杂尝试
- 优先考虑已知的常见攻击
决策3：遇到失败如何处理？
- 验证输入是否正确
- 检查代码逻辑
- 尝试其他方法
- 查阅文档和资料
9.3 学习建议
对于初学者：
- 先理解基础概念（RSA原理、AES、秘密共享）
- 手动实现简单的攻击（如共因子攻击）
- 逐步增加难度
- 多做CTF题目实践
对于进阶学习者：
- 深入研究数学原理
- 阅读学术论文
- 研究真实世界的密码学漏洞
- 参与开源密码学项目
推荐资源：
- 书籍：《应用密码学》（Applied Cryptography）
- 课程：Coursera的密码学课程
- 实践：CryptoHack, CTFtime
- 工具：RsaCtfTool, SageMath
十、总结
10.1 题目设计的巧妙之处
这道RSA-Buffet题目设计精妙，体现在：
- 多样性： 涵盖了4种不同的RSA攻击技术
- 层次性： 从简单（共因子）到复杂（Wiener）
- 综合性： 结合了RSA、AES、秘密共享
- 实用性： 所有漏洞都有真实案例
- 教育性： 循序渐进，适合学习
10.2 核心收获
通过完整分析这道题，我们学到了：
技术层面：
- 四种RSA攻击技术的原理和实现
- 混合加密系统的工作机制
- Shamir秘密共享的数学基础
- 密码学工具的使用方法
思维层面：
- 系统化分析复杂问题的方法
- 从弱点出发而非暴力破解
- 理论与实践相结合
- 安全设计的核心原则
实践层面：
- 代码实现和调试能力
- 工具使用和脚本编写
- 问题定位和解决
- 文档阅读和学习
10.3 更广阔的视野
密码学不仅是数学和计算机科学，更是：
- 工程实践： 如何在真实系统中安全实现
- 风险管理： 平衡安全性、性能、成本
- 持续进化： 随着攻击技术发展而更新
- 责任意识： 密码学关系到隐私和安全
最后的提醒：
这道题展示的所有攻击技术都是为了学习和提高安全意识。在实际应用中：
- 始终使用标准库和成熟的实现
- 遵循最新的安全标准和最佳实践
- 定期审计和更新密码学系统
- 保持对新攻击技术的关注
密码学是一个迷人的领域，它将优雅的数学理论与严峻的安全挑战完美结合。希望通过这篇详细的技术解析，你不仅学会了如何解决这道题，更重要的是掌握了分析和解决密码学问题的思维方式。
继续探索，持续学习，在密码学的道路上越走越远！
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全《RSA-Buffet：一道综合性RSA密码学题目的完整技术解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论