二十年以来对 RSA 密码系统攻击综述

0.引入

这篇文章翻译自Dan Boneh的Twenty Years of Attacks on the RSA Cryptosystem，其中部分译文参考了二十年以来对 RSA 密码系统攻击综述 (seebug.org)（但是这个译文机翻有点重，而且公式也没有了）。希望通过这篇文章，对目前常见的RSA攻击进行一个总结以及较为深入的了解。

1.分解大整数(Factoring Large Integers)

我们将模分解称为对RSA的暴力攻击。尽管因数分解算法一直在改进，但在正确使用RSA时，目前的技术水平，还远远没有对RSA的安全性构成威胁。虽然大整数的因式分解是计算数学中最美丽的问题之一，但它不是本文的主题。

目前最快的分解算法是General Number Field Sieve(普通数域筛选法)，其时间复杂度为

学长在服务器上操作下来情况是这样的：16核32线程分解400bits的n，需要4000s；分解505bits的n，需要67小时。

 

• 开放性问题1：给定整数n和e，满足gcd(e, phi(n))=1。定义函数$f_{e,n}:Z^*_n\to Z^*_n,\ f_{e,n}(x)=x^{\frac{1}{e}}\pmod n$​​​，是否存在一个多项式时间的算法A，对于给定n，可以计算n的分解同时能访问一些e的oracle $f_{e,n}(x)$。

有学者指出，上述开放性问题，对于一个较小的e来说，答案是否定的。

下面我们将证明知道公开私钥 d 和分解 N 是等效的。 因此，对于知道 d 的任何一方隐藏 N 的因式分解是没有意义的。

• 分解n显然可以很容易计算得到d。
• 若给定d，我们有$k=e*d-1$​，通过定义我们可以知道，k是$\phi (n)$​的倍数，我们知道$\phi(n)$​是偶数，同时有$k=2^t*r$​，（$r$​是奇数）。对于$g\in Z^*_n$​，有$g^k\equiv1\pmod n$​，并且$g^{\frac{k}{2}}$​是模n的平方根，由中国剩余定理我们知道，对于n=p*q，这样的数有4个。其中，有两个是正负一，还有两个是$\pm x$​，其中$x\equiv1\pmod p,x\equiv-1\pmod q$​。使用后两者，我们就可以通过计算gcd(x-1, n)得到n的分解。有简单的论证表明，如果g是在$Z^*_n$​中随机取，那么序列$g^{\frac{k}{2}},g^{\frac{k}{4}},\dots,g^{\frac{k}{2^t}}\pmod n$​​​​的其中一个是平方根且能分解n的概率至少为1/2。序列中的所有元素都可以在$O(\log_2{n})^3)$​的时间内有效计算。

2.两种简单攻击

2.1共模攻击

共模攻击是一种只需要知道多组公钥对，就可以推出明文的攻击，在上一篇中已经介绍，这里就不再赘述。

2.2Blinding——盲签名（攻击）

令<n,d>为私钥，<n,e>为公钥。我们想让Bob对m签名，Bob肯定会拒绝。于是我们选择一个随机数$r\in Z_n^*$​，并且令$M'=r^em$​，明文改变了，Bob可能愿意在看上去没什么问题的M’上签名。但是此时，我们就可以很简单的得到原本的签名$S'\equiv(M')^d\pmod n,\ S\equiv S'/r\pmod n$​。

不过由于大多数签名方案在签名之前对消息应用"单向散列"算法，这种攻击并不是一个严重的问题。况且，正如标题中攻击在括号里一样，这种盲签名在区块链中应用更广。

3.低解密指数攻击

为了减少解密时间（或签名时间），人们希望使用一个较小的d，而不是随机的d。而这种操作就会导致下面的一些攻击。

• 定理(M. Wiener)：令$n=pq$，且$q<p<2q，d<\frac{1}{3}n^{\frac{1}{4}}$​，如果给定公钥，我们可以有效恢复解密指数d。

• 证明：我们有等式$ed-k\phi(n)=1$，于是

  此时，$\frac{k}{d}$是$\frac{e}{\phi(n)}$​的近似值。尽管我们不知道$\phi(n)$，但是我们可以用n近似它。

  同时，由p、q的不等关系容易得到$p+q-1<3\sqrt n$，于是

  我们用上面的不等式代换原有的等式

  由于等式$k\phi(n)=ed-1<ed$，因为$e<\phi(n)$，根据不等式原则可以知道$k<d<\frac{1}{3}n^{\frac{1}{4}}$。于是，上面的不等式可以进一步得到

  这是一个经典的逼近关系，分数 $\frac{k}{d}$ 且 $k<n$ 在约束$\log_2n$内非常逼近 $\frac{e}{n}$ 。实际上，所有类似这样的分数都是的连分数展开的收敛。因此我们首要做的便是计算的连分数 $\frac{e}{n}$ 的收敛，其中一个连分数就等于 $\frac{k}{d}$ 。由于$ed − kϕ(N)=1$，所以$gcd(k,d)=1$，因此$\frac{k}{d}$是一个最简分数。这就是一个可以算出密钥d的线性时间算法。

Wiener attack后来被 Boneh and Durfee两人改进，把d的界扩大到了$d<n^{0.292}$，这样的结果表明Wiener的界限并不固定。正确的界限可能是$d<n^{0.5}$。不过截至到这篇paper发表的时间，这还是一个尚未解决的问题。

• 开放性问题2：令$n=pq，d<n^{0.5}$，如果给定满足RSA的e、d，是否可以有效的恢复d？

4.低加密指数

为了减少加密或签名验证时间，通常会使用一个小的公钥指数。e的最小可能值为3，但为防止某些攻击，一般推荐使用$e=2^{16}+1=65537$。当使用e=65537时，签名验证需要17次乘法运算，而使用随机的e时则需要大约1000次乘法运算。与上一节的攻击不同，当使用一个小e时，应用的攻击不仅仅是得到明文而已。

4.1 Coppersmith’s Theorem

针对RSA低公钥指数最有力的攻击是基于Copper-smith的一个定理，Coppersmith定理有很多应用，这里我们只讨论其中的一些应用，具体如下。

• 定理(Coppersmith)：令n为一个整数，$f\in Z[x]$是d次的一元多项式，设$X=N^{\frac{1}{d}-\epsilon}$其中$\epsilon\geq0$，在给定$<n,f>$之后Marvin能够有效找到所有满足$|x_0|<X$的整数，运行时间由在维数为$O(w)$且$w=min(1/\epsilon,\log_2N)$的格上运行的LLL算法所需时间决定。

  该定理为有效地求模$N$的所有小于$X=N^{1/d}$的根提供了一种算法，当X越小，算法的运行时间越短。这个定理的强大之处在于它能够找到多项式的小根。当模数为素数时，就目前而言，找不到比使用Coppersmith定理更好的求根算法。

我们概述了Coppersmith定理证明背后的主要思想，我们采用由Howgrave-Graham提出的简化方法。给定多项式$h(x)=\Sigma a_ix^i\in Z[x]$，并定义$||h||^2=\Sigma|a_i|^2$。证明需要下面的引理。

• 引理：令$h(x)\in Z[x]$是d次多项式，同时令X为正整数。假设$||h(xX)||<N/\sqrt d$，如果存在$|x_0|<X$满足$h(x_0)=0\pmod N$，那么$h(x_0)=0$对整数成立。

• 证明：从Schwarz不等式观察到：

  因为$h(x_0)=0\pmod N$，所以我们可以得到结论。

引理指出，如果$h$是一个低范数多项式，则$h\pmod N$的所有小根也是$h$在整数上的根。引理表明，要找到$f(x)\pmod N$的一个小根$x_0$，我们需要寻找另一个和$f\pmod N$有相同根的低范数多项式$h\in Z[x]$，这样就能容易找到在$h$整数上的根$x_0$。为此，我们可以寻找一个多项式$g\in Z[x]$，使得$h=gf$具有低范数，即范数小于$N$。这相当于寻找具有低范数多项式的整数线性组合$f,xf,x^2f,\dots,x^rf$。不过，大多数情况下，并不存在具有足够小的范数的非平凡线性组合。

Coppersmith找到了解决这个问题的方法：如果$f(x_0)\equiv 0\pmod N$​成立，那么对于任意$k$​则有$f(x_0)^k\equiv 0\pmod {N^k}$​。更一般地，定义以下多项式：

• 对于给定m，有

  对任意$u\geq0,0\leq v\leq m$，则$x_0$是$g_{u,v}(x)\pmod {N^m}$的一个根。

要使用引理4，我们必须找到多项式$g_{u,v}(x)$的一个整数线性组合$h(x)$，使得$h(xX)$的范数小于 $N^m$(回想一下$X$是满足$X\leq N^{1/d}$的$x_0$的上界)。由于范数（是$N$而不是$N^m$）的松弛上界，我们可以证明，对于足够大的$m$，总是存在一个线性组合$h(x)$满足所要求的界。一旦$h(x)$被找到，引理4就说明它有整数根$x_0$，于是，$x_0$就可以很容易地找到。

如何有效地找到$h(x)$还有待证明，要做到这一点，我们必须先陈述一些关于格的基本事实。 设是$u_1,\dots,u_w\in Z^w$线性独立的向量。由$<u_1,\dots,u_w>$构成的(满秩)格是$u_1,\dots,u_w$的所有整数线性组合的集合。$L$的行列式定义为w×w方阵的行列式，其行向量是$u_1,\dots,u_w$。

在我们的例子中，我们把多项式$g_{u,v}(xX)$看作向量，并研究了它们所构成的格L。设$v=0,\dots,m$，$u=0,\dots,d-1$，则格的维数为$w=d(m+1)$。例如，当$f$是二次一元多项式且$m=3$时，得到以下的格：

$*$元素对应我们忽略的其值的多项式的系数，所有空元素为零。由于矩阵是三角阵，其行列式就是对角线元素乘积。我们需要在这个格中找到短向量。

Hermite的一个经典结论表明：任意维数为$w$的格$L$包含一个非零向量$v\in L$​，它的范数满足$||v||\leq \gamma_w\det(L)^{1/w}$，其中$\gamma_w$是只依赖于$w$的常数。Hermite的界可以用来证明，对于足够大的$m$，我们的格包含小于的范数$N^m$向量。问题是我们能否有效地在中构造长度小于Hermite界的短向量，而LLL算法恰好是一种有效的算法。

• Fact（LLL）：若格$L$​有一组基$<u_1,\dots,u_w>$​，通过LLL算法，可以得到一个向量$v\in L$满足：

  算法的运行时间是输入长度的四分之一

通过LLL算法，我们就可以完成Coppersmith定理的证明。为了保证LLL算法产生的向量满足引理4的界，我们需要满足：

其中$w=d(m+1)$是$L$​的维度。常规计算表明，对于足够大的$m$，也能满足约束条件。实际上，当时$X=N^{\frac{1}{d}-\epsilon}$，取$m=O(k/d)$和$k=\min(\frac{1}{\epsilon},\log N)$就足够了。因此，运行时间主要由在维数为$O(k)$的格上运行LLL算法所决定。

一个自然而然的问题，Coppersmith定理能否应用于二元和多元多项式。如果$f(x,y)\in Z_N[x,y]$有根$(x_0,y_0)$且$|x_0y_0|$有适当的界，我们能有效地找到$(x_0,y_0)$吗？尽管相同的技术似乎仍然适用于某些二元多项式，但它目前还是一个有待证明的开放性问题。随着越来越多的结果依赖于Coppersmith定理的二元扩展，严密的算法将会非常有用。

• 开放性问题3：找出可以将 Coppersmith 定理推广到二元多项式的一般条件。

4.2 Hastad广播攻击

其简化版本就是国内常说的低加密指数广播攻击，直接CRT然后开三次方就可以得到明文。一般来说，需要收集k组密文，$k\geq e$。

Hastad提出了一种更强的攻击方法。为了抵御上述的攻击，发送方会做一些简单的防御。Bob在加密之前"填充"消息，而不是直接广播加密后的$M$。例如，如果$M$是m位长的，Bob可以将$M_i=i2^m+M$发送给party $P_i$。由于我们获得了不同消息的加密，就无法发起上述攻击。然而，Hastad证明了这种线性填充是不安全的，事实上，他证明了在加密之前对消息应用任何固定多项式都不能阻止攻击。

假设对于每个参与者$P_1,\dots,P_k$，Bob有一个固定的公用多项式$f_i\in Z_{N_i}[x]$。为了广播消息$M$，Bob将$f_i(M)$的加密发送给party $P_i$。我们通过窃听知道了$C_i\equiv f_i(M)^{e_i}\pmod N_i$，其中$i=1,\dots,k$。Hastad证明，如果有足够的参与方，我们就可以从所有的密文中恢复出明文。以下定理是Hastad原始结论的一个更强的版本。

• 定理6（Hastad）：令$N_1,\dots,N_k$​是两两互质的整数，并设$N_{\min}=\min_i(N_i)$​。设$g_i\in Z_{N_i}$是$k$​个$d$次多项式。假设存在唯一的$M<N_{\min}$满足

  假设$k>d$​，给定$<N_i,g_i>_{i=1}^k$，我们就可以很容易恢复$M$。

这个定理表明，当提供了足够多的方程，我们就可以有效地求解以两两互素的整数为模的单变量方程组。令$g_i\equiv f_i^{e_i}-C_i\pmod {N_i}$​，当有至少$d$​组数据时，我们就可以恢复$M$​了。特别的，如果所有的e都一样并且Bob发送线性相关的消息，那么我们只要$k(k>e)$组数据，​就可以算出明文。

Hastad的原始定理比上述定理更弱。与$d$次多项式不同，Hastad定理需要$d(d+1)/2$​次多项式。Hastad定理的证明类似于上一节中提到的Coppersmith定理证明。然而，Hastad 格中没有使用$g$​的幂，因此得到了一个较弱的界 。

总结这一部分，我们注意到，要正确地防御上述广播攻击，必须使用随机填充方法，而不是使用固定填充方法。

4.3 Franklin-Reiter相关消息攻击

当Bob用相同的模数发送与Alice相关的加密消息时，Franklin和Reiter发现了一种巧妙的攻击。$<N,e>$是Alice的公钥，假设$M_1,M_2\in Z_N^*$是两个不同的消息，但存在一个已知的多项式$f\in Z_N[x]$，满足$M_1=f(M_2)$。为了将$M_1,M_2$发送给Alice，Bob可能会简单地对消息进行加密，并发送得到的密文$C_1,C_2$。通过证明可以知道，在给定$C_1,C_2$的情况下，我们可以很容易地计算出$M_1,M_2$。虽然攻击对任意小$e$都有效，但为了简化证明，我们给出了$e=3$时的引理。

• 引理（FR）：令$e=3$，$<N,e>$是RSA的公钥，且对于$M_1\ne M_2\in Z_N^*$，存在一个线性多项式$f=ax+b\in Z_N[x]\ \ (b\ne0)$满足$M_1=f(M_2)\pmod N$。于是，给定$<N,e,C_1,C_2,f>$，我们就可以在$(\log N)^2$的时间内恢复$M_1,M_2$。

• 证明：为了保证这部分证明的一般性，我们使用任意的$e$来表示它（而不是局限在$e=3$）。由于$C_1\equiv M_1^e\pmod N$，我们可以知道$M_2$是多项式$g_1(x)=f(x)^e-C_1\in Z_N[x]$的一个根。同样的，$M_2$也是$g_2(x)=x^e-C_2\in Z_N[x]$的一个根。这两个多项式都有同一个线性因子$x-M_2$，因此我们就可以计算$\gcd(g_1,g_2)$，如果结果是线性的，那么我们就找到了$M_2$。

  我们证明了当$e=3$时，GCD的结果一定是线性的。多项式因子$x^3-C_2$将$p,q$都模成一个线性因子和一个不可约二次因子(因为$\gcd(e,\phi(N))=1$，所以$x^3-C_2$在$Z_N$中只有一个根)。因为$g_2$不能整除$g_1$，所以GCD一定是线性的。对于$e>3$的情况，GCD几乎总是线性的。然而，对于一些罕见的$M_1,M_2$和$f$，有可能得到一个非线性的GCD，在这种情况下攻击会失败。

  对于$e>3$情况，攻击所需时间是$e$的平方。因此，只有在使用小的公钥指数$e$时才能应用这种攻击。对于大$e$，计算GCD的工作令人望而却步。为任意$e$设计这样的攻击是一个有趣的问题（尽管可能很困难）。特别是，上面$g1$和$g2$的GCD能否在$\log e$的多项式时间内找到吗？

4.4 Coppersmith短填充攻击

Franklin-Reiter的攻击可能看起来有点人为。毕竟，为什么Bob要给Alice发送相关消息的加密呢？Coppersmith加强了攻击，并证明了一个关于填充攻击的重要的结论。

一个简单的随机填充算法可能会通过将几个随机位附加到一个末端来填充一个明文 $M$，但是以下攻击指出了这种简单填充的危险。假设Bob向Alice发送了正确填充的加密$M$。攻击者Marvin拦截密文并阻止其到达目的地。Bob注意到Alice没有回复他的消息，并决定将重新发送给Alice。他随机填充并传输生成的密文$M$。Marvin现在有两个密文，对应于使用两种不同随机填充对同一消息的两次加密。以下定理表明，虽然他不知道使用的填充算法，但Marvin仍能够算出明文。

• 定理8：令$<N,e>$是RSA的公钥，N长为$n$-bits。令$m=[n/e^2]$，设$M\in Z_N^*$是长最多为$n-m$-bits的消息。定义$M_1=2^mM+r_1,M_2=2^mM+r_2$，其中$r_1,r_2$是不同的整数，且$0\leq r_1,r_2\leq 2^m$。如果给定$<N,e>$和密文$C_1,C_2$，那么就可以有效恢复$M$。
• 证明：定义$g_1(x,y)=x^e-C_1,g_2(x,y)=(x+y)^e-C_2$。我们知道，当$y=r_2-r_1$时，两个多项式有共同的根$M_1$。也就是说，$\Delta=r_2-r_1$是结果$h(y)=res_x(g_1,g_2)\in Z_N[y]$的根。$h$的次数最多为$e^2$。此外，有$|\Delta|<2^m<N^{1/e^2}$，因此$\Delta$是$h\pmod N$的一个小根，所以我们就可以通过Coppersmith定理计算它。一旦$\Delta$求出来，Franklin-Reiter攻击就可以用来计算$M_2$，最终算出$M$。

当 e = 3 时，只要填充长度小于消息长度的 1/9，就可以发起攻击。 这是一个重要的结论。 但是需要注意，对于 e = 65537 这一推荐值，对于标准的模数大小来说，这种攻击就无效了。

4.5 部分密钥泄露攻击

设$<N,d>$为RSA私钥，假设Marvin通过某种方式知道了$d$的一部分，比如说$d$的四分之一比特。他能得到$d$剩下的部分吗？当相应的公钥指数很小时，答案是肯定的。最近，Boneh，Durfee和Frankel证明了只要$e<\sqrt N$，就有可能从它的一小部分位算出的所有部分。这个结论说明了保护整个RSA私钥的重要性。

• 定理9(BDF)：令$<N,d>$是RSA的私钥，其中$N$有n比特。当给定$[n/4]$个最低有效位，Marvin可以在