当前位置：首页 > news >正文

CTF密码学实战：当RSA公钥e过大时，如何用Boneh-Durfee攻击还原DASCTF的so-large-e题目

news 2026/5/8 10:30:36

CTF密码学实战：当RSA公钥e过大时，如何用Boneh-Durfee攻击还原DASCTF的so-large-e题目

在CTF竞赛的密码学挑战中，RSA问题始终占据重要地位。其中一类特殊情形——公钥指数e异常巨大的情况，往往让参赛者感到棘手。本文将深入剖析DASCTF竞赛中一道典型例题"so-large-e"，通过Boneh-Durfee攻击实现私钥恢复的全过程。

1. RSA异常参数攻击场景识别

当遇到RSA问题时，首要任务是分析密钥参数特征。常规RSA中，e通常取65537这样的小素数，但当出现以下特征时需警惕：

e与n的比特长度接近（如本题e为1024位，n为1024位）
e明显大于常规值（超过n^0.5时需要特殊处理）
d值相对较小（满足d < n^0.292时适用Boneh-Durfee）

# 典型异常密钥特征示例 from Crypto.PublicKey import RSA with open('pub.pem') as f: key = RSA.importKey(f.read()) print(f"n位数: {key.n.bit_length()}, e位数: {key.e.bit_length()}") print(f"e/n比例: {key.e/key.n:.4f}")

2. Boneh-Durfee攻击原理剖析

与广为人知的Wiener攻击相比，Boneh-Durfee攻击能处理更大的私钥d。其核心思想是将密钥恢复问题转化为格基约化问题：

2.1 数学基础转换

RSA等式ed ≡ 1 mod φ(n)可表示为：

ed = 1 + k(N - s) 其中 s = p + q - 1

这转化为关于(d, k)的方程：

k(N - s) + 1 ≡ 0 mod e

2.2 格构造策略

攻击通过构造特定格基，利用LLL算法寻找短向量：

格基参数	作用
维度	通常取m=4, t=2
delta	平衡参数(0.5-0.6)
X,Y	d和k的界

# 参数选择参考表 delta_values = { 'n_bits': [1024, 2048, 4096], 'recommended_delta': [0.54, 0.52, 0.50], 'max_d_bits': [270, 540, 1080] }

3. 实战攻击脚本解析

以下是针对DASCTF题目的完整攻击实现：

from Crypto.Util.number import long_to_bytes from sage.all import * def boneh_durfee(n, e, delta=0.54, m=4): n_bits = n.nbits() X = int(2*n**delta) Y = int(3*n**0.5) # 多项式构造 P.<x,y> = PolynomialRing(ZZ) pol = 1 + x*(n-y) # 格基生成 polynomials = [] for i in range(m+1): for j in range(m-i+1): poly = x**j * pol**i * e**(m-i) polynomials.append(poly) # LLL约化 monomials = [] for poly in polynomials: monomials += poly.monomials() monomials = sorted(set(monomials)) dim = len(monomials) M = matrix(ZZ, dim) for i in range(dim): for j in range(dim): M[i,j] = polynomials[i](X,Y).monomial_coefficient(monomials[j]) B = M.LLL() # 解提取 Q = sum([(B[0,i]/monomials[i](X,Y))*monomials[i] for i in range(dim)]) roots = Q.roots() if roots: d = int(roots[0][0]) return d return None # 题目参数 n = 116518679305515263290840706715579691213922169271634579327519562902613543582623449606741546472920401997930041388553141909069487589461948798111698856100819163407893673249162209631978914843896272256274862501461321020961958367098759183487116417487922645782638510876609728886007680825340200888068103951956139343723 e = 113449247876071397911206070019495939088171696712182747502133063172021565345788627261740950665891922659340020397229619329204520920999096535909867327960323598168596664323692312516466648588320607291284630434682282630745947689431909998401389566081966753438869725583665294310689820290368901166811028660086977458571233 c = 6838759631922176040297411386959306230064807618456930982742841698524622016849807235726065272136043603027166249075560058232683230155346614429566511309977857815138004298815137913729662337535371277019856193898546849896085411001528569293727010020290576888205244471943227253000727727343731590226737192613447347860 # 执行攻击 d = boneh_durfee(n, e) if d: print(f"Recovered d: {d}") flag = long_to_bytes(pow(c, d, n)) print(f"Flag: {flag.decode()}") else: print("Attack failed, try adjusting delta")

4. 参数调优与攻击优化

实际应用中需要根据题目特点调整关键参数：

4.1 delta选择策略

场景特征	推荐delta	预期效果
e ≈ n	0.54-0.56	高成功率
e < n/2	0.52-0.54	平衡速度与成功率
超大n	0.50-0.52	防止内存溢出

4.2 性能优化技巧

格维度选择：m=3-5之间平衡效率与效果
早期终止：检测到第一个有效解立即返回
多线程尝试：并行测试不同delta值

# 参数优化示例 for delta in [0.52, 0.54, 0.56]: for m in [3, 4, 5]: print(f"Trying delta={delta}, m={m}") d = boneh_durfee(n, e, delta, m) if d: break if d: break