毕业设计（2）：维纳攻击论文翻译

发表于 更新于 分类于 本文字数： 6k

前言

1989年，人们在 MICHAEL J. WIENER 的手稿中发现了一篇题为 Cryptanalysis of Short RSA Secret Exponents 的论文。此文中，Wiener 介绍了一种使用续分数算法对 RSA 短密钥的攻击方法。出于毕业设计的要求，下面是我对这篇论文的翻译。请注意，此翻译未经校对，仅作存档用。

下面是一些可能会让人感到疑惑的用词：

  • 位长：通常原文是 size of,bits of number of 等，指的应该是指数的二进制位长度；
  • 秘密指数，公共指数：指的是密钥和公钥中，在加解密时充当指数的数字，即 \(e\) 和 \(d\)；
  • 续分数：continued fraction；
  • 分数：本文中，有可能其实是分式。

下面是翻译正文。

I. 概要

本文介绍了一种在使用短密钥的 RSA 时的密码分析攻击。该攻击使用了一种基于续分数的算法，当知道了分数的足够近的估值，该算法能在多项式时间内找到分数的分子和分母。含有秘密指数 \(d\) 的分式的估值可以用公共指数 \(e\) 和模数 \(pq\) 来创建。此基于续分数的算法可以使用此估值可以充分地找到短秘密指数。典型情况是 \(e < pq\) 、 \(\gcd( p - 1, q - 1)\) 较小且 p 和 q 的位长大致相同，则这种攻击可以发现位长最大约为模数四分之一的秘密指数。本文介绍了使用这种攻击的方法、改进方法和两个悬而未决的问题。这种攻击对 RSA 的正常情况，即秘密指数的大小与模数大致相同的情况，不构成威胁。这是因为这种攻击使用的是公共指数提供的信息，而在正常情况下，公共指数的选择几乎可以与模数无关。

II. 介绍

在 RSA 公钥系统中的所有密钥对集合中[5]，有一些密钥的特性使其可以被多种密码分析攻击所利用。有些攻击利用了模数的弱点，还有的攻击则利用了公共指数或秘密指数的弱点。这里讨论的”弱点”，是那些使得针对 RSA 的攻击可以在模数长度的多项式时间内完成的特性。

针对 RSA 模数的攻击旨在发现模数的两个质数因子（\(p\) 和 \(q\)）。在 \(p-1\) 和 \(q-1\) 的质因子都足够小的时候，有一种攻击可以分解模数[3]。当 \(p+1\) 和 \(q+1\) 的质因子都很小的时候，也存在一种攻击可以分解模数[6]。当两个质数的差小于 \(\sqrt{p}(\log p)^k\) ，其中 \(k\) 是某些常量，此时存在一个分解模数的简单算法。此算法基于下面的特征。

\[ \left(\frac{p+q}{2}\right)^2-pq=\left(\frac{p-q}{2}\right)^2 \]

通过寻找 \(\frac{p+q}{2}\) 和 \(\frac{p-q}{2}\) 就可以分解模数。\((\frac{p+q}{2})^2\) 可以在从模数开始的完全平方线性搜索中找到。当模数与其平方之差恰为完全平方数时，就可以找到正确的平方。

还有很多 RSA 攻击除了其它条件外，还要求公共指数或秘密指数足够短。某些情况下，使用短公共指数或秘密指数很有吸引力，因为这可以减少加密或解密操作的执行时间。这是因为在模数固定的情况下，RSA 的加解密时间大致与指数位长成正比。使用短指数特别有优势的一种情况是，双方的通信设备算力差距悬殊。例如在智能卡和大型计算机之间的通信中使用 RSA 。在这个例子中，让智能卡掌握短秘密指数而大型计算机掌握短公共指数，以减智能卡需要做的处理是很有吸引力的选择。但是，我们必须警惕对 RSA 的短指数攻击。

当向多方广播同一信息时，短公共指数就有可乘之机[1]。为了描述此种攻击，假设将一条消息 \(m\) 广播给三方，且公共指数为 \(e_1=e_2=3_3=3\) ，模数为 \(n1,n2,n3\) ，那么加密消息为：

\[ m^3\mod{n_1},\quad m^3\mod{n_2},\quad m^3\mod{n_3} \]

使用中国剩余定理，我们可以找出 \(m^3\mod{n_1n_2n_3}\) 。但是，由于 \(m<n_1,n_2,n_3\)，所以 \(m^3<n_1n_2n_3\) 。因此，\(m^3\) 不会因对 \(n_1n_1n_2n_3\) 取模而减小。消息可以通过对 \(m^3\) 求立方根而得到。在本论文中描述了一种对短秘密指数的攻击。这种攻击基于续分数。

II. 续分数背景

当已知分数的估计值足够接近时，就可以使用续分数求出分数的分子和分母。这将与第四节中的 RSA 有关，在第 IV 节中，公共指数和模数将用于构建一个含有秘密指数的分数估计值。

根据给定的分数的估计值，利用续分数求分子和分母的算法在此称为续分数算法。该算法将在第 III 节中介绍。 本 节将为讨论连续分数算法提供必要的背景。关于连分数的进一步讨论， 可参阅 [2] 。

续分数的表达式为

\[ \begin{equation} \begin{aligned} &\frac{a_1}{q_1+\frac{a_2}{q_2+\frac{a_3}{\cdots\frac{\ }{q_{m-1}+\frac{a_m}{q_m}}}}}\\ &=a_1/(q_1+a_2/(q_2+a_3/(\cdots/q_{m-1}+a_m/q_m)\cdots)) \end{aligned} \end{equation} \]

而我们感兴趣的是，上式中所有 \(a_i\) 均为 \(1\) 的情况。方便起见，我们定义

\[ \begin{equation} <q_0,q_1,\cdots,q_m>=q_0+1/(q_1+1/(q_2+1/(\cdots/q_{m-1}+1/q_m)\cdots)) \end{equation} \]

例如，\(<0,2,1,3> =0+1/(2+1/(1+1/3))=4/11\) 。称 \(<0,2,1,3>\) 为 \(\frac{4}{11}\) 的续分数展开式

正有理数 \(f\) 的续分数展开式是通过减去 \(f\) 的整数部分，然后不断对余下部分取倒数再减去整数部分，直到小数部分为零为止。设 \(qi\) 为整数商，\(r\) 为第 \(i\) 步余下的小数，\(m\) 为反转的步数：

\[ \begin{equation} \begin{aligned} &q_0=\lfloor f\rfloor, \quad r_0=f-q_0, 且\\ &q_i=\lfloor \frac{1}{r_{i-1}}\rfloor,\quad r_i=\frac{1}{r_{i-1}}-q_i,\quad (i=1,2,\cdots,m) \end{aligned} \end{equation} \]

因为 \(r_m=0\)，我们有 \(f=\langle q_0,q_1,\cdots,q_m\rangle\) 。此处可以得出两点结论，它们稍后会很有用的。第一， \(q_m\geq2\)。若 \(q_m=1\) 会推出 \(r_{m-1}=1\) ，这是不可能的，故得证。第二个结论是，对任意 \(x>0\)：

\[ \begin{equation} \begin{aligned} \langle q_0,q_1,\cdots,q_m\rangle <\langle q_0,q_1,\cdots,q_m+x\rangle,\\ &若 m 是偶数,\\ \langle q_0,q_1,\cdots,q_m\rangle >\langle q_0,q_1,\cdots,q_m+x\rangle,\\ &若 m 是奇数. \end{aligned} \end{equation} \]

这可以通过查看 (2) 式中分数嵌套的层数看出。

现在我们开始思考如何通过 \(f\) 的续分数展开式构造出 \(f\) 。利用 (2) 式，可以从 \(q_m\) 开始，每步不断加和求倒数，直到回到 \(q_0\) ，以得到 \(f\)。不过，要是能从 \(q_0\) , 开始重建 \(f\) 就很好了。设 \(n_i\) 和 \(d_i\) （其中 \(i=0,1,\cdots,m\)）分别为一系列被定义为如下形式的分子和分母：

\[ \begin{equation} \begin{aligned} \frac{n_i}{d_i}=\langle q_0,q_1,\cdots,q_i\rangle,\quad \gcd(n_i,d_i)=1\\ &i=0,1,\cdots,m\\ \end{aligned} \end{equation} \]

可以写成如下形式：

\[ \begin{equation} \begin{aligned} &n_0=q_0, &&d_0=1,\\ &n_1=q_0q_1+1, &&d_1=q_1,\\ &n_i=q_in_{i-1}+n_{i-2}, &&d_i=q_id_{i-1}+d_{i-2},\\ &&&\qquad i=2,3,\cdots,m. \end{aligned} \end{equation} \]

这样，通过分式 \(f=\frac{n_m}{d_m}\) 就可以构造出 \(f\) 来了。

上述的分子分母 \(n,d\) 之间有下列在后面很有用的关系，可以证明：

\[ \begin{equation} n_id_{i-1}-n_{i-1}d_i=-(-1)^i,\quad i=1,2,\cdots,m \end{equation} \]

现在，我们已经介绍了足够的连分数背景知识，以供讨论连分数算法。

III. 续分数算法

设 \(f'\) 是 \(f\) 的低估值：

\[ \begin{equation} f'=f(1-\delta), \quad\delta \geq 0 \end{equation} \]

设 \(q_i\)，\(r_i\)，和 \(q'_i\)，\(r'_i\)，分别是 \(f\) 和 \(f'\) 的第 i 个商和因数。若 \(\delta\) 足够小，那么可以下面的算法求出 \(f\) 的分子和分母。重复以下步骤，直到找到 \(f\) 为止：

  • 生成 \(f'\) 的续分数展开式的下一个商（\(q_i'\)）。
  • 用 (6) 式构造分式使之等于 \[ \begin{aligned} &\langle q_0',q_1',\cdots, q_{i-1}',q_i'+1,\rangle, \qquad&i 为偶数,\\ &\langle q_0',q_1',\cdots,q_{i-1}',q_i',\rangle, \qquad&i 为奇数. \end{aligned} \]
  • 检查构造的分式是否等于 \(f\) 。

在第偶数个商的值上加 \(1\) 的原因是，\(f\) 的猜测值应该大于 \(f'\) ，因为 \(f \geq f'\)。这点可以在 (4) 式中由 \(\langle q'_0,q'_1,\cdots,q'_{i-1},q_i'\rangle\) 小于 \(\langle q'_0,q'_1,\cdots,q'_{i-1},q_i'+r'_i\rangle\) 看出。注意为了确定 \(f\) 的猜测值是否正确，必须对其进行检验。

若

\[ \begin{equation} \begin{aligned} &\langle q_0,q_1,\cdots, q_{m-1},q_m-1,\rangle<f'\leq \langle q_0,q_1,\cdots, q_m\rangle, \qquad&i 为偶数,\\ &\langle q_0,q_1,\cdots,q_{m-1},q_m+1,\rangle<f'\leq \langle q_0,q_1,\cdots, q_m\rangle, \qquad&i 为奇数. \end{aligned} \end{equation} \]

成立，那么续分数算法就是正确的。

现在考虑 (9) 式关于 \(\delta\) 的大小的推论。在 (8) 式解得

\[ \begin{equation} \delta =1-\frac{f'}{f} \end{equation} \]

分别分析以下的几种情况：\(m=0\)， \(m=1\) ，\(m\) 为大于等于 \(2\) 的偶数，\(m\) 为大于等于 \(3\) 的奇数。

  • 情况 1：\(m=0\)。

    用 (9) 式代换 (10)式中的 \(f'\) ：

    \[ \begin{equation} \delta<1-\frac{\langle q_0-1\rangle}{\langle q_0\rangle} \end{equation} \]

    利用 (2) 式，可将其简化为 \(\delta < 1/q_0\)，并可重写为（请注意 \(n_0 = q_0\) 和 \(d_0 = 1\)）

    \[ \begin{equation} \delta<\frac{1}{n_0d_0} \end{equation} \]

  • 情况 2：\(m=1\)。

    用 (9) 式代换 (10)式中的 \(f'\) ：

    \[ \begin{equation} \delta<1-\frac{\langle q_0,q_1+1\rangle}{\langle q_0,q_1\rangle} \end{equation} \]

    利用 (2) 式，可以有：

    \[ \begin{equation} \delta<\frac{1}{(q_0q_1+1)(q_1+1)} \end{equation} \]

    前面已经证明 \(q_m \geq 2\) ，这意味着此时 \(\frac{3}{2}q_1\geq q_1+1\)。结合 (14) 式以及 (6)式中的 \(n_1\) 和 \(d_1\) 表达式，有：

    \[ \begin{equation} \delta=\frac{1}{\frac{3}{2}n_1d_1} \end{equation} \]

    足以保证续分数算法的成功。

  • 情况 3：\(m\) 为大于等于 \(2\) 的偶数。 用 (9) 式代换 (10)式中的 \(f'\) ：

    \[ \begin{equation} \delta<1-\frac{\langle q_0,q_1,\cdots,q_{m-1},q_m-1\rangle}{\langle q_0,q_1,\cdots,q_m\rangle} \end{equation} \]

    利用 (6) 式，有：

    \[ \begin{equation} \begin{aligned} \langle q_0,q_1,\cdots,q_{m-1},q_m-1\rangle&=\frac{(q_{m}-1)n_{m-1}+n_{m-2}}{(q_{m}-1)d_{m-1}+d_{m-2}}\\ \langle q_0,q_1,\cdots,q_m\rangle&=\frac{q_{m}n_{m-1}+n_{m-2}}{q_{m}d_{m-1}+d_{m-2}} \end{aligned} \end{equation} \]

    将上面的表达式代入到 (16) 式：

    \[ \begin{equation} \delta<\frac{n_{m-1}d_{m-2}-n_{m-2}d_{m-1}}{(q_mn_{m-1}+n_{m-2})(q_md_{m-1}+d_{m-2}-d_m-1)} \end{equation} \]

    利用 (7) 式及 (6) 式中 \(nm\) 和 \(d_m\) 的表达式，得：

    \[ \begin{equation} \delta<\frac{1}{n_m(d_m-d_{m-1})} \end{equation} \]

    因此

    \[ \begin{equation} \delta<\frac{1}{n_md_m} \end{equation} \]

    足以保证续分数算法的成功。

  • 情况 4：\(m\) 为大于等于 \(3\) 的奇数。 和情况 3 中进行类似的分析，得

    \[ \begin{equation} \delta<\frac{1}{n_m(d_m+d_m-1)} \end{equation} \]

    由 \(d_m=q_md_{m-1}+d_{m-2}\) 且 \(q_m\geq2\) ，有 \(d_m+d_{m-1}\leq \frac{3}{2}d_m\) 。因此，

    \[ \begin{equation} \delta<\frac{1}{\frac{3}{2}n_md_m} \end{equation} \]

    足以保证续分数算法的成功。

综合考虑上面提到的四种情况：

\[ \begin{equation} \delta <\frac{1}{\frac{3}{2}n_md_m} \end{equation} \]

足以保证续分数算法的成功。这里的 \(n_m,d_m\) 就是前面提到过的 \(f\) 的分子和分母。

现在考虑续分数算法执行的花费时间。设 \(x=\max(n_m,d_m)\) ，\(f\) 的续分数展开式中除计算的数量可被表示为 \(O(\log x)\) 。每次除计算后，会得到并检验一个 \(f\) 的猜测值。算式要求每次得到的 \(f\) 的猜测值是 \(\log x\) 的多项式。因此，假设 \(f\) 的检验在 \(\log x\) 的多项式中是正确的，那么续分数算法执行花费的时间就是 \(\log x\) 的多项式。

IV. 在 RSA 上应用续分数算法

在 [5] 中给出了公共指数 \(e\) 和秘密指数 \(d\) 的关系：

\[ \begin{equation} ed\equiv1\mod LCM(p-1,q-1) \end{equation} \]

这种关系对于公开指数和秘密指数互为倒数的指数运算来说是必要的。根据 (24)，必定存在一个整数 K，使

\[ \begin{equation} ed=K\cdot LCM(p-1,q-1)+1 \end{equation} \]

若令 \(G=\gcd(p-1,q-1)\) ，由 \(lcm(p-1,q-1)=\frac{(p-1)(q-1)}{G}\) 得

\[ \begin{equation} ed=\frac{K}{G}(p-1)(q-1)+1 \end{equation} \]

\(K\) 和 \(G\) 有可能有共同的因子。我们定义 \(k = \frac{K}{\gcd(K，G)}\) 和 \(g=\frac{G}{\gcd(K,G)}\)。那么有

\[ \begin{equation} ed=\frac{k}{g}(p-1)(q-1)+1 \end{equation} \]

把 (27) 式同时除以 \(dpq\)：

\[ \begin{equation} \frac{e}{pq}=\frac{k}{dg}(1-\delta),\qquad 其中\ \delta=\frac{p+q-1-\frac{g}{k}}{pq} \end{equation} \]

需要注意 \(\frac{e}{pq}\) 是完全由公开信息构成的，且是对 \(\frac{k}{dg}\) 的近似低估。在使用续分算法之前，我们必须记住这种算法总是能找到最小项的分数。由 (25) 可知，\(\gcd(K, d) = 1\)。因为 \(k\) 整除 \(K\)，所以 \(\gcd(k, d) = 1\)。根据定义，\(\gcd(k，g)= 1\)。因此，\(gcd(k，dg)= 1\) ，故而只要 \(\delta\) 足够小就可以使用续分数算法求出 \(k\) 和 \(dg\)。

通过 (28) 式中的 \(\delta\) 表达式和 (23) 式对 \(\delta\) 的限制，可以证明

\[ \begin{equation} kdg<\frac{pq}{\frac{3}{2}(p+q)} \end{equation} \]

对求出 \(k\) 和 \(dg\) 是充分的。注意 \((-1-\frac{g}{k})\) 在 \(\delta\) 的表达式中被舍弃了，因为其相对于 \((p+q)\) 是很小的。这不会影响 (29) 式的有效性，因为 \(-1-\frac{g}{k}\) 在算式中只会减小 \(\delta\) 的大小。

现在，我们将考虑如何检验 \(k\) 和 \(dg\) 的猜测是正确的。为了简化测试，我们假设 \(ed > pq\)。这并不是一个特别严格的假设，因为当 \(e\) 或 \(d\) 固定时，另一个的期望值约为 \(pq / G\)（回顾 \(G = \gcd(p - 1, q - 1)\)。除非 G 选得很大，否则 \(ed>pq\) 的可能性很大。根据 (27) 式，\(ed > pq\) 的结果是 \(k>g\) 。重写(27)式成：

\[ \begin{equation} edg=k(p-1)(q-1)+g \end{equation} \]

可以看到，只要 \(k>g\) ,那么用 \(k\) 除 \(edg\) 就有商 \((p-1)(q-1)\) 余 \(g\) 。这就给了我们一个 \((p-1)(q-1)\) 和 \(g\) 的猜测。如果 \((p-1)(q-1)\) 是 \(0\)，那么 \(k\) 和 \(dg\) 的值都是错误的。这种情况必须被过滤掉，不然该测试就会把 \(pq\) 分解为 \(1\) 和 \(pq\)。通过下列等式，我们可以用 \((p-1)(q-1)\) 的猜测值来猜测 \(\frac{p+q}{2}\) ：

\[ \begin{equation} \frac{pq-(p-1)(q-1)+1}{2}=\frac{p+q}{2} \end{equation} \]

若 \(\frac{p+q}{2}\) 的值不是整数，则 \(k\) 和 \(dg\) 的值都是错误的。通过下式，可以用 \(\frac{p+q}{2}\) 的猜测值来猜测 \((\frac{p-q}{2})^2\)：

\[ \begin{equation} (\frac{p+q}{2})^2-pq=(\frac{p-q}{2})^2 \end{equation} \]

若 \((( p - q)/2)\) 的猜测是完全平方，那么原来对 \(k\) 和 \(dg\) 的猜测就是正确的。用 \(dg\) 除以 \(g\) 可以求出秘密指数 \(d\) 。如前所述，\(g\) 是 \(edg\) 除以 \(k\) 的余数。我们也能通过 \(\frac{(p+q)}{2}\) 和 \(\frac{(p-q)}{2}\) 轻松地算出 \(p\) 和 \(q\) 的值。

如果不采取任何措施对抗这种 RSA 上的续分数攻击，那么就可以期望 \(g\) 很小且 \(g<dg\)。在这种条件下，由 (29) 式可知，二进制位数不大于大约模数四分之一比特位数的秘密指数可以在多项式时间内找到。这种攻击无法扩展到秘密指数与模的大小大致相同的正常情况，因为它依赖于公共指数提供信息来对模数进行因数分解，而在正常情况下，公共指数的选择几乎与模无关。

V. 例子

在这一部分，我们给续分数算法中放入一组很小的 RSA 密钥对：

\[ pq=8927\quad e= 2621 \]

\(\frac{e}{pq}=\frac{2621}{8927}\) 的续分数展开式如表 I。

需要求的量 计算方法 \(i=0\) \(i=1\) \(i=2\)
\(q'_i\) 见 (3) 式 \(0\) \(3\) \(2\)
\(r_i'\) 见 (3) 式 \(\frac{2621}{8927}\) \(\frac{1064}{2621}\) \(\frac{493}{1064}\)
\(\frac{n_i'}{d_i'}=\langle q_0',q_1',\cdots,q_i'\rangle\) 见 (6) 式 \(\frac{0}{1}\) \(\frac{1}{3}\) \(\frac{2}{7}\)
\(\frac{k}{dg}\) 的估值 \(\langle q_0',q_1',\cdots,q'_{i-1},q_i'+1\rangle\quad(偶数)\\\langle q_0',q_1',\cdots,q_i'\rangle\quad(奇数)\) \(\frac{1}{1}\) \(\frac{1}{3}\) \(\frac{3}{10}\)
\(edg\) 的估值 \(e\cdot dg\) \(2621\) \(7863\) \(26210\)
\((p-1)(q-1)\) 的估值 \(\lfloor\frac{edg}{k}\rfloor\) \(2621\) \(7863\) \(8\)
\(g\) 的估值 \(edg\mod k\) \(0\) \(0\) \(2\)
\(\frac{p+q}{2}\) 的估值 见 (31) 式 \(3153.5\) \(532.5\) \(96\)
\((\frac{p-q}{2})^2\) 见 (32) 式 退出 退出 \(289=17^2\)
\(d\) \(\frac{dg}{g}\) \(5\)

在本例中，RSA 续分数攻击的结果是：

\[ d=8927\quad, p=113\quad,q=79\quad, k=3\quad, g=2\quad. \]

通过将值代入 (27) 式验证，可以知道 \(d=5\) 就是 \(e=2621\) 对应的密钥。还可以验证，算法成功的充分条件 (29) 式得到了满足。

这个例子展现了对 RSA 进行续分数攻击的细节，但考虑一个更现实的情况也很有用。假设在 RSA 算法中用了一个 \(1024\) 比特（bit）的模数，那么 \(p, q\) 的大小约为 \(2^{512}\)。假设 \(g=2\)，且 \(e\approx pq\)，则 \(k\approx dg\)（见(28) 式）。那么利用 (29) 式，可以看到续分数攻击可以找到最大约为 \(2^{255}\) 的密钥。

VI. 对抗 RSA 的续分数攻击

有两种方法可以减少可以使用 RSA 续分数攻击找到的秘密指数的最大值。由 (29) 式可知，这两种方法就是让 \(k\) 变大或让 \(g\) 变大。

要使 \(k\) 增大，就必须让公共指数 \(e\) 增大（见 (27)式）。这可以通过在 \(e\) 上添加 \(lcm (p-1，q-1)\) 的倍数来实现。假设 \(e>(pq) ^{1.5}\) ,可以推出 \(\frac{k}{dg}>(pq)^{0.5}\) （见 (28) 式）。将 \(k=dg(pq)^{0.5}\) 代入到 (29) 式，得到 \(d<1\) 。因此，若 \(e>(pq) ^{1.5}\) ，续分数算法就不能保证对任意大小的秘密指数均有效了。增大 \(e\) 的大小有其弊端，这会导致公钥加密花费的时间增多。但是这在一些系统中是可以接受的。

要使 \(g\) 更大，必须选择 p 和 q 使得 \(\gcd (p-1，q-1)\) 很大。但是，我们稍后可以看到，在特定条件下有些方法可以找出 \(g\) 或 \(g\) 的因子。

VII. 改善攻击算法

在这一节，我们讨论四种针对短秘密指数攻击的可能改善方法。第一个改善是允许续分数算法稍微越过 (29) 式的限制持续搜寻 \(d\)。算法只能保证在限制内一定有效，但是略微超出限制也可能有效。这能让找到的（最大）秘密指数位长增加一位左右。

第二种改善基于下面的观察：\(\frac{k}{dg}\) 的低估值 \(\frac{e}{pq}\) ，其分母就是对 \((p-1)(q-1)\) 的高估值。一个更贴近 \((p-1)(q-1)\) 的估值是：

\[ \lfloor(\sqrt{pq}-1)^2\rfloor \]

使用此估值，(29) 式变成

\[ kdg<\frac{2}{3}(\frac{\sqrt{pq}-1}{\sqrt{p}-\sqrt{q}})^2. \]

这可以提高可以找到的秘密指数大小。此项改进提高的量随 \(|p-q|\) 的减小而提高。

第三个 RSA 上的续分数攻击改善方法是，对 \(\frac{k}{dg}\) 的多个猜测值执行该算法。我们可以从某个猜测值开始，然后逐步尝试更大的猜测值。这样一来，我们就等于对 \(\frac{k}{dg}\) 进行了线性搜索。对于最大为 (29) 式中限制大小的秘密指数，此算法消耗多项式时间。而当秘密指数的位长增长超过限制，算法执行的次数就呈指数增长。

第四个改善是尝试寻找 \(g\) 或 \(g\) 的因子。假设 \(t\) 是 \(g\) 的一个已知因子，那么我们可以用

\[ t\left(\frac{e}{pq}\right) 作为\frac{k}{d(\frac{g}{t})}的低估值。 \]

这种情况下，(29) 式就变成了

\[ kd\left(\frac{g}{t}\right)<\frac{pq}{\frac{3}{2}(p+q)} \]

\(d\) 的大小的增加可以通过 \(t\) 的一个因子找到。我们需要一种方法找到 g 的所有因子。因为 \(g\) 整除 \(\gcd(p-1)(q-1)\), 且 \(g\) 也整除 \(p-1\) 和 \(q-1\)，那么 g 也整除 \(pq-1\)，因为

\[ pq-1=(p-1)(q-1)+(p-1)+(q-1) \]

一种可能的寻找 \(g\) 的所有因数的办法是因数分解 \(pq-1\)。如果 \(g\) 选择得很大且 \(g\) 的所有质因子都很大，那么通过分解 \(pq-1\) 寻找 \(g\) 的因数可能会很困难。但是，如果 \(g\) 足够大，从而使 \(\frac{p-1}{g}\) 和 \(\frac{q-1}{g}\) 很小，我们就可以通过寻找 \(\frac{p-1}{g}\) 和 \(\frac{q-1}{g}\) 的可能值来找到 \(g\)。

VIII. 悬而未决的问题

使用短秘密指数的主要原因是减少密钥做指数时（消耗）的时间。要减少密钥做指数消耗的时间，一种有效的办法是利用 \(p\) 和 \(q\)（而不仅仅是乘积 \(pq\)）的知识 [4]。利用这种方法，需要执行两次一半位长的指数计算。第一次指数计算使用指数 \(d_p=d\mod{p-1}\)，得出模 \(p\) 后的结果。第二次则使用指数 \(d_q=d\mod{q-1}\) 得出模 \(q\) 的结果。这两个结果结合在一起，可以通过中国剩余定理轻松地得到最终的模 \(pq\) 的结果。我们可以通过选择 \(d\) 使得 \(d_p\) 和 \(d_q\) 都很短，从而进一步的减少密钥指数运算的时间。一个有趣的公开问题是，在 \(d_p\) 和 \(d_q\) 都很短但是不相等的时候，是否存在一种 RSA 攻击。

另一个未解决的问题是于公共指数的位长有关。本论文前面描述的攻击在选择的公共指数至少比模数 \(pq\) 长 \(50\%\) 时会无效。对某些系统而言，为了快速的密钥计算，这是可以承担的小代价。一个有趣的问题是，当秘密指数很小但是公共指数比模数还大时，是否存在一种 RSA 攻击。

IX. 结论

续分数算法可以在多项式时间内找到足够短的 RSA 秘密指数。一种典型的情况是，\(e<pq\)，\(\gcd(p-1,q-1)\) 很小，且 \(p\) 和 \(q\) 位长大致相等，此算法就可以找到位长最大约为模数的四分之一的秘密指数。

有很多种办法对抗 RSA 上的续分数攻击。如果 \(e>(pq)^{1.5}\) ，那么续分数算法对任何位长的秘密指数都无法保证有效。同时我们也可以选择让 \(\gcd(p-1,q-1)\) 很大，因为能找到的秘密指数长度与 \(\gcd(p-1,q-1)\) 成反比。不过，让 \(\gcd(p-1,q-1)\) 变大可能会导致其它的问题。

我们还讨论了若干 RSA 上的续分数攻击的改善方法。但是，在多项式时间内搜寻时，它们只能让能找到的最大秘密指数长度增加些许几位。因为当秘密指数的长度增长到超过最大限度时，寻找秘密指数的时间需求会呈指数增长。此攻击无法拓展到通常的情况，即秘密指数与模数大致有一样的位长。

参考文献

  1. J. Hastad. “On using RSA with low exponent in a public key network,” Lecture Notes in Computer Science: Advances in Cryptology-CRYPT0 ’85 Proceedings. New York: Springer-Verlag, pp.403-408.
  2. D. E. Knuth, Art of Computer Programming Vol. 2/Seminumerical algorithms. New York: Addison Wesley, 1969.
  3. J. M. Pollard. “Theorems on factorization and primality testing,”Proc. Cambridge Philos. Soc., vol. 76, 1974, pp. 521-528.
  4. J. J. Quisquater and C. Couvreur, “Fast decipherment algorithm for RSA public-key cryptosystem,” Electron. Lett., vol. 18, no. 21,pp. 905-907, Oct. 1982.
  5. R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public key cryptosystems.” Commun. ACM.vol. 21, no. 2, pp. 158-164, Feb. 1978.
  6. H. C. Williams, “A p + 1 method of factoring,” Muthemutics of Computation, vol. 39, no. 159, pp. 225-234, July 1982.