文章总结： 本文详解ASISCTF密码题Gracias，该题结合三素数RSA与ElGamal加密。核心漏洞在于使用了过小的私钥d，使得d约等于n的0.167次方。作者通过将Boneh-Durfee攻击适配至三素数RSA场景，利用格基规约算法成功恢复私钥，进而解密获取Flag。文章涵盖了漏洞分析、攻击原理、算法适配及完整的解题脚本，展示了针对小私钥RSA的攻击技术。 综合评分： 95 文章分类： CTF,漏洞分析,代码审计
ASIS CTF Finals 2017 – Gracias 密码学挑战题详解
原创
破镜安全
破镜安全
2026年1月9日 08:00 四川
ASIS CTF Finals 2017 – Gracias 密码学挑战题详解
一、题目背景
本题是ASIS CTF Finals 2017中的一道密码学挑战题,名为”Gracias”。题目实现了一个基于多素数RSA的混合加密系统,结合了RSA加密和ElGamal加密的特点。本文将从零开始,详细分析题目的加密机制、漏洞所在,以及完整的攻击过程。
二、题目文件分析
题目提供了一个压缩包,解压后包含以下文件:
2.1 加密源代码 (gracias.py)
首先,我们来看题目提供的加密算法源代码:
#!/usr/bin/python
from gmpy import *
from Crypto.Util.number import *
import gensafeprime
from flag import FLAG
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)
print 'c =', c
print 'pubkey =', pubkey
2.2 密文和公钥 (enc_pubkey.txt)
题目还提供了加密后的密文和公钥:
c = (1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773, 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827)
pubkey = (n, e, a, g)
其中:
- n = 1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567
- e = 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451
- a = 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523
- g = 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722
三、加密算法深度分析
3.1 密钥生成过程
让我们逐行分析密钥生成函数 make_pubpri:
p, q, r = [ getPrime(nbit) for _ in xrange(3)]
n = p * q * r
这里生成了三个512位的素数p、q、r,然后计算模数 n = p * q * r。这是一个三素数RSA系统,不同于传统的两素数RSA。
phi = (p-1)*(q-1)*(r-1)
计算欧拉函数 φ(n)。对于三素数RSA,欧拉函数为 φ(n) = (p-1)(q-1)(r-1)。
d = getPrime(1 << 8)
e = inverse(d, phi)
这是关键的漏洞所在:
1 << 8等于 256,表示私钥d是一个256位的素数- 然后计算 e = d^(-1) mod φ(n),即e是d的模逆元
这种做法与标准RSA完全相反。标准RSA是先选择一个小的公钥e(如65537),然后计算大的私钥d。而这里先选择了一个非常小的私钥d,导致公钥e变得非常大。
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
这部分生成ElGamal加密所需的参数:
- a是一个1024位的安全素数
- g是a的一个生成元
3.2 加密过程分析
加密函数 encrypt 实现了一个混合加密方案:
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
加密过程分为以下步骤:
步骤1: 随机生成一个数k,范围在[2, a)之间
步骤2: 计算共享密钥 K = g^k mod a (这是ElGamal加密的核心)
步骤3: 生成两个密文:
- c1 = k^e mod n (使用RSA加密随机数k)
- c2 = m * K mod a (使用共享密钥K加密明文m)
这是一个典型的混合加密方案:RSA用于加密会话密钥k,ElGamal用于加密实际消息。
四、漏洞识别与分析
4.1 小私钥问题
通过分析密钥生成代码,我们发现了一个严重的安全漏洞:
d = getPrime(1 << 8) # d是一个256位的素数
让我们计算一下私钥d相对于模数n的大小:
- 模数n由三个512位素数相乘,约为 512 * 3 = 1536位
- 私钥d只有256位
- 因此 d ≈ n^(256/1536) ≈ n^0.167
4.2 为什么小私钥是危险的
在RSA加密系统中,私钥d和公钥e满足以下关系:
e * d ≡ 1 (mod φ(n))
这意味着存在一个整数k,使得:
e * d = k * φ(n) + 1
当d很小时,这个等式可以转化为一个多项式小根问题,使用格基规约算法(LLL)可以求解。针对小私钥RSA的攻击主要有两种:
- Wiener攻击: 适用于 d < n^0.25
- Boneh-Durfee攻击: 适用于 d < n^0.292
本题中 d ≈ n^0.167,完全在Boneh-Durfee攻击的范围内。
五、Boneh-Durfee攻击原理
5.1 标准RSA的Boneh-Durfee攻击
Boneh-Durfee攻击是一种针对小私钥RSA的强大攻击方法。其核心思想是将RSA问题转化为多项式小根问题。
对于标准的两素数RSA (n = p * q):
- 欧拉函数: φ(n) = (p-1)(q-1) = n – (p+q) + 1
- 设 A = (n+1)/2,构造多项式: f(x,y) = x(A+y) + 1
- 该多项式在模e下有小根 (x,y) = (k, -(p+q-1)/2)
- 使用Coppersmith方法和LLL算法求解小根
5.2 适配到三素数RSA
本题使用的是三素数RSA (n = p * q * r),需要对攻击方法进行调整:
对于三素数RSA:
- φ(n) = (p-1)(q-1)(r-1)
- 展开: φ(n) = pqr – (pq+pr+qr) + (p+q+r) – 1
- 即: φ(n) = n – (pq+pr+qr) + (p+q+r) – 1
因此,我们需要修改多项式构造:
- 设 A = (n-1)/2
- 设 y = -(pq+pr+qr) + (p+q+r)
- 多项式: f(x,y) = x(A+y) + 1
关键的修改在于y的界限:
- 对于两素数RSA: y ≈ n^0.5
- 对于三素数RSA: y ≈ n^(2/3)
六、攻击实施
6.1 修改Boneh-Durfee攻击脚本
我们使用David Wong实现的Boneh-Durfee攻击脚本作为基础,针对三素数RSA进行修改。关键修改在boneh_durfee函数中:
def boneh_durfee(n, e):
delta = RR(0.167) # d ~ n^0.167
m = 5
t = round((1-2*delta) * m)
X = ZZ(2*floor(n^delta))
# 关键修改:将Y的界限设为n^(2/3)
Y = ZZ(floor(n^(2/3)))
P.<x,y> = PolynomialRing(ZZ)
A = ZZ((n-1)/2)
pol = 1 + x * (A + y)
solx, soly = boneh_durfee_small_roots(pol, e, m, t, X, Y)
if solx > 0:
return int(pol(solx, soly) / e)
return 0
参数说明:
- delta = 0.167: 表示 d ≈ n^0.167
- m = 5: 格的维度参数
- t: 控制y方向的多项式数量
- X = 2 * n^delta: x的上界
- Y = n^(2/3): y的上界(这是针对三素数RSA的关键修改)
6.2 运行攻击脚本
将题目给出的n和e代入脚本,运行攻击:
sage boneh_durfee.sage
攻击成功后,输出结果:
96495049525709737646237784043989949922984947124527440290534285859764556084120
-213794805403874041582980303133544562301251683427479249295482840787267897208520588155734823678603567894373005996132986582548573443974113270682593599108980563590099083306897483648896074029256401888893482421279582317475577712512180341863233891668553849278499685187092538645494649114612591891435800686745132070463
100556095937036905102538523179832446199526507742826168666218687736467897968451
输出的三个值分别是:
- 第一行: solx (k的值)
- 第二行: soly (y的值)
- 第三行: 私钥d = 100556095937036905102538523179832446199526507742826168666218687736467897968451
攻击成功!我们成功恢复了256位的私钥d。
七、解密密文
7.1 验证私钥正确性
在使用恢复的私钥d之前,我们需要验证它是否正确。RSA的基本性质是:
对于任意消息m: (m^e)^d ≡ m (mod n)
我们使用m=2进行验证:
d = 100556095937036905102538523179832446199526507742826168666218687736467897968451
print(pow(pow(2, e, n), d, n) == 2) # 输出: True
验证通过!这证明我们恢复的私钥d是完全正确的。
7.2 解密过程
回顾加密过程:
- c1 = k^e mod n
- c2 = m * K mod a,其中 K = g^k mod a
解密需要三个步骤:
步骤1: 使用私钥d解密c1,得到随机数k
k = pow(c1, d, n)
由于 c1 = k^e mod n,而 d 是 e 的模逆元,因此 c1^d ≡ k (mod n)。
步骤2: 使用k计算共享密钥K
K = pow(g, k, a)
这一步重现了加密时的共享密钥计算过程。
步骤3: 使用K解密c2,得到明文m
m = (c2 * modinv(K, a)) % a
由于 c2 = m * K mod a,我们需要计算 m ≡ c2 * K^(-1) (mod a)。
7.3 完整解密脚本
from Crypto.Util.number import long_to_bytes
def modinv(a, m):
"""扩展欧几里得算法计算模逆元"""
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
gcd, x, _ = extended_gcd(a % m, m)
if gcd != 1:
raise Exception('Modular inverse does not exist')
return (x % m + m) % m
# 公钥和密文
n = 1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567
e = 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451
a = 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523
g = 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722
c1 = 1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773
c2 = 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827
# 通过Boneh-Durfee攻击恢复的私钥
d = 100556095937036905102538523179832446199526507742826168666218687736467897968451
# 解密过程
k = pow(c1, d, n)
K = pow(g, k, a)
m = (c2 * modinv(K, a)) % a
# 转换为字符串
flag = long_to_bytes(m)
print(flag.decode())
运行脚本后,成功得到flag:
ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}
解密成功!
八、技术总结
8.1 攻击链回顾
本题的完整攻击链可以总结为以下步骤:
- 代码审计: 分析加密源代码,识别密钥生成和加密流程
- 漏洞发现: 发现私钥d只有256位,远小于模数n
- 攻击选择: 确定使用Boneh-Durfee攻击恢复小私钥
- 算法适配: 将标准攻击适配到三素数RSA,修改Y的界限
- 私钥恢复: 运行攻击脚本,成功恢复256位私钥d
- 密文解密: 使用私钥解密RSA部分,再解密ElGamal部分
8.2 关键技术点
1. 多素数RSA
多素数RSA使用多个素数的乘积作为模数:
- 标准RSA: n = p * q
- 多素数RSA: n = p * q * r (或更多素数)
- 欧拉函数: φ(n) = (p-1)(q-1)(r-1)
2. 小私钥攻击
当RSA私钥d过小时,可以使用以下攻击方法:
- Wiener攻击: d < n^0.25
- Boneh-Durfee攻击: d < n^0.292
- 本题: d ≈ n^0.167,完全可以被攻击
3. 格基规约(LLL算法)
Boneh-Durfee攻击的核心是LLL算法:
- 用于在格中找到短向量
- 将RSA小根问题转化为格中的短向量问题
- 通过LLL算法求解多项式的小根
4. 混合加密系统
本题使用了RSA和ElGamal的混合加密:
- RSA部分: 加密会话密钥k
- ElGamal部分: 使用共享密钥K加密消息
- 弱点: RSA部分的漏洞导致整个系统崩溃
8.3 安全建议
1. 私钥大小要求
- 私钥d应该足够大,建议 d > n^0.292
- 不要为了提高解密速度而使用小私钥
- 标准做法: 先选择小的公钥e,再计算大的私钥d
2. 密钥生成方式
错误的做法(本题):
d = getPrime(256) # 先生成小的d
e = inverse(d, phi) # 再计算e
正确的做法:
e = 65537 # 先选择标准公钥
d = inverse(e, phi) # 再计算d
3. 混合加密系统设计
- 确保每个组件都是安全的
- 一个组件的弱点会导致整个系统失效
- 使用经过验证的标准方案
九、学习要点
9.1 代码审计能力
在密码学CTF题目中,源代码分析至关重要:
- 仔细分析密钥生成过程
- 识别不安全的参数选择
- 理解加密算法的实现细节
9.2 攻击方法的适配
标准攻击方法需要根据具体场景调整:
- 理解攻击的数学原理
- 识别需要修改的参数
- 正确设置边界条件
9.3 工具使用能力
本题涉及的工具:
- SageMath: 运行Boneh-Durfee攻击脚本
- Python: 编写解密脚本
- 密码学库: pycrypto, gmpy等
9.4 数学基础
解决本题需要的数学知识:
- 数论: 模运算、欧拉函数、模逆元
- RSA原理: 公钥私钥的数学关系
- 多项式理论: Coppersmith方法
十、总结
本题”Gracias”是一道综合性很强的密码学挑战题,涉及多个知识点的综合运用。题目的核心漏洞在于使用了过小的私钥d(256位),这使得Boneh-Durfee攻击成为可能。
通过本题的分析和求解,我们完成了以下工作:
- 分析了三素数RSA的密钥生成和加密流程
- 识别出小私钥漏洞(d ≈ n^0.167)
- 将Boneh-Durfee攻击适配到三素数RSA场景
- 成功恢复256位私钥d
- 解密混合加密系统,获得flag
本题充分展示了密码学攻击的完整流程,从漏洞发现到攻击实施,再到最终的密文解密。这对于学习密码学攻击技术和理解RSA安全性具有重要的教育意义。
参考资料
- Dan Boneh and Glenn Durfee, “Cryptanalysis of RSA with Private Key d Less than N^0.292”
- “Fast Variants of RSA”, New Mexico State University
- David Wong’s Boneh-Durfee Implementation: https://github.com/mimoo/RSA-and-LLL-attacks
- Coppersmith’s Method for Finding Small Roots of Modular Polynomial Equations
最终Flag: ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全《ASIS CTF Finals 2017 – Gracias 密码学挑战题详解》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论