文章总结： 本文详解ASISCTF题目，针对三素数RSA与ElGamal混合加密方案，利用私钥d过小的漏洞实施Wiener攻击。文章推导了多素数环境下的数学原理，通过连分数及线性组合穷举恢复私钥并解密获取Flag，强调了密钥生成顺序不当引发的严重风险。 综合评分： 90 文章分类： CTF,漏洞分析,实战经验
CTF Crypto 题解：多素数 RSA 上的 Wiener 攻击
原创
破镜安全 破镜安全
破镜安全
2026年3月1日 14:20 四川
CTF Crypto 题解：多素数 RSA 上的 Wiener 攻击
题目信息
- 比赛：ASIS CTF
- 题目名称：Gracias
- 类别：Crypto（密码学）
- 附件：gracias.py（加密程序源码）、enc_pubkey.txt（公钥与密文）
一、读懂题目：附件里藏着什么
拿到题目后，首先阅读两个附件。
enc_pubkey.txt 给出了公钥四元组和密文对：
pubkey = (n, e, a, g)
c = (c1, c2)
具体数值（已截短展示）：
n = 16968...61567 （1536 位）
e = 81416...97451 （1535 位）
a = 17101...77523 （1024 位）
g = 96969...64722 （1024 位）
c1 = 15697...49773 （1536 位）
c2 = 13953...39827 （1024 位）
gracias.py 是加密程序的完整源码：
def make_pubpri(nbit):
p, q, r = [ getPrime(nbit) for _ in xrange(3)]
n = p * q * r
phi = (p-1)*(q-1)*(r-1)
l = min([p, q, r])
d = getPrime(1 << 8)
e = inverse(d, phi)
a = gensafeprime.generate(2*nbit)
while True:
g = getRandomRange(2, a)
if pow(g, 2, a) != 1 and pow(g, a/2, a) != 1:
break
return (n, e, a, g), (n, d, a, g)
def encrypt(m, pub):
n, e, a, g = pub
k = getRandomRange(2, a)
K = pow(g, k, a)
c1, c2 = pow(k, e, n), (m * K) % a
return c1, c2
nbit = 512
pubkey, privkey = make_pubpri(nbit)
m = bytes_to_long(FLAG)
c = encrypt(m, pubkey)
有了源码，加密过程完全透明，接下来逐步拆解。
二、理解加密方案：两层结构
2.1 密钥生成（make_pubpri）
密钥生成分为两个独立部分：RSA 部分和 ElGamal 部分。
RSA 部分：
p, q, r = [ getPrime(nbit) for _ in xrange(3)] # nbit = 512
n = p * q * r
phi = (p-1)*(q-1)*(r-1)
d = getPrime(1 << 8)
e = inverse(d, phi)
这里生成了三个 512 位素数 p、q、r，模数 n = p * q * r，共 1536 位。
这是三素数 RSA，与标准 RSA（两素数）的结构相同，只是多一个因子。RSA 的核心关系依然成立：
e * d ≡ 1 (mod phi(n))
其中 phi(n) = (p-1)(q-1)(r-1) 是欧拉函数。
值得注意的是密钥生成顺序：程序先随机选取了一个 256 位素数 d（d = getPrime(1 << 8)，其中 1 << 8 = 256），再由 d 推算出 e。这与标准做法（先固定 e=65537 再算 d）相反，导致 d 极小。
ElGamal 部分：
a = gensafeprime.generate(2*nbit) # 1024 位安全素数
while True:
g = getRandomRange(2, a)
if pow(g, 2, a) != 1 and pow(g, a/2, a) != 1:
break
a 是一个 1024 位的安全素数（safe prime），即 a = 2p’ + 1，其中 p’ 也是素数。g 满足两个条件：
g^2 mod a != 1：g 不是 ±1g^((a-1)/2) mod a != 1：g 不是二次剩余，即不在阶为 2 的子群中
这两个条件保证 g 是 a 的原根（primitive root），即 g 生成模 a 意义下的完整乘法群，群阶为 phi(a) = a-1 = 2p’。
公钥为 (n, e, a, g)，私钥为 (n, d, a, g)。
2.2 加密过程（encrypt）
k = getRandomRange(2, a) # 随机临时密钥
K = pow(g, k, a) # K = g^k mod a
c1 = pow(k, e, n) # c1 = k^e mod n （RSA 加密 k）
c2 = (m * K) % a # c2 = m * K mod a（乘法掩盖）
加密分两步：
第一步：用 RSA 公钥 (n, e) 加密随机临时密钥 k，得到 c1。
第二步：计算 K = g^k mod a，再用 K 与消息 m 相乘后取模，得到 c2 = m * K mod a。
这是一个混合加密方案（Hybrid Encryption）：RSA 负责安全地传递会话密钥 k，ElGamal 风格的乘法掩盖负责隐藏消息 m。
2.3 正确的解密流程
如果知道私钥 d，解密分三步：
第一步：k = c1^d mod n （RSA 解密，还原临时密钥）
第二步：K = g^k mod a （重建共享密钥）
第三步：m = c2 * K^(-1) mod a （乘法逆元，还原消息）
第三步的原理：c2 = m * K mod a，所以 m = c2 / K mod a = c2 * K^(-1) mod a，其中 K^(-1) 是 K 在模 a 意义下的乘法逆元。
三、发现漏洞：私钥 d 严重过小
仔细观察密钥生成的这一行：
d = getPrime(1 << 8)
1 << 8 = 256，即 d 是一个随机的 256 位素数。
而 n 是三个 512 位素数的乘积，共约 1536 位。
对比一下比特长度：
n 的比特长度：1536 位
d 的比特长度：256 位
比值：d 约为 n^(1/6)
这个比例是极度危险的。RSA 的安全性假设之一是私钥指数 d 足够大。1990 年，Michael Wiener 证明：当 d < N^(1/4) / 3 时，可以从公钥 (N, e) 高效恢复 d，无需分解 N。
本题 n ≈ 2^1536，n^(1/4) ≈ 2^384，而 d ≈ 2^256，256 远小于 384，Wiener 攻击的条件宽裕地满足。
四、Wiener 攻击：从数学到实现
4.1 连分数的基本概念
在介绍攻击之前，先理解连分数（Continued Fraction）。
任意实数 x 可以写成如下形式：
x = a_0 + 1/(a_1 + 1/(a_2 + 1/(a_3 + ...)))
对于有理数，这个过程是有限的，可以通过辗转相除法计算：
x = a_0 + 余数_0/分母
a_0 = floor(x)
余数_0 = x - a_0
然后对 1/余数_0 重复上述步骤...
连分数展开的每一步截断，得到的分数 h_i/k_i 称为渐近分数（convergent）。渐近分数具有一个重要性质：它们是对原始数的”最佳有理近似”，即在分母不超过 k_i 的所有分数中，h_i/k_i 最接近 x。
4.2 Wiener 攻击的数学推导
由 RSA 基本关系：
e * d = 1 + k * phi(n) （k 是某个正整数）
两边同除以 n * d：
e/n = k/d + (1 - k*(n - phi(n))) / (n*d)
右边第二项是一个很小的误差。对于标准两素数 RSA（n = p*q）：
n - phi(n) = p + q - 1 ≈ 2*sqrt(n)
误差项约为：
|e/n - k/d| ≈ 2k / (d * sqrt(n))
由 Legendre 定理，当某个分数 p/q 满足 |x – p/q| < 1/(2*q^2) 时，p/q 一定是 x 连分数展开的某个渐近分数。将上面的误差代入这个条件：
2k / (d * sqrt(n)) < 1/(2*d^2)
=> d < n^(1/4) / (4k)^(1/2) ≈ n^(1/4) / 3
这就是著名的 Wiener 边界：d < n^(1/4) / 3 时，k/d 必然出现在 e/n 的连分数展开中，攻击者遍历所有渐近分数即可找到 d。
4.3 三素数情形的推广
本题 n = p * q * r，phi(n) = (p-1)(q-1)(r-1)，展开计算：
n - phi(n) = pqr - (p-1)(q-1)(r-1)
= pq + pr + qr - (p + q + r) + 1
≈ 3 * n^(2/3) （因为 p, q, r 各约为 n^(1/3)）
这比两素数情况下的 2sqrt(n) = 2n^(1/2) 大得多（2/3 > 1/2），误差项变大：
|e/n - k/d| ≈ 3k / (d * n^(1/3))
对应的有效边界变为 d < n^(1/3) / (某常数)。
本题 n^(1/3) ≈ 2^512，而 d ≈ 2^256，条件依然充分满足。
然而由于误差增大，d 未必精确等于某个渐近分数的分母 k_i，而是可能表示为相邻两个渐近分数分母的线性组合：
d = alpha * k_{i-1} + beta * k_i
其中 alpha 和 beta 是很小的正整数。解题脚本的 multi 模式正是利用这一点，在遍历渐近分数的同时，对 alpha 和 beta 进行小范围穷举。
4.4 渐近分数的计算：next_frac 函数
def next_frac(self):
hi_1, hi_2 = 1, 0
ki_1, ki_2 = 0, 1
a, b = self.e, self.N
r = 1
while r:
p, r = divmod(a, b) # a = p*b + r（辗转相除）
hi = p * hi_1 + hi_2 # 渐近分数分子递推
ki = p * ki_1 + ki_2 # 渐近分数分母递推
hi_1, hi_2 = hi, hi_1
ki_1, ki_2 = ki, ki_1
a, b = b, r
yield (hi, ki) # 逐步产出渐近分数 (h_i, k_i)
这个函数对 e/N 做辗转相除，用递推公式 h_i = a_i * h_{i-1} + h_{i-2}、k_i = a_i * k_{i-1} + k_{i-2} 逐步生成渐近分数序列，每次 yield 一个 (h_i, k_i) 对。
4.5 多素数穷举：multi 函数
def multi(self, rate):
N, e = self.N, self.e
pt = getRandomRange(2, N - 1) # 随机选取测试明文
ct = pow(pt, e, N) # 计算对应密文
ki_1, ki_2 = 0, 1
for frac in self.next_frac():
hi, ki = frac
ki_1, ki_2 = ki, ki_1 # 维护相邻两个渐近分数分母
if hi == 0:
continue
_ki_1, _ki_2 = ki_1, ki_2
check = lambda rs: pow(ct, int(rs[:rate], 2) * _ki_1
+ int(rs[rate:], 2) * _ki_2, N) == pt
rs = mbruteforce(check, '01', 2 * rate, method='fixed')
if rs:
return int(rs[:rate], 2) * ki_1 + int(rs[rate:], 2) * ki_2
return None
逐步解析：
第一步，构造验证对（pt, ct）：
随机取一个明文 pt，计算 ct = pt^e mod N。这对数据的用途是：若某个候选 d’ 满足 ct^(d’) ≡ pt (mod N)，则 d’ 就是正确的私钥 d。这个验证以压倒性的概率成立，因为 RSA 加解密的正确性保证了只有真正的 d 能通过验证。
第二步，遍历渐近分数，维护相邻分母：
ki_1 和 ki_2 始终保存最新的两个渐近分数分母。
第三步，穷举线性组合：
mbruteforce 枚举所有长度为 2*rate = 8 的二进制串（共 2^8 = 256 种）。每条二进制串 rs 被分为两半：
- 前 4 位
rs[:4]转为整数，作为 alpha（范围 0~15） - 后 4 位
rs[4:]转为整数，作为 beta（范围 0~15）
构造候选 d：
d_candidate = alpha * ki_1 + beta * ki_2
第四步，验证候选 d：
用 check 函数验证 pow(ct, d_candidate, N) == pt。一旦通过，返回该 d_candidate 作为最终结果。
整个过程的搜索空间：（渐近分数数量，量级约为 log(N)） × 256 种线性组合，总计数百万次模幂运算，在现代计算机上数分钟内可以完成。
五、解密：还原 flag
找到 d 后，解密过程分三步，完整代码如下：
def solve():
n = 1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567
e = 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451
a = 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523
g = 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722
c1 = 1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773
c2 = 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827
wiener = Wiener(n, e, 1) # mode=1 启用多素数模式
d = wiener.attack() # Wiener 攻击恢复私钥 d
k = pow(c1, d, n) # RSA 解密：还原临时密钥 k
K = pow(g, k, a) # 重建共享密钥：K = g^k mod a
m = c2 * inverse(K, a) % a # 消除掩盖：m = c2 * K^(-1) mod a
return long_to_bytes(m)
实际运行输出：
[*] Running Wiener attack (multi-prime mode)...
[+] Found d = 100556095937036905102538523179832446199526507742826168666218687736467897968451
d bit length: 256
[*] Decrypting...
[+] Flag: ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}
攻击成功找到了 256 位的私钥 d，随后完整还原出 flag。
六、为什么这个加密方案不安全：根本原因
6.1 错误的密钥生成顺序
标准 RSA 密钥生成应当：
- 先固定公钥指数 e（通常取 e = 65537）
- 再计算 d = e^(-1) mod phi(n)
此时 d 的大小由 phi(n) 决定，约为 n 的量级，足够大。
本题反其道而行之：先选 d（256 位），再算 e。虽然数学上完全合法（e 和 d 的关系是对称的），但导致 d 极小，直接触发 Wiener 攻击。
6.2 三素数 RSA 不能弥补这一缺陷
三素数 RSA 相比两素数 RSA 的主要优势在于：分解 n = pqr 在计算上更难，且在已知部分私钥的情况下更难完全破解。但这些优势的前提是 d 足够大。Wiener 攻击完全绕过了分解 n 这一步骤，只需利用 e/n 的连分数展开恢复 d，三素数的结构不提供任何额外保护。
6.3 安全素数和原根的选取是否有帮助
a 被选为安全素数，g 被选为 a 的原根，这使得模 a 的离散对数问题（DLP）在理论上是困难的。但在这道题中，攻击者根本不需要求解离散对数——通过 Wiener 攻击恢复 d 之后，直接用 RSA 解密 c1 即可得到 k，进而计算 K = g^k mod a。DLP 的困难性在已知 k 的情况下毫无意义。
七、关键知识点梳理
RSA 基本原理
RSA 加密：c = m^e mod n RSA 解密：m = c^d mod n 关键关系：e * d ≡ 1 (mod phi(n))
phi(n) 对于三素数 RSA 的计算：phi(pqr) = (p-1)(q-1)(r-1)
连分数与渐近分数
- 连分数展开：通过辗转相除，将有理数表示为整数序列
- 渐近分数（convergent）：连分数每一步截断得到的最优有理近似
- Legendre 定理：若 |x – p/q| < 1/(2*q^2)，则 p/q 是 x 的某个渐近分数
Wiener 攻击的核心思路
由于 e*d ≡ 1 (mod phi(n))，分数 k/d 近似等于 e/n（其中 k 是辅助整数）。当 d 很小时，k/d 出现在 e/n 的连分数展开的渐近分数中，从而可以恢复 d。
Wiener 边界（两素数）：d < N^(1/4) / 3 Wiener 边界（三素数）：d < N^(1/3) / 常数
混合加密结构
本题使用 RSA 加密会话密钥、ElGamal 风格乘法掩盖加密消息的混合方案，属于教科书级别的密码协议构造，思路本身是合理的，漏洞完全源于参数选取错误。
八、防御建议
- 不要先选 d 再推 e：正确做法是先固定 e（推荐 65537），再计算 d = e^(-1) mod phi(n)，让 d 自然地取到正确大小。
- 验证 d 的比特长度：在密钥生成后检查 d 的比特长度，若 d.bit_length() 远小于 n.bit_length() / 2，应立即重新生成密钥。
- 使用成熟的密码库：OpenSSL、Python cryptography 库等经过审计的实现不会产生此类参数错误，不要从零手工实现 RSA 密钥生成。
九、完整解题脚本
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from gmpy2 import is_square, isqrt, mpz
from Crypto.Util.number import long_to_bytes, getRandomRange, inverse
from pwnlib.util.iters import mbruteforce
class Wiener(object):
def __init__(self, N, e, mode):
self.N = N
self.e = e
self.mode = mode
def next_frac(self):
# 对 e/N 做连分数展开，逐步产出渐近分数 (h_i, k_i)
hi_1, hi_2 = 1, 0
ki_1, ki_2 = 0, 1
a, b = self.e, self.N
r = 1
while r:
p, r = divmod(a, b)
hi = p * hi_1 + hi_2
ki = p * ki_1 + ki_2
hi_1, hi_2 = hi, hi_1
ki_1, ki_2 = ki, ki_1
a, b = b, r
yield (hi, ki)
def multi(self, rate):
N, e = self.N, self.e
# 构造验证对：ct = pt^e mod N，用于验证候选 d
pt = getRandomRange(2, N - 1)
ct = pow(pt, e, N)
ki_1, ki_2 = 0, 1
for frac in self.next_frac():
hi, ki = frac
ki_1, ki_2 = ki, ki_1 # 维护相邻两个渐近分数分母
if hi == 0:
continue
_ki_1, _ki_2 = ki_1, ki_2
# 穷举 alpha 和 beta（各 4 位，共 256 种组合）
check = lambda rs: pow(ct,
int(rs[:rate], 2) * _ki_1 + int(rs[rate:], 2) * _ki_2,
N) == pt
rs = mbruteforce(check, '01', 2 * rate, method='fixed')
if rs:
return int(rs[:rate], 2) * ki_1 + int(rs[rate:], 2) * ki_2
return None
def attack(self):
if self.mode:
return self.multi(4) # 多素数模式
else:
return self.two() # 两素数模式
def solve():
n = mpz(1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567)
e = mpz(814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451)
a = mpz(171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523)
g = mpz(96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722)
c1 = mpz(1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773)
c2 = mpz(139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827)
print('[*] 正在执行 Wiener 攻击（多素数模式）...')
wiener = Wiener(n, e, 1)
d = wiener.attack()
print(f'[+] 恢复私钥 d = {d}')
print(f' d 比特长度：{int(d).bit_length()} 位')
k = pow(c1, d, n)
K = pow(g, k, a)
m = c2 * inverse(K, a) % a
flag = long_to_bytes(m)
print(f'[+] Flag：{flag.decode()}')
if __name__ == '__main__':
solve()
运行结果：
[*] 正在执行 Wiener 攻击（多素数模式）...
[+] 恢复私钥 d = 100556095937036905102538523179832446199526507742826168666218687736467897968451
d 比特长度：256 位
[+] Flag：ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}
十、总结
这道题的加密方案本身设计思路合理——用 RSA 加密会话密钥、ElGamal 乘法掩盖加密消息是成熟的混合加密模式，使用安全素数和原根也是正确选择。然而一行代码的失误（d = getPrime(256)）让整个方案土崩瓦解：私钥 d 仅有 256 位，而模数 n 有 1536 位，Wiener 攻击的条件被极度宽松地满足。
攻击的完整链路是：利用 e/n 的连分数展开，在相邻渐近分数分母的线性组合中穷举出 d，再依次完成 RSA 解密和 ElGamal 解密，还原消息。全过程无需分解 1536 位的模数。
flag：ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}
这个 flag 本身就是一句话的总结：在多素数 RSA 上实施 Wiener 攻击是可行的。
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全 破镜安全《CTF Crypto 题解：多素数 RSA 上的 Wiener 攻击》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论