RSA算法^[1]是目前使用最广泛的公钥密码算法，其安全性得到了广泛的探讨和研究，其解密指数的安全性分析尤为重要^[2-4]。在实际应用中，用户会选择小解密指数，以提升RSA算法解密或签名的速度。但是，使用小解密指数会使得密钥被攻击者恢复，造成财产的损失、信息的泄露。如何找出RSA算法所使用的解密指数的安全范围是业界关注的重点问题。

目前已有多项研究提出针对使用小解密指数的RSA算法的攻击并给出解密指数的不安全范围。最著名的是WIENER^[5]提出的攻击，通过分析该攻击的成功条件，WIENER指出若解密指数的比特长度小于模数的1/4，则可被恢复。在文献[5]的基础上，VERHEUL和TILBORG^[6]得到大素数的高位被泄露时解密指数的不安全范围，OJHA和PADHYE^[7]得到构成模数的2个大素数存在小系数线性组合时解密指数的不安全范围。这些研究皆指明攻击成功时解密指数与模数的关系。然而，解密指数的安全性不仅与模数相关。STEINFELD等^[8]指出在解密指数略大于Wiener攻击的范围时，也可攻击成功。BONEH和DURFEE^[9]、MAITRA和SARKAR^[10]皆指出，解密指数的安全性还与加密指数有关。可见，在分析RSA算法的解密指数安全性时，只考虑解密指数与模数的关系具有局限性。

为此，本文首先提出了使用格规约(Lattices Reduction)对RSA算法的解密指数进行攻击的算法(LW)，然后分析LW算法攻击成功的条件，最终得到攻击成功时解密指数与模数、加密指数、大素数的关系。LW算法的思路如下：首先，根据RSA算法中公钥与解密指数的关系，使用RSA算法的公钥构造二维格，使其最短向量尽可能与解密指数相关；然后，使用Gauss的格规约方法^[11]或LLL算法^[12]找到该最短向量；最后，在最短向量中提取解密指数。经证明，若使用连分数逼近方法可攻击成功，则在相同条件下，使用LW算法也能攻击成功，而使用LW算法可以得到更广义的、与素数和加密指数相关的RSA算法的解密指数的安全范围。目前主流的基于连分数逼近的攻击方法有：Wiener的攻击^[5]、Verheul和Tilborg的攻击^[6]、Ojha和Padhye的攻击^[7]。通过分析在这3种攻击方法的条件下使用LW算法可成功攻击的条件，分别得到在这3个条件下更广义的RSA算法的解密指数的安全范围。

1.   预备知识

1.1   符号说明

如无特殊说明，文中符号解释如下：det(M)表示矩阵M的行列式；||v||表示向量v的欧几里得范数，即若v=(a, b)，则$\|\boldsymbol v\|=\sqrt{a^2+b^2}$；|a|表示a的绝对值；$\lceil a\rceil 、[a]$和$\lfloor a\rfloor$分别表示a的向上取整、四舍五入和向下取整；gcd(a, b)表示a和b的最大公因数；φ(·)为欧拉函数；$\mathbb{R}$和$\mathbb{Z}$分别表示实数域和整数域；#S表示集合S的元素个数；$a \lessapprox b$表示a小于或约等于b；a=θ(b)表示a与b量级相同，即存在可忽略量ε>0，使得(1-ε)b≤a≤(1+ε)b。

1.2   RSA算法

RSA算法^[1](算法1)由3部分组成：密钥生成、加密和解密。

算法1   RSA算法

密钥生成：选择大素数p和q，计算模数N=pq，φ(N)=(p-1)(q-1)，选择加密指数e，使得gcd(e, φ(N))=1，计算解密指数d≡e^-1(mod φ(N))。公开公钥(N, e)，保存私钥d。

加密：输入明文m，输出密文c≡m^e(mod N)。

解密：输入密文c，输出明文m′≡c^d(mod N)。

1.3   连分数

有限连分数^[13]简称连分数，其表达式为：

或简写为[a₀, a₁, a₂, …, a_n]，当a₁, a₂, …, a_n都为正整数时，又称为简单连分数。[a₀, a₁, a₂, …, a_i](0≤i≤n)被称为连分数的第i个收敛(Convergent，或称“渐进”)。

下面给出2个可用于连分数逼近方法的连分数性质。

引理1^[13]   任何有理数都可以用简单连分数表示。

引理2^[13]   若$\left|\frac{p}{q}-x\right|<\frac{1}{2 q^2}$，则$\frac{p}{q}$是x的一个连分数收敛。

1.4   格

定义1^[11]   令$\boldsymbol{v}_1, \boldsymbol{v}_2, \cdots, \boldsymbol{v}_n \in \mathbb{R}^m$为一组线性独立的向量，$\boldsymbol B=\left[v_1, v_2, \cdots, v_n\right] \in \mathbb{R}^{m \times n}$，则由B生成的格L(B)为v₁, v₂, …, v_n的整数线性组合的集合，即

定义2^[11]   格的最短向量问题(SVP)是：寻找格中欧几里得范数最小的非零向量，即寻找非零向量v∈L(B)，使得||v||最小。

当格的维度为2时，可使用Gauss的格规约方法^[11]解决SVP问题; 当格的维度不大时，可使用LLL算法^[12]近似地解决SVP问题。

定义3^[11]   定义n维格L(B)的基本域为集合$\mathcal{F}\left(\boldsymbol v_1, \cdots, \boldsymbol v_n\right)=\left\{t_1 \boldsymbol v_1+t_2 \boldsymbol v_2+\cdots+t_n \boldsymbol v_n: 0 \leqslant t_i<1\right\}, \mathcal{F}$的容积(Volume)为L(B)行列式(Determinant)，即：

以下格的性质被用于本文的格规约方法。

引理3^[11]   令$\mathbb{B}_R$(a)是球心为a、半径为r的n维球体，则$\mathbb{B}_r$(a)的容积为：

其中Γ为伽马函数。特别地，当维度为2，即n=2时，有Γ(1+n/2)=Γ(2)=1，可得Vol($\mathbb{B}_r$(a))=πr²。

引理4^[11]   令$\mathbb{B}_r$(0)为L(B)中以零点为球心、半径为r的n维大球体，则$\mathbb{B}_r$(0)中向量的数量可近似等于$\mathbb{B}_r$(0)的容积除以L(B)的基本域的容积，即：

使用引理4可近似地估算格中最短向量的长度，Gauss的启发式就是一种这样的估算算法。

备注1^[11]   (Gauss的启发式)令格L(B)的维度为n，定义高斯期望最短长度为σ(L(B))，若格基B拥有足够的随机性，则格L(B)的最短向量长度满足||v||_shortest≈σ(L(B))。其中，当格L(B)的维度n=2时，有

根据备注1可得，若格L(B)中存在向量w∈L(B)，使得$\|\boldsymbol{w}\| \lessapprox \sigma(L(\boldsymbol{B}))$，则向量w大概率为格L(B)的最短向量。

引理5^[11]   (Hermite定理)n维格L(B)中至少有一个向量v∈L(B)满足

特别地，当格L(B)的维度n=2时，有

2.   LW算法的设计与分析

本章提出运用格规约对使用小解密指数的RSA算法进行攻击的LW算法，然后对LW算法进行分析。

算法2   LW算法

输入：RSA算法的模数N和加密指数e。

输出：RSA算法的解密指数d。

步骤1：构造格基$\boldsymbol{B}=\left[\begin{array}{cc} R & -N \\ 0 & e \end{array}\right]$，其中R=θ(p)。

步骤2：使用Gauss的格规约方法或LLL算法找出格L(B)的最短向量w。

步骤3：计算v=(k, d)=wB^-1，返回d。

LW算法的攻击思路如下：首先, 使用已知公钥信息构造二维格; 然后, 计算格中参数, 使得该格的最短向量与解密指数尽可能相关；最后，通过解决二维格的SVP问题来恢复解密指数。具体过程如下：

(1) 构造二维格L(B)：根据RSA算法的密钥生成过程，可知存在k，使得ed-kφ(N)=1。构造向量v和格基B，使得向量w=vB尽可能为格L(B)的最短向量。其中向量v=(k, d)，格基B形如$\left[\begin{array}{cc} R & -N \\ 0 & e \end{array}\right]$，R为待计算参数。

(2) 计算格中参数R：通过计算合适的参数R，使得向量w中每个元素量级相同，进而使得LW算法拥有最大成功概率。令s=1-(p+q)，可得w=(kR, ks+1)。若要w中每个元素量级相同，则需要R=θ(s)。不妨令p≥q，即p为RSA算法的参数中较大的一个素数，可得s=θ(p)。所以，在取R=θ(p)时，可使得向量w中每个元素量级相同，即若ρ=[log₂ p]，则取R=2^ρ。

(3) 计算解密指数d：使用Gauss的格规约方法或LLL算法找出向量w，然后计算v=wB^-1=(k, d)，进而恢复解密指数d。

使用LW算法攻击成功的关键点在于：所构造的向量w需要为格L(B)的最短向量，进而能使用Gauss的方法或LLL算法找到该向量。可使用备注1的方法得到向量w为格L(B)的最短向量所需满足的条件，见以下命题。

命题1   在RSA算法中，令大素数p和q满足p≥q。若满足ped²≤N²，则在已知模数N和加密指数e的情况下，使用LW算法可恢复解密指数d。

证明   不妨令p=N^ρ，e=N^ε，d=N^δ，由RSA算法的密钥生成过程可得φ(N)=(p-1)(q-1)=N+1-(p+q)。令s=1-(p+q)，可得φ(N)=N+s，其中|s|=θ(N^ρ)。由于d≡e^-1(mod φ(N))，则存在k，使得ed-kφ(N)=1，即ed-kN=ks+1，其中|k|=θ(N^ε+δ-1)。令R=θ(N^ρ)，v=(k, d)，$\boldsymbol{v}=(k, d), \boldsymbol{B}=\left[\begin{array}{cc} R & -N \\ 0 & e \end{array}\right]$，w=(kR, ks+1)，可得vB=w，即w为格L(B)上的向量，且$\|\boldsymbol w\| \approx \sqrt{2} N^{\rho+\varepsilon+\delta-1}, \sigma(L(\boldsymbol{B})) \approx \sqrt{1 / \pi} N^{(\rho+\varepsilon) / 2}$。由备注1可得，若||w||≤σ(L(B))，则w大概率为L的最短向量，进而可使用Gauss的格规约方法或LLL算法找到w，并通过计算v=(k, d)=wB^-1来恢复解密指数d。当N足够大时，可近似比较指数的大小，即ρ+ε+δ-1≤(ρ+ε)/2，整理可得

即ped²≤N²。综上，若ped²≤N²，则可恢复解密指数d。证毕。

下面给出2个使用LW算法对使用小解密指数的RSA算法进行攻击的例子。本文所有例子均经过实验验证，实验的参考代码可在GitHub仓库中获取：https://github.com/CyT0ver/Attack-RSA-Small-d-using-Lattice。

例1   p=7 771 159 731 609 483 211，q=2 947 386 503 237 666 051，N=pq=22 904 611 307 449 834 128 008 346 881 909 169 761，e=722 262 311 366 174 354 989，d=158 561 584 531 008 409。其中，p>q，p≈N^{0.505 6}，e≈N^{0.558 3}，d≈N^{0.460 4}，ped²≈N^{1.984 7} < N²。使用LW算法，在设置R=2⁶⁴时，使用LLL算法可找到短向量w，并由v=wB^-1=(k, d)可得解密指数d。

例2   p=11 691 268 676 806 734 812 183 364 083，q=5 161 104 192 036 123 949，N=pq=60 339 855 778 087 867 006 418 157 012 645 372 358 782 723 767，e=217 313 062 367 259 180 263 192 524 848 395，d=27 488 663 851 854 587。其中，p>q，p≈N^{0.600 0}，e≈N^{0.691 2}，d≈N^{0.351 4}，ped²≈N^{1.994 1} < N²。使用LW算法，在设置R=2⁹³时，使用LLL算法找到短向量w，并通过计算v=wB^-1=(k, d)恢复解密指数d。

命题1的证明依赖于备注1的Gauss启发式，由于Gauss的启发式是一个概率算法，所以LW算法在极小的概率下会存在特殊情况，使得即使满足命题1的攻击范围，也会攻击失败，如下例。

例3   p=6 212 434 253 312 289 161，q=7 705 371 143 963 067 067，N=pq=47 869 111 629 240 255 903 708 882 380 340 160 787，e=6 919 054 782 499 191 497，d=6 918 446 685 856 378 313。其中，p>q，p≈N^{0.498 8}，e≈N^{0.500 0}，d≈N^{0.500 0}。计算可得ped²≈N^{1.998 8} < N²，满足命题1的攻击范围。但是，在实验中发现，在设置R=2⁶²时，d与使用LW算法求出的d′相差2。

对例3中的特殊情况进行分析，结果显示：在k可枚举时，存在v′=(k, d+i)，$\boldsymbol{B}=\left[\begin{array}{cc} R & -N \\ 0 & e \end{array}\right]$，w′=(kR, ie+ks+1)，使得v′B=w′，即w′也是格L(B)上的向量，甚至是最短向量，从而导致使用Gauss的格规约方法或LLL算法找到了向量w′，而不是LW算法需要寻找的向量w。

当出现如例3的特殊情况时，可在LW算法的基础上使用枚举的方法，以从向量w′中恢复解密指数。如：当|(ks+1)/e|可枚举时，通过枚举i直至i≈|(ks+1)/e|，可得|ie+ks+1| < e; 通过选取R=θ(N/d)来使得||w′||≈e，即w′是格L(B)中比命题1中的w更短的向量；进而可使用Gauss的格规约方法或LLL算法找到w′, 然后计算v′=w′B^-1=(k, d+i)，从而恢复解密指数d。这种枚举的方法在ped²>N²但d略大于e的情况下也能攻击成功，如下例。

例4   p=16 634 746 592 804 413 571，q=5 904-115 439 904 173 963，N=pq=98 213 464 197 469 889 222 198 936 571 382 051 873，e=28 616 917 559 186 953，d=3 432 007 098 400 442 548 397，其中d>e且ped²>N²，不在LW算法的攻击范围内。但通过实验发现，在设置R=2⁵⁴时，d与使用LW算法求出的d′相差了788，即通过枚举i直到i=788时，可恢复解密指数d。

命题1的结论及上述4个例子为RSA算法的参数选择提供了参考，如：RSA算法的使用者为了加快RSA算法的加密和解密速度而同时选择小的加密指数e和解密指数d，由于在生成密钥时需要保证ed≡1(mod N)，为了均衡加密和解密的速度，使用者只能选取e≈N^1/2和d≈N^1/2，但这种密钥是不安全的，因为此时会因为满足LW算法的攻击条件而导致攻击者可使用LW算法恢复解密指数。

3.   LW算法与连分数逼近方法的等价关系

连分数逼近方法表明：若存在足够大的a、b、c和d，满足$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$，则在已知a和b的条件下，可求得c和d。LW算法表明：若存在向量v=(d, c)，格基$\boldsymbol{B}=\left[\begin{array}{cc}R & a \\ 0 & -b\end{array}\right]$和向量w=vB=(Rd, ad-bc)，满足$\|\boldsymbol{w}\| \lessapprox \sigma(L(\boldsymbol{B}))$，则在已知格基B的条件下，可求得向量v=(d, c)。

本章证明连分数逼近方法和LW算法存在等价关系。首先证明：若连分数逼近方法的攻击条件可满足，则LW算法的攻击条件也可满足。由引理2可知，连分数逼近方法的成功条件为$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$。由命题1可知，若满足$\|\boldsymbol{w}\| \lessapprox \sigma(L(\boldsymbol{B}))$，则使用LW算法可以极大概率得到向量v。而由以下命题可知，若$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$成立，可推出$\|\boldsymbol{w}\| \lessapprox \sigma(L(\boldsymbol{B}))$也成立。

命题2   若存在足够大的a、b、c和d，使得$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$，则存在$\boldsymbol{B}=\left[\begin{array}{cc}R & a \\ 0 & -b\end{array}\right], \boldsymbol{v}=(d, c), \boldsymbol{w}= \boldsymbol{v} \boldsymbol{B}=(R d, a d-b c)$，使得$\|\boldsymbol{w}\| \lessapprox \sigma(L(\boldsymbol{B}))$。

证明   设$b=2^\beta, d=2^\delta$，对不等式$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$左右同乘bd，可得$|a d-b c| \leqslant \frac{b}{2 d}$。记ad-bc=s，则$|s| \leqslant \frac{b}{2 d}=2^{\beta-\delta-1}$。设置参数$R=2^{\beta-2 \delta-1}, \boldsymbol{B}=\left[\begin{array}{cc}R & a \\ 0 & -b\end{array}\right]$, $\boldsymbol{v}=(d, c)$，可得w=vB=(Rd, s)为格L(B)中的向量，且$\|\boldsymbol{w}\| \leqslant \sqrt{2} \cdot 2^{\beta-\delta-1}=2^{\beta-\delta-1 / 2}, \operatorname{det}(L(\boldsymbol{B}))^{1 / 2}=2^{(\beta-2 \delta-1+\beta) / 2}= 2^{\beta-\delta-1 / 2}$，即||w||≤det(L(B))^1/2。当有足够大的a、b、c、d，使得$\sqrt{1 / \pi}$可忽略时，有

证毕。

然后证明：若LW算法的攻击条件可满足，则连分数逼近方法的攻击条件也可满足。命题1指出，若使用LW算法能成功攻击，则向量w为格L(B)的最短向量。由引理5可知，若w为格L(B)的最短向量，则$\|\boldsymbol{w}\| \leqslant \sqrt{2} \operatorname{det}(L(\boldsymbol{B}))^{1 / 2}$。由引理2知，连分数逼近方法的成功条件为$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$。以下命题证明，若$\|\boldsymbol{w}\| \leqslant \sqrt{2} \operatorname{det}(L(\boldsymbol{B}))^{1 / 2}$成立，则$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$也成立。

命题3   若存在足够大的a、b、c和d，参数$R= \left|\frac{a d-b c}{2 d}\right|$，格基$\boldsymbol{B}=\left[\begin{array}{cc}R & a \\ 0 & -b\end{array}\right]$，向量v=(d, c)，w=vB=(Rd, ad-bc)，使得w为格L(B)的最短向量，则$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$。

证明   设b=2^β，d=2^δ，R=2^γ，则$\operatorname{det}(L(\boldsymbol{B}))= 2^{\beta+\gamma}, \|\boldsymbol{w}\|=(\sqrt{5} / 2) \cdot 2^{\delta+\gamma+1}$。因为w为L(B)的最短向量，所以由引理5得

当a、b、c和d足够大时，可只考虑指数的比较，即δ+γ+1≤(β+γ)/2，整理可得δ+(δ+γ+1)≤β-1，即|d(ad-bc)|≤b/2，不等式两边同乘以1/(bd²), 则有$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$。证毕。

综合命题2和命题3可知，在知道a、b、c和d的比特长度时，若可以利用a/b的连分数逼近得到c/d，则能够以极大概率通过LW算法得到v=(d, c)，反之亦然。故连分数逼近方法和LW算法的格规约方法存在等价关系。

命题4   若使用连分数逼近方法可成功攻击，则在相同条件下使用LW算法也可成功攻击，反之亦然。

证明   首先证明满足连分数逼近方法的攻击条件时，使用LW算法可攻击成功。由引理2得，连分数逼近方法的成功条件为$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$。由命题2可知，对于格基$\boldsymbol{B}=\left[\begin{array}{cc}R & a \\ 0 & -b\end{array}\right]$、向量v=(d, c)和向量w=vB=(Rd, ad-bc)，满足$\|\boldsymbol{w}\| \lessapprox \sigma(L(\boldsymbol{B}))$。再根据命题1，此时LW算法可攻击成功。

然后证明满足LW算法的攻击条件时，使用连分数逼近方法可攻击成功。由命题1得，若使用LW算法能攻击成功，则向量w为格L(B)的最短向量。由命题3得，此时满足$\left|\frac{a}{b}-\frac{c}{d}\right| \leqslant \frac{1}{2 d^2}$，即使用连分数逼近方法可攻击成功。证毕。

下面对第2章的若干例子使用连分数逼近的方法，以论证这种等价关系。

(1) 例1中，可得到$\left|\frac{e}{N}-\frac{k}{d}\right| \leqslant \frac{1}{2 d^2}$，即可用e/N的连分数逼近k/d，实验得到k/d是e/N的第3个连分数收敛。

(2) 例2中，可得到$\left|\frac{e}{N}-\frac{k}{d}\right| \leqslant \frac{1}{2 d^2}$，即可用e/N的连分数逼近k/d，实验得到k/d是e/N的第7个连分数收敛。

(3) 例3中，可得到$\left|\frac{e}{N}-\frac{k}{d}\right|>\frac{1}{2 d^2}$，但实验中发现，d与e/N的第1个连分数收敛的分母只相差了2。

(4) 例4中，可得到$\left|\frac{e}{N}-\frac{k}{d}\right|>\frac{1}{2 d^2}$，但实验得到d与e/N的第1个连分数收敛的分母相差了787，与e/N的第2个连分数收敛的分母相差了788，即通过枚举i直到i=787(或i=788)时，可恢复解密指数d。

4.   不同攻击条件下的LW算法

在第2章中给出了在已知RSA算法的模数N和加密指数e的条件下使用LW算法可攻击成功的条件，在实际应用中，攻击者还可获取更多的附加信息，这些信息的泄露会影响解密指数的安全范围，因此有必要分析在攻击者知道不同信息的条件下的解密指数安全范围。

目前有多项研究提出了在不同前提条件下针对使用小解密指数的RSA算法的攻击方法，主流的攻击方法有Wiener攻击^[5]、Verheul-Tilborg攻击^[6]和Ojha-Padhye攻击^[7]。但这3种攻击方法均基于连分数逼近的方法，且只给出了攻击成功时解密指数与模数的狭义安全关系。

为分析更广义的解密指数的安全范围，本章对满足不同攻击条件下的LW算法进行设计与分析。第3章的结论显示，若使用连分数逼近方法可攻击成功，则使用LW算法也可攻击成功。故可把LW算法应用于以上3种攻击方法的条件中，并分析在各个已知条件下，使用LW算法成功攻击时解密指数与模数、加密指数、大素数的广义安全范围。

Wiener的攻击方法表明，若满足d < N^1/4，则可根据公钥(N, e)恢复解密指数d。Wiener攻击的已知条件与LW算法的已知条件一致，故根据第2章的分析，Wiener的攻击条件d < N^1/4只是p=θ(N^1/2)且e=θ(N)的特殊情况。使用LW算法重新分析后，得到攻击成功的条件为ped²≤N²。

Verheul-Tilborg的攻击方法表明，若已知大素数的高位比特$\tilde{p}$，使得$|p-\tilde{p}| \leqslant N^{1 / 2-\gamma}$，则当d≤N^1/4+γ/2时，可根据公钥(N, e)恢复解密指数d。

Ojha-Padhye的攻击方法表明，若已知满足$|a p-b q| \leqslant N^{\alpha / 2} / 16$的a和b，则当d < N^1/2-α/4时，可根据公钥(N, e)恢复解密指数d。

下面分别对在Verheul-Tilborg攻击方法和Ojha-Padhye攻击方法的已知条件下，对LW算法进行设计与分析。

4.1   Verheul-Tilborg条件下的LW算法

本节提出在Verheul-Tilborg攻击方法的已知条件下对使用小解密指数的RSA算法进行攻击的LW算法：首先，根据关系ed-kN′=k(s_p+s_q)+1、$N^{\prime}=N+1-(\tilde{p}+\tilde{q})$构造向量v=(k, d)和格基$\boldsymbol{B}=\left[\begin{array}{cc}R & -N^{\prime} \\ 0 & e\end{array}\right]$，设置参数$R=\theta(|p-\tilde{p}|)$，以使vB为格L(B)中的最短向量的概率最大; 然后，通过Gauss的格规约方法或LLL算法找到vB，并最终恢复v中的解密指数d。详见算法3和命题5。

算法3   Verheul-Tilborg条件下的LW算法

输入：RSA算法的模数N、加密指数e和大素数p的高位$\tilde{p}$。

输出：RSA算法的解密指数d。

步骤1：计算$\tilde{q}=\lfloor N / \tilde{p}\rfloor$和$N^{\prime}=N+1-(\tilde{p}+\tilde{q})$。

步骤2：构造格基$\boldsymbol{B}=\left[\begin{array}{cc}R & -N^{\prime} \\ 0 & e\end{array}\right]$，其中$R=\theta(|p-\tilde{p}|)$。

步骤3：使用Gauss的格规约方法或LLL算法找到格L(B)的最短向量w。

步骤4：计算v=(k, d)=wB^-1，返回d。

命题5   在RSA算法中，令大素数p和q满足p≥q，且令p=N^ρ。若存在$\tilde{p}$满足$|p-\tilde{p}| \leqslant N^{\rho-\gamma}$，则在已知模数N、加密指数e和$\tilde{p}$，且满足ped²≤N^2+γ的情况下，使用算法3可恢复解密指数d。

证明   令$s_p=p-\tilde{p}$，可得$\left|s_p\right| \leqslant N^{\rho-\gamma}$；令$\tilde{q}=N / \tilde{p}$，由N=pq可得$|q-\tilde{q}| \leqslant N^{1-\rho-\gamma}$。令$s_q=q-\tilde{q}$，可得$\left|s_q\right| \leqslant N^{1-\rho-\gamma}$。由于p≥q，则有$\left|s_p+s_q\right| \leqslant N^{\rho-\gamma}$。令e=N^ε，d=N^δ，由RSA算法的密钥生成过程可得$\varphi(N)=N+1- (\tilde{p}+\tilde{q})-\left(s_p+s_q\right)$。不妨令$N^{\prime}=N+1-(\tilde{p}+\tilde{q})$，则φ(N)=N′-(s_p+s_q)。由于d≡e^-1(mod φ(N))，则存在k，使得ed-kφ(N)=1，即ed-kN′=k(s_p+s_q)+1，其中|k|=θ(N^ε+δ-1)。令参数R=θ(N^ρ-γ)，向量v=(k, d)，格基$\boldsymbol{B}=\left[\begin{array}{cc}R & -N^{\prime} \\ 0 & e\end{array}\right]$，格向量w=vB=(kR, k(s_p+s_q)+1)，可得$\|\boldsymbol{w}\| \approx \sqrt{2} N^{\rho-\gamma+\varepsilon+\delta-1}, \sigma(L(\boldsymbol{B})) \approx \sqrt{1 / \pi} N^{(\rho-\gamma+\varepsilon) / 2}$。根据备注1，若||w||≤σ(L(B))，则w大概率为L(B)的最短向量。使用Gauss的格规约方法或LLL算法可找到短向量w，进而通过计算v=wB^-1=(k, d)恢复解密指数d。当N足够大时，可近似比较指数的大小，即ρ-γ+ε+δ-1≤(ρ-γ+ε)/2，整理可得

即ped²≤N^2+γ。综上，若ped²≤N^2+γ，则使用算法3可恢复解密指数d。证毕。

由命题5可得：Verheul-Tilborg攻击成功的条件d≤N^1/4+γ/2只是p=θ(N^1/2)且e=θ(N)的特殊情况, 若使用算法3进行攻击，攻击成功的条件可扩展为ped²≤N^2+γ(p≥q)。

下面给出使用算法3对使用小解密指数的RSA算法进行攻击的例子。

例5   p=13 556 816 809 365 573 763，q=1 947 095 473 445 800 211，N=pq=26 396 416 643 849 644 470 088 394 458 681 463 993，e=454 562 615 750 669 153 749，d=7 607 160 071 080 291 129，$\tilde{p}$=13 546-827 679 130 451 968。其中，p>q，p≈N^{0.511 3}，e≈N^{0.552 0}，γ≈0.083 7，d≈N^{0.504 6}>N^1/4+γ/2不在Verheul-Tilborg算法的攻击范围，但ped²≈N^{2.072 4} < N^{2.083 7}=N^2+γ，即在算法3的攻击范围，实验测试结果表明可用算法3恢复该例子中的解密指数。若令$\tilde{q}=\left\lfloor\frac{N}{\tilde{p}}\right\rfloor$和$N^{\prime}=N+1-(\tilde{p}+\tilde{q})$，可得$\left|\frac{e}{N^{\prime}}-\frac{k}{d}\right| \leqslant \frac{1}{2 d^2}$，即还可用e/N′的连分数逼近得到k/d，实验可得k/d是e/N′的第7个连分数收敛。

4.2   Ojha-Padhye条件下的LW算法

本节提出在Ojha-Padhye的已知条件下对使用小解密指数的RSA算法进行攻击的LW算法：首先，根据关系ed-kN′=ks+1、$N^{\prime}=N+1-(\sqrt{b / a}+ \sqrt{a / b}) \sqrt{N}$构造向量v=(k, d)和格基$\boldsymbol{B}=\left[\begin{array}{cc}R & -N^{\prime} \\ 0 & e\end{array}\right]$，设置参数R=θ(N^α/2), 以使vB为格L(B)中的最短向量的概率最大；然后，通过Gauss的格规约方法或LLL算法找到vB，并最终恢复v中的解密指数d。详见算法4和命题7。

算法4   Ojha-Padhye条件下的LW算法

输入：RSA算法的模数N和解密指数e，满足|ap-bq|≤N^α/2/2的a和b，其中p和q为RSA算法的大素数。

输出：RSA算法的解密指数d。

步骤1：计算$N^{\prime}=\left\lfloor N+1-\left(\sqrt{\frac{b}{a}}+\sqrt{\frac{a}{b}}\right) \sqrt{N}\right\rfloor$。

步骤2：构造格基$\boldsymbol{B}=\left[\begin{array}{cc}R & -N^{\prime} \\ 0 & e\end{array}\right]$，其中R=θ(N^α/2)。

步骤3：使用Gauss的格规约方法或LLL算法找到格L(B)的最短向量w。

步骤4：计算v=(k, d)=wB^-1，返回d。

命题6   若有a、b、p、q和N=pq，使得

则    $\left|p+q-\left(\sqrt{\frac{b}{a}}+\sqrt{\frac{a}{b}}\right) \sqrt{N}\right| \leqslant N^{\alpha / 2}$。

证明   与文献[7]的命题1证明类似。首先

由于$\sqrt{\frac{b}{a}} \cdot \frac{\sqrt{N}}{p}>0$，有$\left|1+\sqrt{\frac{b}{a}} \cdot \frac{\sqrt{N}}{p}\right|>1$，所以

即

同理可得

联立式(4)和式(5)，可得

证毕。

命题7   在RSA算法中，令大素数p和q满足p≥q。若存在a和b，满足|ap-bq|≤N^α/2/2，则在已知模数N、加密指数e、a和b，且满足ed²≤N^2-α/2的情况下，可使用算法4恢复解密指数d。

证明   不妨设e=N^ε，d=N^δ，由命题6可得$\mid p+q- (\sqrt{b / a}+\sqrt{a / b}) \sqrt{N} \mid<N^{\alpha / 2}$。令$s=p+q-(\sqrt{b / a}+\sqrt{a / b}) \sqrt{N}$，可得|s| < N^α/2。由RSA算法的密钥生成过程可得$\varphi(N)=N+1-(\sqrt{b / a}+\sqrt{a / b}) \sqrt{N}-s$。不妨令$N^{\prime}=N+1- (\sqrt{b / a}+\sqrt{a / b}) \sqrt{N}$，则φ(N)=N′-s。由于d≡e^-1(mod φ(N))，则存在k，使得ed-kφ(N)=1，即ed-kN′=ks+1，其中|k|=θ(N^ε+δ-1)。令参数R=θ(N^α/2)，向量v=(k, d)，格基$\boldsymbol{B}=\left[\begin{array}{cc}R & -N^{\prime} \\ 0 & e\end{array}\right]$，格向量w=vB=(kR, ks+1)，可得$\|\boldsymbol{w}\| \approx \sqrt{2} N^{\alpha / 2+\varepsilon+\delta-1}, {\sigma}(\boldsymbol{L}) \approx \sqrt{1 / \pi} N^{\alpha / 4+\varepsilon / 2}$。根据备注1，若||w||≤σ(L(B))，则w大概率为L的最短向量。使用Gauss的格规约方法或LLL算法可找到短向量w，进而通过计算v=wB^-1=(k, d)来恢复解密指数d。当N足够大时，可近似比较指数的大小，即α/2+ε+δ-1≤α/4+ε/2，整理可得

即ed²≤N^2-α/2。综上，若ed²≤N^2-α/2，则使用算法4可恢复解密指数d。证毕。

由命题7可得：Ojha-Padhye攻击成功的条件d < N^1/2-α/4只是e=θ(N)的特殊情况，若使用算法4进行攻击，攻击成功的条件可扩展为ed²≤N^2-α/2。

下面给出使用算法4对使用小解密指数的RSA算法进行攻击的例子。

例6   p=7 010 690 394 300 496 153，q=5 662 462 476 069 981 011，N=pq=39 697 771 289 070 818 936 145 992 186 588 550 683，e=388 452 861 963 165 789 401，d=13 387 488 027 727 273 721。其中，p>q，p≈N^{0.501 2}，e≈N^{0.547 6}，d≈N^{0.508 7}。令α=0.796 7，可知存在a=21和b=26，使得|ap-bq|=473 902 490 912 927 < 474 721 050 866 297=N^α/2/2。d>N^1/2-α/4不在Ojha-Padhye算法的攻击范围，但ed²≈N^{1.565 0} < N^{1.617 0}=N^2-α/2，即在算法4的攻击范围。实验结果表明：可用算法4恢复该例子中的解密指数。若令$N^{\prime}=N+1-(\sqrt{b / a}+\sqrt{a / b}) \sqrt{N}$，可得$\left|\frac{e}{N^{\prime}}-\frac{k}{d}\right| \leqslant \frac{1}{2 d^2}$，即可用e/N′的连分数逼近k/d，实验可得k/d是e/N′的第7个连分数收敛。

5.   结论

本文提出了运用格规约方法对使用小解密指数的RSA算法进行攻击的LW算法，并分析该算法攻击成功时解密指数与模数、加密指数、大素数的关系。同时，证明了LW算法与使用连分数逼近的攻击方法存在等价关系，即在符合连分数逼近方法的攻击条件时，LW算法也可成功攻击，反之亦然。基于这种等价关系，本文分析在3种不同已知条件下，使用LW算法可成功攻击时解密指数与模数、加密指数、大素数的广义安全关系，结论如下：

(1) 在Wiener攻击^[5]的已知条件下，使用LW算法进行攻击，攻击范围可从Wiener提出的d < N^1/4扩展到ped²≤N²；

(2) 在Verheul-Tilborg攻击^[6]的已知条件下，使用LW算法进行攻击，攻击范围可从Verheul和Tilborg提出的d≤N^1/4+γ/2扩展到ped²≤N^2+γ；

(3) 在Ojha-Padhye攻击^[7]的已知条件下，使用LW算法进行攻击，攻击范围可从Ojha和Padhye提出的d < N^1/2-α/4扩展到ed²≤N^2-α/2。

由于LW算法的正确性证明依赖于Gauss的启发式，所以该算法在极小的概率下会存在即使满足攻击范围也会攻击失败的特殊情况。实验表明，这些特殊情况大多在k值可被枚举的情况下出现，如例3。如何找到能够包含这类特殊情况的、更准确的攻击范围，是本文遗留的开放问题。