Boneh-Durfee 攻击:d < n^0.292 时用格基约减恢复 RSA 小私钥
crypto/rsa · verified
一句话结论
当 RSA 私钥 d 小于 n^0.292(超过 Wiener 的 n^0.25 界但未达到安全规模)时,利用 e·d ≡ 1 (mod φ(n)) 构造二元多项式 f(x,y)=1+x(A+y)(A=(n+1)/2),在模 e 下建立 Boneh-Durfee 格,LLL 约减后对短向量求结式,可恢复 x=2k、y=-(p+q)/2,进而得到 d 并解密。
原理
e·d ≡ 1 (mod φ(n))等价于存在整数k使e·d - 1 = k·φ(n)。又φ(n)=n-p-q+1。- 令
A=(n+1)/2、y=-(p+q)/2,则A+y = φ(n)/2。取x=2k,有1 + x(A+y) = 1 + k·φ(n) = e·d ≡ 0 (mod e)。 - 因此
(x,y)=(2k, -(p+q)/2)是二元多项式f(x,y)=1+x(A+y)在模e下的小根。x的规模约为d(因为k≈d),y的规模约为√n。 - Boneh-Durfee 把
f的移位多项式(x^i·e^{m-k}·f^k与y^j·f^k·e^{m-k})组成格,利用x、y都较小使对应向量成为短向量;LLL 后取两个独立短向量,对其多项式求结式消去一个变量,解出(x0,y0)。 - 由
1 + x0(A+y0) = e·d得d = (1 + x0(A+y0))/e。d恢复后即可解密密文。 - 界:Wiener 攻击要求
d < n^0.25;Boneh-Durfee 把可解范围推进到d < n^0.292。超过该界需要部分密钥泄露、多密钥等额外信息。
触发条件
- 已知
n、e、c,且d明显小于正常规模(d < n^0.292)。 e较大(通常与n同量级),使f模e的小根条件成立。- 能运行 LLL/BKZ 与多项式结式运算(Sage)。
- 格参数
m、t需按delta调整;delta越接近 0.292,所需格维数与计算量越大。
利用步骤
- 估计
d的比特规模,确认d < n^0.292(若d < n^0.25可先试更简单的 Wiener 连分数)。 - 取
delta≈0.271、m=8、t=int((1-2·delta)·m)、X=2·floor(n^delta)、Y=floor(n^(1/2))。 - 构造
P.<x,y> = PolynomialRing(ZZ),A=int((n+1)/2),pol = 1 + x*(A+y)。 - 调用标准
boneh_durfee(pol, e, m, t, X, Y):生成移位多项式、构造格、LLL、取短向量、求结式并解出(solx,soly)。 - 计算
d = int(pol(solx,soly)/e),用pow(pow(2,e,n),d,n)==2或直接解密校验。 m = pow(c,d,n),转字节得到明文。
PoC
from Crypto.Util.number import *
N = ...
e = ...
c = ...
delta = 0.271
m = 8
t = int((1 - 2 * delta) * m)
X = 2 * floor(N^delta)
Y = floor(N^(1/2))
P.<x, y> = PolynomialRing(ZZ)
A = int((N + 1) / 2)
pol = 1 + x * (A + y)
# boneh_durfee 为标准的 Boneh-Durfee 格实现:
# 生成 x/y 移位多项式 -> 构造格 -> LLL -> 取短向量 -> 结式消元
solx, soly = boneh_durfee(pol, e, m, t, X, Y)
d = int(pol(solx, soly) / e)
m_int = power_mod(c, d, N)
print(long_to_bytes(m_int))
说明:
boneh_durfeehelper 较长(原文附带完整脚本),核心是格构造、BB.LLL()、对两行短向量求resultant并解根;本卡只保留可调参数与调用方式。
变体与关联
- 变体:
d < n^0.25时用 Wiener 连分数攻击,计算量更小;Boneh-Durfee 是其扩展。 - 变体:同一模数多把密钥、
d略大于 0.292 时,用 Howgrave-Graham–Seifert 多密钥方法把界推高。 - 变体:已知
d的高位/低位时,可结合部分密钥泄露的 Coppersmith/格方法。 - 关联:[[crypto-rsa-partial-e-coppersmith-hgs-multi-key-small-d]](多密钥小 d)、[[crypto-rsa-private-exponent-low-bits-partial-p]](d 低位泄露)、[[crypto-rsa-dual-rsa-lattice-small-d]](同一 d 用于多个模数)。
检测与防御
- 防御:
d必须足够大(至少n^0.5量级),使用标准库生成密钥,不要为了“加速解密”人为选择小d。 - 防御:优先使用
e=65537的标准密钥;若必须用小d,改用 CRT-RSA 并确保dp/dq也足够大。 - 检测:审计密钥参数,检查
d.bit_length()是否明显小于n.bit_length();CTF 中看到d约为n^0.27即可按本卡尝试。 - 响应:确认小私钥后可被恢复,立即轮换密钥并审计历史密文。