RSA加解密专题 - Coppersmith 相关攻击二
上一章我们介绍了 Coppersmith 相关攻击的基本原理和实现方法，帮助大家了解了如何利用 Coppersmith 方法来攻击 RSA 加密算法。接下来，我们将继续深入探讨 Coppersmith 相关攻击的应用。
欢迎来到《密码学核心算法实战》的 Coppersmith 相关攻击二专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。
$d_q$ 的低位泄露攻击 🙃
这种情况多见于破损pem文件，或者某些特定的实现中，攻击者可能会获得 $d_q$ 的部分低位信息。我们可以利用这些泄露的低位信息来恢复完整的 $d_q$，进而推导出私钥。
和前一篇文章中的私钥低位泄露一样，我们认识到低位，可以理解成原来的方程在取模时的值，然后我们就可以求解另外的参数的低位，最后通过 Coppersmith 方法求解高位。
$d_q$ 的低位泄露攻击例题
'''
破损私钥以及密文
-----BEGIN RSA PRIVATE KEY-----
MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB
yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA==
-----END RSA PRIVATE KEY-----
如何进行手工分离参数就不一一分析了，详情看之前的文章，这里直接给出数据
'''
n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
dq_l = 0xc90bcecf1cbab3358585e8a041d1b1
q_inv_p = 0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598
c = 30867633715813868869594516898484466949832562855682390289015078636128522331216753026144388726648565996116979180534633656943032219373784742974695394149452376092090200793002116674808387426569939440254310919848751355794417768901965964656988835770326844588984815500667657575205646452291264006781430216086103523765
直接取模，然后构建出方程：
因为 $d_q < q - 1$，所以可以知道 $k$ 的范围是 $[1, e]$，我们可以枚举 $k$ 来求解 $q$ 的低位。
小技巧：因为求解 $q$时用到了 $k^{-1}$，即 $k$ 是奇数（要和模互质），所以我们可以直接跳过偶数的 $k$ 来加速枚举。
注意，我们还有一个额外的参数，它是 $q^{-1} \mod p$，我们由关系 $q \cdot q^{-1} \equiv 1 \mod p$ 可以知道
两边同时乘 $q$，就可以得到
所以，在模 $n$ 的情况下，我们构造出 Coppersmith 来解出高位的方程是
解题代码示例：
from Crypto.Util.number import *
from sage.all import *
n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
dq_l = 0xc90bcecf1cbab3358585e8a041d1b1
q_inv_p = 0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598
c = 30867633715813868869594516898484466949832562855682390289015078636128522331216753026144388726648565996116979180534633656943032219373784742974695394149452376092090200793002116674808387426569939440254310919848751355794417768901965964656988835770326844588984815500667657575205646452291264006781430216086103523765
nbits = n.nbits()
konw_bits = dq_l.nbits()
mod = 2**konw_bits
P.<x> = PolynomialRing(Zmod(n))
print("Start solving...")
for k in range(1, e + 1):
if k % 2 == 0:
continue
q_l = ((e * dq_l - 1) * inverse_mod(k, mod) + 1) % mod
# 构造二次多项式
f = q_inv_p * (x * mod + q_l)**2 - (x * mod + q_l)
f = f.monic()
roots = f.small_roots(X=2**(nbits // 2 - konw_bits + 1), beta=1)
if roots:
x_val = int(roots[0])
q = x_val * mod + q_l
if n % q == 0:
print(f"[*] Found q with k = {k}")
p = n // q
d = inverse_mod(e, (p-1)*(q-1))
m = pow(c, d, n)
print("Message:", long_to_bytes(int(m)))
break
# b'flag{the_broken_pem_is_dangerous!}'
双元变量 Coppersmith 攻击 😅
在某些特定的攻击场景中，我们可能会同时获得两个相关参数的部分信息。这时，我们可以构造一个包含两个变量的多项式方程，利用 Coppersmith 方法来同时求解这两个未知数。
但是，相较于单元变量的 Coppersmith 攻击，双元变量需要自己构造格，并且需要自己实现 LLL 算法来进行格的约简，因此难度较大。不过这里我会给出一种简单的构造方式。
对于双元变量方程：
我们可以构造出如下的格：
其中 $X$ 和 $Y$ 是我们对未知数 $x$ 和 $y$ 的范围的估计。通过对这个格进行 LLL 约简，我们可以得到一个新的基，其中包含一个短向量，这个短向量对应的多项式在 $x$ 和 $y$ 的范围内有一个小根，这个小根就是我们要找的解。
双元变量 Coppersmith 攻击例题
from sage.all import *
from Crypto.Util.number import *
from secret import m
p = getPrime(1024)
k = getPrime(64)
r1 = getPrime(512)
r2 = getPrime(512)
t1 = (k * inverse(m + r1, p)) % p
t2 = (k * inverse(m + r2, p)) % p
leak1 = t1 >> 244
leak2 = t2 >> 244
print("leak1 =",leak1)
print("leak2 =",leak2)
print("p =",p)
print("k =",k)
print("r1 =",r1)
print("r2 =",r2)
# leak1 = 1098816764286426157385797801363396675371118108280094592042050672573359525317258628504654733753781201133132612254789332026374788761747254155970613812606464205839077461898387247572628046476143045468089557793517353783804524800718752833296
# leak2 = 1049656482213011765520700817730759174299375637725089075248860293784388137259519537644863360085943551872969496676976510844694589456499043770509884151671385719255903566416708982265930991647265599750836450978226653691655928529034866663445
# p = 108209265779528487066534499136599909709853973107950537298744390757900138945182229902606206423050930011269860879007733713146197683046339710813223062191831446119265107116553831108599559354822644205393315657677544783720147837009193921493082268867053418119324279998822097576668591119657920848005423817059278923289
# k = 12365281680381288671
# r1 = 9144410517756126435013029016083002712735801054642387622098751193487101216215562293703971866241356055783669611204550875272227458679304511201946361648448397
# r2 = 12776175140844604979090713660094736561506184755499536907757209332776967059175177777412075292688365522364612020362287897485306481341531072303954683485324863
在这个例题中，我们同时获得了两个相关参数的部分信息，即 $t1$ 和 $t2$ 的高位泄露。我们可以利用这些泄露的信息来构造一个包含两个变量的多项式方程，并使用 Coppersmith 方法来求解这两个未知数 $x$ 和 $y$。
设 $x$ 和 $y$ 分别是我们要求解的未知数，$A$ 和 $B$ 是已知的高位泄露，那么我们可以构造出如下的方程：
由 $t_1 \cdot (m + r1) \equiv k \mod p$ 可以得到：
带入上面式子，我们可以得到一个关于 $t_1$ 和 $t_2$ 的二次多项式方程：
带入 $t_1 = A + x$ 和 $t_2 = B + y$，进而化简成可以使用格基方法求解的方程：
解题代码示例：
from sage.all import *
from Crypto.Util.number import *
p = 108209265779528487066534499136599909709853973107950537298744390757900138945182229902606206423050930011269860879007733713146197683046339710813223062191831446119265107116553831108599559354822644205393315657677544783720147837009193921493082268867053418119324279998822097576668591119657920848005423817059278923289
k = 12365281680381288671
r1 = 9144410517756126435013029016083002712735801054642387622098751193487101216215562293703971866241356055783669611204550875272227458679304511201946361648448397
r2 = 12776175140844604979090713660094736561506184755499536907757209332776967059175177777412075292688365522364612020362287897485306481341531072303954683485324863
leak1 = 1098816764286426157385797801363396675371118108280094592042050672573359525317258628504654733753781201133132612254789332026374788761747254155970613812606464205839077461898387247572628046476143045468089557793517353783804524800718752833296
leak2 = 1049656482213011765520700817730759174299375637725089075248860293784388137259519537644863360085943551872969496676976510844694589456499043770509884151671385719255903566416708982265930991647265599750836450978226653691655928529034866663445
A = leak1 << 244
B = leak2 << 244
D = (r1 - r2) % p
X_bound = 2**244
Y_bound = 2**244
# 构造二次多项式的系数
c_xy = D
c_x = (D * B + k) % p
c_y = (D * A - k) % p
c_0 = (D * A * B - k * (B - A)) % p
# 归一化多项式，使得最高次项系数为1
inv_D = inverse_mod(D, p)
C_x = (c_x * inv_D) % p
C_y = (c_y * inv_D) % p
C_0 = (c_0 * inv_D) % p
# 构造格
M = Matrix(ZZ,[
[p, 0, 0, 0],
[0, p * X_bound, 0, 0],
[0, 0, p * Y_bound, 0],
[C_0, C_x * X_bound, C_y * Y_bound, X_bound * Y_bound]
])
L = M.LLL()
PR.<x,y> = PolynomialRing(ZZ)
polys = []
for row in L : # 恢复多项式
ploy = (row[0]) + (row[1] // X_bound) * x + (row[2] // Y_bound) * y + (row[3] // (X_bound * Y_bound)) * x * y
if not ploy.is_constant():
polys.append(ploy)
if len(polys) >= 2: # 由于我们构造的格中有两个短向量，所以我们只需要前两个非零多项式来求解
break
x_root = None
f1 = polys[0]
f2 = polys[1]
res = f1.resultant(f2, y) # 消去 y，得到关于 x 的单变量多项式
if not res.is_constant():
roots = res.univariate_polynomial().roots() # 求解 x 的根
for r, _ in roots:
if 0 <= r < X_bound:
f1_x = f1.subs(x=r) # 将 x 的值代入 f1，得到关于 y 的单变量多项式
y_roots = f1_x.univariate_polynomial().roots()
for ry, _ in y_roots: # 验证 (x, y) 是否满足原方程
if (r * ry + C_x * r + C_y * ry + C_0) % p == 0:
x_root = r
break
t1 = A + Integer(x_root)
m = (k * inverse(t1, p) - r1) % p
flag = long_to_bytes(int(m))
print(flag)
# b'flag{u_know_the_bivariate_coppersmith!!!}'
Boneh Durfee 攻击 😝
Boneh Durfee 攻击是一种针对 RSA 加密算法的攻击方法，主要用于攻击 RSA 的私钥 $d$ 的构造不当的情况。具体来说，当 RSA 的私钥 $d$ 满足 $d < N^{0.292}$ 时，攻击者可以利用 Boneh Durfee 攻击来恢复私钥 $d$。这种方法是优于 Wiener 攻击的，因为它可以攻击更大的私钥范围。
从 $e \cdot d = k \cdot \phi(n) + 1$ 开始，直接取模 $e$，我们得到：
由 $n = p \cdot q$ 和 $\phi(n) = (p-1)(q-1)$，我们可以将 $\phi(n)$ 表示为 $n - (p + q) + 1$。因此，我们可以将上面的方程改写为：
转化一下，我们可以得到：
设 $A = \frac{n + 1}{2}$，$x = 2 k$，$y = \frac{p + q}{2}$，我们可以将上面的方程改写为：
我们可以构造多项式 $f(x,y)$，要求找到它在模 $e$ 下 的小根。为了通过LLL算法求解，我们需
要构造一个格，其基向量由 $f(x,y)$ 在模 $e^m$ 下的多个平移（shifts）构成。
我们定义两类平移多项式:
x-shifts：
y-shifts：
然后，我们将 $x$ 替换为 $xX$，$y$ 替换为 $yY$ 以便在格中编码目标上界，根据这些多项式的系数向量构造出一个方阵(Lattice Matrix)。通过运行LLL算法对格进行格基规约，即可在规约后的基中找到范数足够低的向量，这些向量对应于在 $\mathbb{Z}$ 上有相同小根的多项式。
设 $m$ 为格的阶，$t$ 为位移次数，以两者取 $1$ 为例构造格：
在真正的 Boneh-Durfee 攻击脚本中（比如 $m = 4$，$t = 2$ 时），矩阵维度会到达数十维。如果我们巧妙地排序（通常按照 $x$ 的次数和组合），矩阵会呈现出分块对角或下三角的形状：
其中：
- 左上角的块 $M_x$ 对应于 x-shifts，在合理排序后，这部分恰好是一个关于单项式的下三角矩阵，主对角线上的元素都是 $e^{m-k}X^i Y^j$ 形式的对角元。
- 右下角的块 $M_y$，对应于 y-shifts。这些多项式会在矩阵的右侧带来额外的列（代表高阶的 $y$ 和 $xy$ 单项式），需要将这部分一并丢入LLL 算法进行规约。
LLL格基规约的作用就是通过行变换，使得底部的向量（即矩阵的行）变得尽可能短。由于所有行对应的多项式在模 $e^m$ 的意义下根不变，规约后得到的最最短向量对应的那个多项式如果在全空间上的值绝对值小于 $e^m$，就可以直接在整数环 $\mathbb{Z}$ 上求解其根 $x_0$，$y_0$ 了。
Boneh Durfee 攻击例题
from Crypto.Util.number import *
from secret import m
p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
print("n =", hex(n))
d = getPrime(int(1024 * 0.270))
e = inverse(d,phi)
print("e =", hex(e))
c = pow(m, e, n)
print("c =", hex(c))
# n = 0xe788a2054a29f6769c2586a6faec7b2b5880317d5ca6a4595e9f07e164c00e34a0e469ef5127a46d1a4a0e9957189031d735d81bd4a8c80ce4b14b9c76aaa4863b629536ad6d7095a2358375d87155a65f981151b5e0d3591636da13ec004f1b545999ee1de21c790c73fd2ed7338b325ad5df231a193398cb1905a81f499bf1
# e = 0x3d2638e4f1975d3e30470f9b99c799229016f24a74560c92f83a5157a1276bb25eae05ca6a5f9f345d4333602d6c3af54ad4d433eaab55d4f457fbbd78807e85d7f6c3266655dc9cf86d6dcf1d06c5a2c630a4b5ef10a67bb6eacb2e188c33399b1a636ad0bd8b912cb42ec54f73ec965c1ecca7df8d74923b98e93b175bfaf7
# c = 0x694e83ff962e9e98e3aeea50eac9c97f22ce06bff699819c68c6b91c71ad49fad7b2f2bf6eb8dd92aee3234229ce8f8bb52e5894f5551bde341a5e18682776d33353a571d883da4ab40d55efdcc0517d4a8c16a63b01926bfbc6594c9123fc8b19b1cc8996f6466f4363f83e3541929c7c1b73221bf2127b1165d027e925f55d
在这个例题中，我们构造了一个 RSA 加密系统，其中私钥 $d$ 满足 Boneh Durfee 攻击的条件。我们使用 SageMath 来实现 Boneh Durfee 攻击，通过构造格并进行 LLL 规约来恢复私钥 $d$，最终解密出消息 $m$。
from sage.all import *
from Crypto.Util.number import *
n = 0xe788a2054a29f6769c2586a6faec7b2b5880317d5ca6a4595e9f07e164c00e34a0e469ef5127a46d1a4a0e9957189031d735d81bd4a8c80ce4b14b9c76aaa4863b629536ad6d7095a2358375d87155a65f981151b5e0d3591636da13ec004f1b545999ee1de21c790c73fd2ed7338b325ad5df231a193398cb1905a81f499bf1
e = 0x3d2638e4f1975d3e30470f9b99c799229016f24a74560c92f83a5157a1276bb25eae05ca6a5f9f345d4333602d6c3af54ad4d433eaab55d4f457fbbd78807e85d7f6c3266655dc9cf86d6dcf1d06c5a2c630a4b5ef10a67bb6eacb2e188c33399b1a636ad0bd8b912cb42ec54f73ec965c1ecca7df8d74923b98e93b175bfaf7
c = 0x694e83ff962e9e98e3aeea50eac9c97f22ce06bff699819c68c6b91c71ad49fad7b2f2bf6eb8dd92aee3234229ce8f8bb52e5894f5551bde341a5e18682776d33353a571d883da4ab40d55efdcc0517d4a8c16a63b01926bfbc6594c9123fc8b19b1cc8996f6466f4363f83e3541929c7c1b73221bf2127b1165d027e925f55d
def boneh_durfee_attack(N, e, m, t, X, Y):
"""
Boneh-Durfee 攻击主函数
N, e: RSA 公钥
m, t: 决定格大小的超参数
X, Y: 根的上界
"""
PR.<x,y> = PolynomialRing(ZZ)
A = (N + 1) // 2
f = x*(A - y) + 1
shifts = []
# x-shifts
for k in range(m + 1):
for i in range(m - k + 1):
shifts.append(x^i * f^k * e^(m - k))
# y-shifts
for k in range(m + 1):
for j in range(1, t + 1):
shifts.append(y^j * f^k * e^(m - k))
# 提取所有的单项式 (x^i * y^j)
monomials = set()
for shift in shifts:
monomials.update(shift.monomials())
monomials = sorted(list(monomials)) # 固定单项式顺序，即矩阵的列
# 构建格矩阵
dim = len(shifts)
M = Matrix(ZZ, dim, dim)
for i, shift in enumerate(shifts):
shift_scaled = shift(X*x, Y*y)
for j, mon in enumerate(monomials):
M[i, j] = shift_scaled.monomial_coefficient(mon)
print(f"[+] 格矩阵构造完成，维度: {dim}x{dim}")
print("[+] 正在执行 LLL 格基规约...")
M_lll = M.LLL()
# 还原多项式，寻找代数无关解
PR2.<x, y> = PolynomialRing(ZZ)
polys = []
for i in range(M_lll.nrows()):
if M_lll[i].is_zero():
continue
poly = 0
for j, mon in enumerate(monomials):
val = M_lll[i, j] // mon(X, Y)
poly += val * mon(x, y)
if poly != 0:
polys.append(poly)
print(f"[+] 获取到了 {len(polys)} 个短多项式，开始求解公根...")
# 因为计算 Resultant 非常慢，这里我们只取前三个最短的非零多项式进行两两组合求解
for i in range(min(3, len(polys))):
for j in range(i+1, min(4, len(polys))):
p1 = polys[i]
p2 = polys[j]
try:
# 使用结式消元
res = p1.resultant(p2, x)
if res.is_zero():
continue
res_y = res.univariate_polynomial()
roots = res_y.roots()
if roots:
for y0, _ in roots:
p1_univariate = p1.subs(y=y0).univariate_polynomial()
if p1_univariate.is_zero():
p1_univariate = p2.subs(y=y0).univariate_polynomial()
if not p1_univariate.is_zero():
x_roots = p1_univariate.roots()
if x_roots:
x0 = x_roots[0][0]
if (x0 * (A - y0) + 1) % e == 0:
return x0, y0
except Exception as ex:
continue
return None, None
delta = 0.27
bits = 1024
X = floor(2 * e**delta)
Y = floor(n**0.5)
m = 7
t = int((m + 1) * (1 - 2*delta)) + 1
x0, y0 = boneh_durfee_attack(n, e, m, t, X, Y)
if x0 is not None:
print(f"[!] 找到小根 x = {x0}, y = {y0}")
# 根据我们设定的 y = (p+q)/2
half_sum = y0
sum_pq = 2 * half_sum
# 构造二次方程 Z^2 - (p+q)Z + N = 0 求解 p, q
R.<Z> = PolynomialRing(ZZ)
f = Z^2 - sum_pq * Z + n
pq_roots = f.roots()
if pq_roots:
p = pq_roots[0][0]
q = pq_roots[1][0]
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(f"Flag: {flag}")
# Flag: b'flag{boneh_durfee_attack_is_fun!}'
上一章：RSA加解密专题 - Coppersmith 相关攻击一 👈
下一章：RSA加解密专题 - 预言机相关攻击 👈
回到开始：关于我 👈
相关链接：
RSA加解密专题 - 公私钥格式相关攻击 👈
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Alice and Bobの神秘小屋！
相关推荐
2026-03-04
RSA加解密专题 - Coppersmith 相关攻击一
Coppersmith 攻击是一种针对 RSA 加密算法的攻击方法，主要用于在特定条件下恢复 RSA 私钥或解密 RSA 密文。该攻击方法由 Don Coppersmith 在 1996 年提出，利用了 RSA 加密算法中的数学结构和性质。 这里我们并不会深入到 Coppersmith 攻击的数学细节，但我们会介绍一些相关的攻击场景和原理，以帮助你理解 Coppersmith 攻击的基本思想和应用。 部分明文泄露攻击 😋单一变量的情况下，我们主要关注构建一个多项式方程，并使用 Coppersmith 方法来寻找小根。这种方法可以在某些特定条件下成功，例如当明文的某些部分已知或满足特定的数学关系时。 最简单的情况莫过于明文的某些部分已知，不管是哪一种泄露直接套用加密的方程就好： \begin{align*} (m_h + x)^e &\equiv c \pmod{n} \\ (m_h + x \ll m_l.\text{nbits}() + m_l)^e &\equiv c \pmod{n} \\ (x \ll m_l.\text{nbits}() + m_l)^e &\equi...
2026-03-01
RSA加解密专题 - 前言
当你在 CTF 赛场拆解 RSA 密文🧩、爆破私钥参数🔑、或是还原模分解的隐藏信息📝时，那些看似毫无头绪的密文串、复杂的数论参数，背后其实是 RSA 加解密的核心逻辑在层层嵌套⚙️。 欢迎来到《RSA 加解密专题》的 CTF 攻坚工坊！这里没有晦涩的理论空谈（真的不绕弯😜），只有一把把破解 RSA 题型的实战密钥🗝️。 在 CTF 密码学的赛场上，RSA 绝对是出场率拉满的 “常驻嘉宾”🥇，而数论基础是拆解它的利刃🔪，模运算、大素数分解是攻破它的关键招式，加解密的核心逻辑则是破解各类变种题型的底层密码。本系列专题将带你深耕 RSA 加解密的全维度知识，从最基础的 RSA 原理、密钥生成与加解密流程，到 CTF 中高频出现的低加密指数、模重复、私钥泄露、共模攻击等经典题型，再到进阶的多素数 RSA、盲签名、CRT 加速破解等复杂场景，我们会一步步揭开 RSA 在 CTF 题型中的出题套路与破解技巧🎭。 别担心，我会用 CTF 实战视角（🔍➡️💻），让你发现这些看似复杂的 RSA 题型，其实都是核心原理的变形与拓展。它们不仅考验着数论与模运算的基础功底，更需要灵活...
2026-03-13
RSA加解密专题 - 预言机相关攻击
在前面几章中，我们已经介绍了RSA加解密的基本原理和一些相关攻击方法。在本章中，我们将继续深入探讨RSA加解密中的预言机相关攻击。这些攻击利用了预言机（Oracle）的功能来推断出明文或私钥，从而威胁到RSA的安全性。 选择明密文相关攻击 😆这种攻击适用于 oracle（预言机）攻击场景，一般输入明文，返回密文，并且输入的明文中不能包含 flag 还有输入密文，返回明文，并且返回的明文中不能包含flag。 首先，我们选择明文攻击，模数一定是和偶数互质的，所以我们直接选择加密 $2$， $4$， $8$，然后可以知道： \begin{align*} c_1 \equiv 2^e \mod n \\ c_2 \equiv 4^e \mod n \\ c_3 \equiv 8^e \mod n \end{align*}由于我们知道自己输入的明文，所以我们可以知道 $c_1$、$c_2$、$c_3$ 之间的关系： \begin{align*} c_{2}^{2} \equiv c_{4} \mod n \\ c_{2}^{3} \equiv c_{8} \mod n \end{alig...
2026-03-02
RSA加解密专题 - 模数相关攻击
当你在 CTF 赛场遇到 RSA 题型时，模数相关的攻击手法⚔️往往是破解的关键。无论是共模攻击、模重复攻击，还是模数分解的相关漏洞，这些都是 RSA 加解密中常见且高频出现的题型。掌握这些攻击手法，不仅能让你在 CTF 赛场上如鱼得水，还能加深你对 RSA 加解密原理的理解。 暴力分解模数 🥳在 $N$ 的比特位数小于 512 的时候，可以采用大整数分解的策略获取 $p$ 和 $q$。一般来说，使用一些高效的分解工具（如 YAFU、msieve、CADO-NFS 等）可以在合理的时间内完成分解，获取 $p$ 和 $q$。 暴力分解模数例题暴力分解模数例题下载 from Crypto.Util.number import * from secret import M p = getPrime(56) q = getPrime(56) e = 65537 n = p * q long_M = long_to_bytes(M.encode()) C = pow(long_M, e, n) print(C) print(n) #n: 3211733906383171840011...
2026-03-02
RSA加解密专题 - 公钥指数相关攻击
在实际应用中，攻击者可能会利用一些特定的攻击方法来破解RSA加密，尤其是当公钥指数选择不当时。 本文将介绍一些与 RSA 公钥指数相关的攻击方法，包括常见的攻击手段如小公钥攻击、共模攻击等。 共模攻击 😝对于同一个模数 $n$，用于加密同一个 $m$，但是用不同 $e$ 加密两次 \begin{align*} m^{e_1} \equiv c_1 \mod n \\ m^{e_2} \equiv c_2 \mod n \end{align*}使用裴蜀定理可以破解,构造 r e_1 + s e_2 = gcd(e_1,e_2)则由 c_{1}^r \cdot c_{2}^s \equiv m^{er_1 + se_2} \mod n从而绕过私钥d解密 共模攻击例题共模攻击例题下载 from Crypto.Util.number import * from secret import m n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819...
2026-03-03
RSA加解密专题 - 公私钥格式相关攻击
pem 格式的文件通常用于数字证书认证机构(Certificate Authorities，CA)，其文件形式主要为 base64 编码的文件，头尾有类似于——-BEGIN PUBLIC KEY——-和——-END PUBLIC KEY——-的头尾标记 本文的目的就是如何从 .pem 格式的证书中，获取公钥、私钥信息。在 RSA 加密中，实际上公钥和私钥都是由一系列数字组成的，这些数字在.pem格式的证书中以特定的格式存储。通过解析这些数字，我们可以获取到公钥和私钥的相关信息，从而进行加密和解密操作。 PEM文件生成与使用 🥳在python中，可以通过 from Crypto.PublicKey import RSA 生成想要的公私钥文件。 生成公钥文件的代码如下： from Crypto.PublicKey import RSA from Crypto.Util.number import * p,q = getPrime(512),getPrime(512) n = p * q e = 0x10001 pub = RSA.construct((n,e)) with open...
评论
