二十年以來對 RSA 密碼系統攻擊綜述

原文：Twenty Years of Attacks on the RSA Cryptosystem

作者：Dan Boneh@Stanford University(dabo@cs.stanford.edu)

譯者：Jing Ling@360ESG A-Team(admin@hackfun.org)

1 介紹

由Ron Rivest，Adi Shamir和Len Adleman發明的RSA密碼系統首次在1977年8月的"科學美國人"雜志上發表（譯者注：本文于1999年2月在美國數學學會的Notices雜志首次發布）。密碼系統最常用于提供隱私保護和確保數字數據的真實性。目前，RSA部署在許多商業系統中。Web服務器和瀏覽器使用它來保護Web流量，它可以用于保障電子郵件的隱私和真實性，還可以用于保護遠程登錄會話，同時它也是電子信用卡支付系統的核心。簡而言之，RSA常用于需要考慮數字數據安全性的應用中。

自最初發布以來，RSA系統已被許多研究人員分析認為是易受攻擊的。盡管二十年的研究出了許多引人入勝的攻擊，但其中沒有一個攻擊是毀滅性的。這些攻擊主要說明了不當使用RSA的危險，可見安全地實施RSA確實也是一項非常重要的任務。我們的目標是使用基礎數學的知識分析其中的一些攻擊，在整個分析過程中，我們遵循標準命名約定，使用Alice和Bob表示希望彼此通信的兩個正常通信方，使用Marvin來表示希望竊聽或篡改Alice和Bob之間通信的惡意攻擊者。

我們首先介紹一下RSA加密的簡化版本。令$N = pq$是比特位長度相同($n/2$位)的兩個大素數的乘積。常見$N$的長度大小是$n$=1024位（即：309個十進制數字），質因子$p,q$=512位。令$e,d$為滿足$ed = 1\ \text{mod}\ \varphi(N)$的兩個整數，其中$\varphi\left( N \right) = (p - 1)(q - 1)$是乘法群$\mathbb{Z}_{N}^{*}$的階數。我們稱$N$為RSA模數，$e$為加密指數，$d$為解密指數。$\left\langle N,e \right\rangle$為公鑰。顧名思義，公鑰是公開的，并用于加密消息。$\left\langle N,d \right\rangle?$稱為密鑰或私鑰，一般情況下只有加密消息的接收者知道，私鑰能夠解密密文。

消息$M$是一個整數且滿足$M \in \mathbb{Z}_{N}^{*}$，要加密$M$，計算$C = M^{e}\ \text{mod}\ N$，要解密密文合法接受者計算$M = C^{d}\ \text{mod}\ N$。（譯者注：下面是譯者添加的$M = C^{d}\ \text{mod}\ N$的證明）

歐拉定理：若$a,n$為正整數，且$a,n$互素（即$\gcd\left( a,n \right) = 1$），則$a^{\varphi(n)} = 1\ \ \text{mod}\ n$。

已知$\ 1 = \ ed\ \ \text{mod}\ \varphi(n)$，$m < n$，$c = m^{e}\ \text{mod}\ n$，$\gcd\left( m,n \right) = 1$，求證$m = c^{d}\ \text{mod}\ n$。

證明：

等式左邊為$m$

等式右邊為$c^{d}\ \text{mod}\ n$

$$\because c = m^{e}\ \text{mod}\ n$$

$$\therefore c^{d}\ \text{mod}n = {(m^{e}\ \text{mod}\ n)}^{d}\ \ \text{mod}\ n = m^{ed}\ \ \text{mod}\ n$$

$$\because 1 = \ ed\ \ \text{mod}\text{\ φ}\left( n \right)$$

$$\therefore ed = k\varphi\left( n \right) + 1$$

$$\therefore c^{d}\ \text{mod}\ n = m^{ed}\ \ \text{mod}\ n = m^{\text{kφ}\left( n \right) + 1}\ \ \text{mod}\ n = m{(m^{\varphi(n)})}^{k}\ \ \text{mod}\ n$$

$$\because\gcd\left( m,n \right) = 1$$

$$\therefore m^{\varphi(n)} = 1\ \ \text{mod}\ n$$

$$\therefore c^{d}\ \text{mod}\ n = m{(m^{\varphi(n)})}^{k}\ \ \text{mod}\ n = m{(1\ \ \text{mod}\ n)}^{k}\ \ \text{mod}\ n = m{(1)}^{k}\ \ \text{mod}\ n = m\ \ \text{mod}\ n$$

$$\because m < n$$

$$\therefore m\ \text{mod}\ n = m$$

$$\therefore c^{d}\ \text{mod}\ n = m\ \ \text{mod}\ n = m$$

等式右邊等于等式左邊，證畢。

定義一個RSA函數$x \longmapsto x^{e}\text{modN}$，如果$d$已知，很容易使用等式$m = c^{d}\ \text{mod}\ n$求出$x$，我們稱$d$為求解函數的陷門。在本次課題研究在沒有陷門$d$的情況下求解RSA函數，更準確的說，給一個三元組$\left\langle N,e,C \right\rangle$，我們知道在不知道$N$的因子想計算$C$模$N$的$e$根是非常困難的。因為$\mathbb{Z}_{N}^{*}$是有限集，因此可以枚舉$\mathbb{Z}_{N}^{*}$的所有元素直到找到$M$。遺憾的是，這將導致算法具有$N$階的運行時間，即其輸入大小的指數，其為$\mathrm{\log}_{2}N$的階數。我們對運行時間更低的算法感興趣，即$n^{c}$的階數（其中$n = \mathrm{\log}_{2}N$）或者$c$是一些小的常數（比如說小于5）。實踐表明這些算法通常在所討論的輸入情況表現良好，在整篇論文中，我們將此類算法稱為高效算法。

此次課題我們主要研究RSA函數而不是RSA密碼系統。籠統地說，隨機輸入上求解RSA函數的應該是非常困難的，也就是意味著給定$\left\langle N,e,C \right\rangle$攻擊者無法計算出明文$M$。這還不夠，密碼系統必須抵御更微妙的攻擊。如果給出$\left\langle N,e,C \right\rangle$，想從$M$中計算出任何信息應該是非常難的，這被稱為語義安全。我們不討論這些微妙的攻擊，但是必須指出的是如上所述的RSA在語義上是不安全的：給定$\left\langle N,e,C \right\rangle$，可以容易地推導出關于明文$M$的一些信息（例如，可以容易地從$C$推導出$N$上的$M$的雅可比符號）。通過向加密過程添加隨機處理流程，可以保障RSA在語義上的安全性。

RSA函數$x \longmapsto x^{e}\text{modN}$是一個單向陷門函數，正向它可以很容易地計算，但是（據我們所知）除非在特殊情況下，否則在沒有陷門$d$的情況下不能有效地反向求解的。單向陷門函數可用于數字簽名，數字簽名可以保障電子文件的真實性和不可否認性。例如，它們用于簽署數字支票或電子采購訂單。為了使用RSA對消息$M \in \mathbb{Z}_{N}^{*}$進行簽名，Alice使用其私鑰$\left\langle N,d \right\rangle$簽名$M$并獲得簽名$S = M^{d}\ \text{mod}\ N$。給定$\left\langle M,S \right\rangle$之后任何人都可以驗證$M$上的Alice簽名通過$M = S^{e}\ \text{mod}\ N$。因為只有Alice可以生成$S$，人們可能會認為攻擊者無法偽造Alice的簽名。然而事情并非如此簡單，為了保障簽名的安全還需要一些額外的措施。數字簽名是RSA的重要應用，此次課題我們也會研究一些針對RSA數字簽名的攻擊。

RSA密鑰對可以這樣生成，選取兩個隨機$\frac{n}{2}$位素數并將它們相乘以獲得$N$來生成。然后，對于給定的加密指數$e < \varphi(N)$，使用擴展歐幾里德算法計算$d = e^{- 1}\mathrm{\ \text{mod}}\ \varphi(N)$。由于素數集是足夠密集的，因此可以通過重復選擇隨機$\frac{n}{2}$位整數并使用概率素性測試對每個素數進行素性測試來快速生成隨機$\frac{n}{2}$位素數。

1.1 大數分解

給了RSA公鑰$\left\langle N,e \right\rangle$，首先想到的攻擊就是分解模數$N$，給了$N$的因子攻擊者可以計算得到$\varphi(N)$，從而也可以計算得到解密指數$d = e^{- 1}\ \text{mod}\ \varphi(N)$，我們稱這種分解模數的方法為針對RSA的暴力攻擊。雖然分解算法已經穩步改進，但是在正確使用RSA情況下，當前的技術水平仍遠未對RSA的安全性構成威脅。大整數分解是計算數學之美，不過本文研究主題并不是大整數分解。為完整起見，我們順便提一下，目前普通數字域篩法是效率最高的分解方法。分解$n$位整數需要時間為$\exp\left( ((c + o(1))n^{\frac{1}{3}}\mathrm{\log}^{\frac{2}{3}}n) \right)$其中$c < 2$，對RSA進行攻擊的方法花費時間超過這個范圍就那么吸引人了，比如暴力搜索$M$方法，還有一些RSA發布不久后的舊方法。

我們的目的是研究在不直接分解RSA模數$N$情況下解密消息的攻擊方法，值得注意的是，一些RSA模數的稀疏集，$N = pq$可以很容易地被分解，舉個例子，如果$p - 1$是乘積的質因子且小于$B$，那么在小于$B^{3}$時間內分解$N$。

如上所述，如果存在有效的因式分解算法，則RSA是不安全的，反之亦然。這是一個由來已久的公開問題：必須要有一個$N?$的因子才能有效地計算$e^{th}?$模$N?$的根數？破解RSA和因式分解一樣難嗎？我們在下面提出了具體的開放性問題。

開放性問題 1

給定$N$和$e$滿足$\gcd\left( e,\varphi\left( N \right) \right) = 1$，定義$f_{e,N}$函數：$\mathbb{Z}_{N}^{*} \rightarrow \mathbb{Z}_{N}^{*}$，$f_{e,N}\left( x \right) = x^{\frac{1}{e}}\mathrm{\ \text{mod}}\ \ N$。是否有多項式時間算法$A$來計算給定$N$的因子以及對于某個$e$求得$f_{e,N}\left( x \right)$的一個諭言？

$f\left( x \right)$的諭言用于評估在單位時間內任何輸入$x$的函數，最近Boneh和Venkatesan提供的證據表明，在$e$比較小的情況下，上述問題的答案可能是否定的。換句話說，在$e$比較小的情況下，可能不存在從分解到破解RSA的多項式時間縮減。他們通過實驗表明在某個模型中對小$e$的問題的肯定答案會產生一個有效的因式分解算法。我們注意到，對開放問題1的肯定回答會引起對RSA的"選擇密文攻擊"。因此，否定的回答可能才是大家喜聞樂見的。

接下來，我們證明公開私鑰$d$和分解$N$是等價的。由此可見，對于知道$d$的任何一方來說，隱藏$N$的因式分解是沒有意義的。

事實1

$\left\langle N,e \right\rangle$為RSA的公鑰，給定私鑰$d$可以有效地分解模數$N = pq$。相反地，給定$N$的因式分解，可以有效地算出私鑰$d$。

證明

$N$的因式分解得到$\varphi\left( N \right)$，因為$e$已知的，那么可以算出$d$，反之亦然。我們現在證明給定$d$可以分解$N$。給定$d$，計算$k = de - 1$。根據$d$和$e$的定義我們知道$k$是$\varphi\left( N \right)$的倍數。由于$\varphi\left( N \right)$是偶數，$k = 2^{t}r$其中$r$為奇數且$t \geq 1$。對于每個$g \in Z_{N}^{*}$都有$g^{k} = 1$，因此$g^{k/2}$是單位模$N$的平方根。根據中國剩余定理，1有四個平方根模$N = pq$。其中兩個平方根是$\pm 1$，另外兩個是$\pm x$，其中$x$滿足$x = 1\mathrm{\ \text{mod}}\ p$和$x = - 1\mathrm{\ \text{mod}}\ q$。用這最后兩個平方根中的任意一個，通過計算$\mathrm{\gcd}(x - 1,N)$來揭示$N$的因式分解。一個直截了當的論證表明，如果從$Z_{N}^{*}$中隨機選擇$g$，那么序列中的一個元素$g^{k/2}$，$g^{k/4}$,...，$g^{k/2^{t}}\ \text{mod}\ N$是統一平方根的概率至少為1/2，從而揭示了$N$的分解，序列中的所有元素可以在時間$O(n^{3})$內有效地計算，其中$n = \log_2N$。

2 基本攻擊

我們首先描述一些老的基本攻擊，這些攻擊說明了RSA的公然濫用情況。雖然存在許多這樣的攻擊，但我們僅舉兩個例子。

2.1 共模

為了避免為每個用戶生成不同的模數$N = pq$，人們可能希望一勞永逸地固定使用一個$N$，所有用戶都使用相同的$N$。可信的中央機構可以向用戶$i$提供唯一的一對$e_{i}$，$d_{i}$，用戶$i$從其中生成公鑰$\left\langle N,e \right\rangle$和私鑰$\left\langle N_{i},e_{i} \right\rangle$。

乍一看，這似乎行得通：為Alice準備的密文$C = M^{e_{a}}\mathrm{\ \text{mod}}\ \ N$無法由Bob解密，因為Bob不知道$d_{a}$。但是，這是不正確的，由此產生的系統是不安全的。事實上，Bob可以使用他自己的指數$e_{b}$，$d_{b}$來分解$N$。一旦$N$被分解，Bob就可以從她的公鑰$e_{a}$中計算出Alice的私鑰$d_{a}$。Simmons的這一觀察結果表明，RSA模不應被一個以上的實體使用。

2.2 盲化

設$\left\langle N,d \right\rangle$是Bob的私鑰，而$\left\langle N,e \right\rangle$是他相應的公鑰。假設攻擊者Marvin想要Bob在消息$M \in Z_{N}^{*}$上簽名。當然Bob不是傻瓜，他拒絕簽署$M$。但是Marvin可以嘗試以下方法：他隨機選擇一個$r \in Z_{N}^{*}$并設$M^{'} = r^{e}\text{M}\ \text{mod}\ N$。然后他讓Bob在隨機消息$M^{'}$上簽名。Bob可能愿意在看上去沒什么問題的$M$上簽名$S^{'}$，但是回想一下$S^{'} = {(M^{'})}^{d}\mathrm{\ \text{mod}}\ \ N$，Marvin現在簡單地計算$S = S^{'}/r\mathrm{\ \text{mod}}\ \ N$就得到Bob在初始$M$上的簽名$S$。

$$S^{e} = \frac{\left( S^{'} \right)^{e}}{r^{e}} = \frac{\left( M^{'} \right)^{ed}}{r^{e}} \equiv \frac{M^{'}}{r^{e}} = M(\mathrm{\ \text{mod}}\ \ N)$$

這種稱為盲化的技術使Marvin能夠在他選擇的消息上獲得有效的簽名，方法是讓Bob在隨機的"盲化"消息上簽名。Bob不知道他實際在簽名的是什么消息。由于大多數簽名方案在簽名之前對消息$M$應用"單向散列"算法，因此此種攻擊倒不是一個嚴重的問題。盡管我們將盲化描述為一種攻擊，但它實際上是實現匿名數字現金所需的一個有用屬性(可以用來購買商品的現金，但不會透露購買者的身份)。

3 低私鑰指數

為了減少加密時間（或簽名生成時間），人們可能希望使用小值$d$而不是隨機$d$。由于模冪運算需要花費線性時間為$\log_2d$，所以小$d$可以使性能提高至少10倍(對于1024位模數而言)。不幸的是，由M.Wiener發現的一種巧妙的攻擊表明，一個小的$d$會導致密碼系統完全被攻破。

定理2（M. Wiener）

令$N = \text{pq}$且$q < p < 2q$，$d < \frac{1}{3}N^{\frac{1}{4}}$，給定$\left\langle N,e \right\rangle$且滿足$ed = 1\ \text{mod}\ \varphi(N)$，攻擊者可以有效計算出$d$。

證明

證明基于使用連分數的逼近，由于$ed = 1\ \text{mod}\ \varphi(N)$，那么存在一個$k$滿足$ed - k\varphi(N) = 1$。所以，

$$\left| \frac{e}{\varphi(N)} - \frac{k}{d} \right| = \frac{1}{d\varphi(N)}$$

因此，$\frac{k}{d}$是$\frac{e}{\varphi(N)}$的逼近，盡管Marvin不知道$\varphi(N)$，但是他可能會使用$N$去近似$\varphi(N)$。因為$\varphi\left( N \right) = N - p - q + 1$（譯者注：$\varphi\left( N \right) = \left( p - 1 \right)\left( q - 1 \right) = pq - p - q + 1 = N - p - q + 1$），$p + q - 1 < 3\sqrt{N}$（譯者注：因為$q^{2} < pq = N$，所以$q < \sqrt{N}$，所以$N - \varphi\left( N \right) = p + q - 1 < 2q + q - 1 < 3q < 3\sqrt{N}$），我們有$\left| N - \varphi\left( N \right) \right| < 3\sqrt{N}$。

使用$N$替換$\varphi(N)$，我們得到：

$$\left| \frac{e}{N} - \frac{k}{d} \right| = \left| \frac{ed - kN}{\text{Nd}} \right| = \left| \frac{ed - k\varphi\left( N \right) - kN + k\varphi\left( N \right)}{\text{Nd}} \right|\text{}$$

$$= \left| \frac{1 - k\left( N - k\varphi\left( N \right) \right)}{\text{Nd}} \right| \leq \left| \frac{3k\sqrt{N}}{\text{Nd}} \right| = \frac{3k}{d\sqrt{N}}$$

現在，$\text{kφ}\left( N \right) = ed - 1 < ed$，因為$e < \varphi\left( N \right)$，我們知道$k < d < \frac{1}{3}N^{\frac{1}{4}}$（譯者注：可以得到$3k < 3d < N^{\frac{1}{4}}$和$dN^{\frac{1}{4}} > 3d^{2}$）。因此我們得到：

$$\left| \frac{e}{N} - \frac{k}{d} \right| \leq \frac{1}{dN^{\frac{1}{4}}} < \frac{1}{2d^{2}}(譯者注：有的資料寫成\frac{1}{3d^{2}})$$

這是一個經典的逼近關系，分數$\frac{k}{d}$且$d < \varphi(N)$在$\log_2N$約束內非常逼近$\frac{e}{N}$。實際上，所有類似$\frac{k}{d}$這樣的分數都是$\frac{e}{N}$的連分數展開的收斂。因此我們首要做的便是計算$\frac{e}{N}$的連分數的$\log N$收斂，其中一個連分數就等于$\frac{k}{d}$。因為$ed - k\varphi\left( N \right) = 1$，我們有$\gcd\left( k,d \right) = 1$，因此$\frac{k}{d}$是一個最簡分數。這是可以算出密鑰$d$的線性時間算法。

由于通常$N$都是1024位，因此$d$必須至少256位長才能避免這種攻擊。這對于諸如"智能卡"之類的低功耗設備來說是不幸的，因為小$d$就能節省大量能耗。 然而，并不是毫無辦法。Wiener提出了許多能夠實現快速解密并且不易受其攻擊影響的技術：

使用大$\mathbf{e}$ ：假設不是減小$e$模$\varphi\left( N \right)$，而是使用$\left\langle N,e^{'} \right\rangle$作為公鑰，其中對于某些大$t$有$e^{'} = e + t \cdot \varphi\left( N \right)$。

顯然，$e^{'}$可以代替$e$用于消息加密，當使用大的$e$值時，上述證明中的$k$不再小。一個簡單的計算表明，如果$e^{'} > N^{1.5}$，那么無論$d$多小，都無法實施上述攻擊。然而，大的$e$值將導致加密時間的增加。

使用CRT：

另一種方法是使用中國剩余定理（CRT）。假設選擇$d$使得$d_{p} = d\mathrm{\ \text{mod}}\ (p - 1)$和$d_{q} = d\mathrm{\ \text{mod}}\ (q - 1)$都很小，比如都是128位。則可以進行如下密文$C$的快速解密：首先計算$M_{p} = C^{d_{p}}\mathrm{\ \text{mod}}\ p$和$M_{q} = C^{d_{q}}\mathrm{\ \text{mod}}\ q$。

然后使用CRT計算滿足$M = M_{p}\mathrm{\ \text{mod}}\ p$和$M = M_{q}\mathrm{\ \text{mod}}\ q$的唯一值$M \in \mathbb{Z}_{N}$.

得到的$M$滿足等式$M = C_{d}\mathrm{\ \text{mod}}\ \ N$。關鍵點在于雖然$d_{p}$和$d_{q}$很小，但是$\text{d}\mathrm{\ \text{mod}}\ \varphi(N)$的值可以很大，大約在$\varphi(N)$的數量級上。因此，定理2的攻擊不再適用。我們注意到，如果給定了$\left\langle N,e \right\rangle$，則存在一種攻擊能夠使攻擊者能夠在時間$O\left( min(\sqrt{d_{p}},\sqrt{d_{q}}) \right)$內對$N$進行因子分解。因此，$d_{p}$和$d_{q}$不能太小。

我們不知道這些方法中是否都安全。我們所知道的是，Wiener攻擊對它們無效。最近由Boneh和Durfee改進的定理2證明了只要$d < N^{0.292}$，攻擊者就可以從$\left\langle N,e \right\rangle$中有效地算出$d$。這些結果表明Wiener的界限并不固定。正確的界限可能是$d < N^{0.5}$。截至撰寫本文時，還是一個尚未解決的問題。

開放性問題2

令$N = pq$，$d < N^{0.5}$，如果Marvin知道$\left\langle N,e \right\rangle$和$ed = 1\mathrm{\ \text{mod}}\ \varphi(N)$及$e < \varphi(N)$關系，他能有效算出$d$嗎？

4 低公鑰指數

為了減少加密或簽名驗證時間，通常會使用一個小的公鑰指數$e$。$e$的最小可能值為3，但為防止某些攻擊，建議使用$e = 2^{16} + 1 = 65537$。當使用值$2^{16} + 1$時，簽名驗證需要17次乘法，而使用隨機的$e \leq \varphi(N)$時則需要大約1000次乘法。與上一節的攻擊不同，當使用一個小$e$時，針對的攻擊不只是攻破而已。

4.1 Coppersmith定理

針對RSA低公鑰指數最有力的攻擊基于Copper-smith的一個定理，Coppersmith定理有很多應用，這里我們只討論其中的一些應用，證明使用LLL格基約化算法如下。

定理3（Coppersmith） 令$N$為一個整數，$f\mathbb{\in Z}\left\lbrack x \right\rbrack$是$d$次的一元多項式，設$X = N^{\frac{1}{d} - \epsilon}$其中$\epsilon \geq 0$，在給定$\left\langle N,f \right\rangle$之后Marvin能夠有效找到所有滿足$f\left( x_{0} \right) = 0\ \text{mod}\ N$的整數$\left| x_{0} \right| < X$，運行時間由在$O(w)$維數且$w = \mathrm{\min}(\frac{1}{\epsilon},\log_2N)$的格上運行LLL算法所需的時間決定。

該定理為有效地求$f$模$N$的所有小于$X = N^{\frac{1}{d}}$的根提供了一種算法，當$X$越小，算法的運行時間越短。這個定理的強大之處在于它能夠找到多項式的小根。當模數為素數時，就目前而言，找不到比使用Coppersmith定理更好的求根算法了，沒有理由不使用Coppersmith定理。

我們概述了Coppersmith定理證明背后的主要思想，我們采用由Howgrave-Graham提出的簡化方法，給定一個多項式$f\left( x \right) = \sum_{}^{}{a_{i}x^{i}\mathbb{\in Z}\left\lbrack x \right\rbrack}$，定義$\left\| h \right\|^{2} = \sum_{i}^{}{\left| a_{i} \right|^{2}}$，證明依賴于下面的觀察。

引理4

令$h\left( x \right)\mathbb{\in Z}\left\lbrack x \right\rbrack$為$d$次多項式，$X$為正整數，假設$\left\| h(xX) \right\| < \frac{N}{\sqrt{d}}$，如果$\left| x_{0} \right| < X$滿足$h\left( x_{0} \right) = 0\ \text{mod}\ N$，那么$h\left( x_{0} \right) = 0$成立。

證明 從Schwarz不等式觀察到：

$$\left| {h(x}_{0}) \right| = \left| \sum_{}^{}{a_{i}x_{0}^{i}} \right| = \left| \sum_{}^{}{a_{i}X^{i}}\left( \frac{x_{0}}{X} \right)^{i} \right| \leq \sum_{}^{}\left| a_{i}X^{i}\left( \frac{x_{0}}{X} \right)^{i} \right|$$

$$\leq \sum_{}^{}{\left| a_{i}X^{i} \right| \leq}\sqrt{d}\left\| h\left( \text{xX} \right) \right\| < N$$

因為$h\left( x_{0} \right) = 0\ \text{mod}\ N$,我們得出結論$h\left( x_{0} \right) = 0$。

引理指出，如果$h$是一個低范數多項式，則$\text{h}\mathrm{\ \text{mod}}\ \ N$的所有小根也是$h$在整數上的根。引理表明，要找到$f\left( x \right)\mathrm{\ \text{mod}}\ \ N$的一個小根$x_{0}$，我們需要尋找另一個與$f$模$N$有相同根的低范數多項式$h \in \mathbb{Z}\left\lbrack x \right\rbrack$，這樣就能容易找到$h$在整數上的根$x_{0}$。為此，我們可以尋找一個多項式$g\mathbb{\in Z}\left\lbrack x \right\rbrack$，使得$h = gf$具有低范數，即范數小于$N$。這相當于尋找具有低范數多項式$f,xf,x^{2}f\ldots,x^{r}f$的整數線性組合。不過，大多數情況下，并不存在具有足夠小的范數的非平凡線性組合。

Coppersmith找到了解決這個問題的竅門：如果$f\left( x_{0} \right) = 0\ \text{mod}\ N$成立，那么對于任意$k$則有$f\left( x_{0} \right)^{k} = 0\ \text{mod}\ N^{k}$。更一般地，定義以下多項式：

$$g_{u,v}\left( x \right) = N^{m - v}x^{u}f{(x)}^{v}$$

對于一些預定義的$m$，則$x_{0}$是$g_{u,v}\left( x \right)$模$N^{m}$的一個根，其中$u \geq 0$和$0 \leq v \leq m$。要使用引理4，我們必須找到多項式$g_{u,v}\left( x \right)$的一個整數線性組合$h\left( x \right)$，使得$h(xX)$的范數小于$N^{m}$ (回想一下$X$是滿足$X \leq N^{1/d}$的$x_{0}$上界)。由于范數（是$N^{m}$而不是$N$）的松弛上界，我們可以證明，對于足夠大的$m$，總是存在一個線性組合$h\left( x \right)$滿足所要求的界。一旦$h\left( x \right)$被找到，引理4就意味著它有$x_{0}$作為整數的根,因此,可以很容易地找到$x_{0}$。

如何有效地找到$h\left( x \right)$還有待證明，要做到這一點，我們必須說明一些關于$\mathbb{Z}^{w}$格的基本事實。 設$u_{1},\ldots,u_{w} \in \mathbb{Z}^{w}$是線性獨立的向量。由$\left\langle u_{1},\ldots,u_{w} \right\rangle$構成的(滿秩)格$L$是$u_{1},\ldots,u_{w}$的所有整數線性組合的集合。$L$的行列式定義為$w \times w$方陣的行列式，它的行列式是向量$u_{1},\ldots,u_{w}$。

在我們的例子中，我們把多項式$g_{u,v}\left( \text{xX} \right)$看作向量，并研究了它們所構成的格$L$。設$v = 0,\ldots,m$，$u = 0,\ldots,d - 1$，則格的維數$w = d(m + 1)$。例如，當$f$是二次一元多項式且$m = 3$時，得到的格由以下矩陣的行構成：

$*$元對應于我們忽略其值的多項式的系數，所有空元為零。由于矩陣是三角形的，它的行列式是對角線上元素的乘積(如上所示)，我們的目標是在這個格中找到短向量。

Hermite的一個經典結論表明：任意維數為$w$的格$L$包含一個非零向量$v \in L$，它的$L_{2}$范數滿足$\left\| v \right\| \leq \gamma_{w}{det(L)}^{\frac{1}{w}}$，其中$\gamma_{w}$是只依賴于$w$的常數。Hermite的界可以用來證明，對于足夠大的$m$，我們的格包含需求小于$N^{m}$的范數向量。問題是我們能否有效地在$L$中構造長度小于Hermite界的短向量。LLL算法是一種有效的算法，恰好可以做到。

事實5（LLL）

設$L$是由$\left\langle u_{1},\ldots,u_{w} \right\rangle$所構成的格。當$\left\langle u_{1},\ldots,u_{w} \right\rangle$作為輸入時，LLL算法輸出一個向量$v \in L$滿足：

$$\left\| v \right\| \leq 2^{\frac{w}{4}}{det(L)}^{\frac{1}{w}}$$

LLL算法的運行時間是輸入長度的四分之一。

LLL算法（以其發明者L. Lovasz、A. Lenstra和H. Lenstra Jr的名字命名）在計算數論和密碼學中有許多應用。它在1982年的發現為整數上多項式的因式分解提供了一種有效的算法，更廣泛地說，為數環上的多項式的因式分解提供了一種有效的算法。LLL算法經常被用來攻擊各種密碼系統，例如，許多基于"背包問題"的密碼系統都是使用LLL算法破解的。

利用LLL算法，我們可以完成Coppersmith定理的證明。為了保證LLL算法產生的向量滿足引理4的界，我們需要滿足：

$$2^{\frac{w}{4}}{det(L)}^{\frac{1}{w}} < \frac{N^{m}}{\sqrt{w}}$$

其中$w = d(m + 1)$是$L$的維數。常規計算表明，對于足夠大的$m$，能滿足約束條件。實際上，當$X = N^{\frac{1}{d} - \epsilon}$時，取$m = O(\frac{k}{d})$和$k = \mathrm{\min}(\frac{1}{\epsilon},\log N)$就足夠了。因此，運行時間主要由在維數為$O(k)$的格上運行LLL算法所決定。

一個自然而然的問題，Coppersmith定理能否應用于二元和多元多項式。如果$f(x,y) \in \mathbb{Z}_{N}\left\lbrack x,y \right\rbrack$有根$\left( x_{0},y_{0} \right)$且有適當的界$\left| x_{0}y_{0} \right|$，Marvin能有效地找到$\left( x_{0},y_{0} \right)$嗎？盡管相同的技術似乎適用于某些二元多項式，但目前還是一個有待證明的開放性問題。隨著越來越多的結果依賴于Coppersmith定理的二元擴張，所以嚴密的算法將會非常有用。

開放性問題3

找出Coppersmith定理可以推廣到二元多項式的一般條件。

4.2 Hastad廣播攻擊

作為Coppersmith定理第一個應用，我們對由Hastad提出的舊攻擊進行了改進。假設Bob希望將加密消息$M$發送給多方$P_{1},P_{2},\ldots,P_{k}$。每一方都有自己的RSA密鑰$\left\langle N_{i},e_{i} \right\rangle$。我們假定$M$比所有$N_{i}$都小。Bob為了發送$M$，天真地使用每個公共密鑰對其進行加密，并將第$i^{\text{th}}$個密文發送給$P_{i}$。攻擊者Marvin可以竊聽Bob對外的連接，并收集傳輸的$k$個密文。

為了簡單起見，假設所有公鑰指數$e_{i}$為3。一個簡單的論證表明，當$k \geq 3$時，Marvin可以計算出$M$。實際上，Marvin得到$C_{1},C_{2},C_{3}$，其中：

$$C_{1} = M^{3}\ \text{mod}\ N_{1},C_{2} = M^{3}\ \text{mod}\ N_{2},C_{3} = M^{3}\ \text{mod}\ N_{3}$$

對于所有的$i \neq j$，我們可以假設$\gcd\left( N_{i},N_{j} \right) = 1$，否則Marvin可以因式分解一些$N_{i}$。因此，將中國剩余定理(CRT)應用于$C_{1},C_{2},C_{3}$，給出的$C^{'} \in \mathbb{Z}_{N_{1}N_{2}N_{3}}$滿足${C^{'} = M}^{3}\ \text{mod}\ N_{1}N_{2}N_{3}$。由于$M$小于所有的$N_{i}$，我們有$M^{3} < N_{1}N_{2}N_{3}$，那么${C^{'} = M}^{3}$在整數上成立，因此，Marvin可以通過計算$C^{'}$的實數立方根來得到$M$。更一般的情況是，如果所有的公鑰指數都等于$e$，則只要$k \geq e$，Marvin就可以計算出$M$。不過這種攻擊只有使用較小的$e$值時才是可行的。

Hastad提出了一種更強的攻擊方法。為了抵御Hastad的攻擊，考慮一下對上述攻擊做一下天真防御。Bob可能在加密之前"填充"消息，而不是廣播加密的$M$。例如，如果$M$是$m$位長的，Bob可以將$M_{i} = i2^{m} + M$發送給$P_{i}$。由于Marvin獲得了不同消息的加密，他無法發起攻擊。然而，Hastad證明了這種線性填充是不安全的，事實上，他證明了在加密之前對消息應用任何固定多項式都不能阻止攻擊。

假設對于每個參與者$P_{1},P_{2},\ldots,P_{k}$，Bob有一個固定的公用多項式$f_{i} \in \mathbb{Z}_{N_{i}}\left\lbrack x \right\rbrack$。為了廣播消息$M$，Bob將$f_{i}(M)$的加密發送給$P_{i}$。Marvin通過竊聽知道了$C_{i} = f_{i}{(M)}^{e_{i}}\ \text{mod}\ N_{i}$，其中$i = 1,\ldots,k$。Hastad表明，如果有足夠的參與方，Marvin可以從所有的密文中計算出明文$M$。下面的定理是Hastad原始結論的一個更強的版本。

定理6 (Hastad) 設$N_{1},\ldots,N_{k}$是成對的相對素數，集合$N_{\min} = {min}_{i}(N_{i})$。設$g_{i} \in \mathbb{Z}_{N_{i}}\left\lbrack x \right\rbrack$是$k$個$d$次多項式。假設存在唯一的$M < N_{\min}$滿足：

$$g_{i}\left( M \right) = 0\ \text{mod}\ N_{i}(i = 1,\ldots,k)$$

假設$k > d$，給定$\left\langle N_{i},g_{i} \right\rangle_{i = 1}^{k}$，我們可以有效地找到的$M$。

證明 令$\overline{N} = N_{1}{\cdots N}_{2}$，我們假定所有的$g_{i}$都是一元的。(實際上，對于某些$i$，$g_{i}$的首項系數在$\mathbb{Z}_{N_{i}}^{*}$中是不可逆的，那么$N_{i}$的因式分解就會顯現出來。通過將每個$g_{i}$乘以$x$的適當冪，假定它們都有$d$次。構造多項式：

$$g\left( x \right) = \sum_{i = 1}^{k}{T_{i}g_{i}(x)},\mathrm{}\mathrm{其中}\mathrm{}T_{i} = \begin{matrix} 1\mathrm{\ \text{mod}}\ \ N_{j}\mathrm{}\mathrm{若}i = j \\ 0\mathrm{\ \text{mod}}\ \ N_{j}\mathrm{}\mathrm{若}i = j \\ \end{matrix}$$

其中$T_{i}$是整數，被稱為中國剩余系數。那么$g(x)$一定是一元的，因為它首項模了所有的$N_{i}$，且次數為$d$。此外，我們還知道$g(M) = 0\mathrm{\ \text{mod}}\ \overline{N}$。定理6現在便可由定理3推導而來，因為$M < N_{\min} < {\overline{N}}^{\frac{1}{k}} < {\overline{N}}^{\frac{1}{d}}$。

該定理表明，如果提供了足夠多的方程，可以有效地求解以相對素數復合模的一元方程組。令$g_{i} = f_{i}^{e_{i}} - C_{i}$，我們可以知道，當參與方數至少為$d$時，Marvin可以從給定的密文中計算出$M$，其中$d$是$e_{i}deg(f_{i})$在所有$i = 1,\ldots,k$上的最大值。特別地，如果所有的$e_{i}$都等于$e$，并且Bob發送線性相關的消息，那么Marvin只要$k > e$就可以算出明文。

Hastad的原始定理比上述定理更弱。與$d$次多項式不同，Hastad定理需要$\frac{d(d + 1)}{2}$次多項式。Hastad定理的證明類似于上一節中提到的Coppersmith定理證明。由于Hastad定理沒有在格中使用$g$的冪，從而得到了一個較弱的界。

總結這一節，我們注意到，要正確地防御上述廣播攻擊，必須使用隨機填充方法，而不是使用固定填充方法。

4.3 Franklin-Reiter相關消息攻擊

當Bob用相同的模數發送與Alice相關的加密消息時，Franklin和Reiter發現了一種聰明的攻擊。$\left\langle N,e \right\rangle$是愛麗絲的公鑰，假設$M_{1},M_{2} \in Z_{N}^{*}$是兩個不同的消息，對于某些已知的多項式$f \in Z_{N}\left\lbrack x \right\rbrack$，$M_{1},M_{2}$滿足$M_{1} = f\left( M_{2} \right)\mathrm{\ \text{mod}}\ - N$。為了將$M_{1}$和$M_{2}$發送給Alice，Bob可能會天真地對消息進行加密，并傳輸得到的密文$C_{1},C_{2}$。我們通過證明可以知道，在給定$C_{1},C_{2}$的情況下，Marvin可以很容易地計算出$M_{1},M_{2}$。雖然攻擊對任意小$e$都有效，但為了簡化證明，我們給出了$e = 3$的引理。

引理7(FR)

令$e = 3$，$\left\langle N,e \right\rangle$為RSA公鑰。設$M_{1} \neq M_{2} \in Z_{N}^{*}$對于$b \neq 0$的線性多項式$f = ax + b \in Z_{N}\left\lbrack x \right\rbrack$滿足$M_{1} = f\left( M_{2} \right)\ \text{mod}\ N$。然后，給定$\left\langle N,e,C_{1},C_{2},f \right\rangle$，Marvin可以在$\log N$的平方時間內計算出$M_{1},M_{2}$。

證明

為了保證這部分證明的一般性，我們使用任意$e$來表示它（而不是限制為$e = 3$）。由于$C_{1} = M_{1}^{e}\mathrm{\ \text{mod}}\ \ N$，我們知道$M_{2}$是多項式$g_{1}\left( x \right) = f\left( x \right)^{e} - C_{1} \in Z_{N}\left\lbrack x \right\rbrack$的根。同樣，$M_{2}$也是$g_{2}\left( x \right) = x^{e} - C_{2} \in Z_{N}\left\lbrack x \right\rbrack$的根。線性因子$x - M_{2}$是兩個多項式的除法。因此，Marvin可以使用歐幾里德算法來計算$g_{1}$和$g_{2}$的最大公約數(Greatest Common Divisor, GCD)。如果GCD是線性的，則可以找到$M_{2}$。GCD可以在$e$和$\log N$的平方時間內算出。

我們證明了當$e = 3$時，GCD一定是線性的。多項式$x^{3} - C_{2}$因子將$p$和$q$都模成一個線性因子和一個不可約二次因子(因為$\mathrm{\gcd}(e,\varphi\left( N \right)) = 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$時才能應用這種攻擊。對于大型電子計算機來說，計算GCD的工作令人望而卻步。一個有趣的問題(盡管可能很難)，為任意的$e$設計這樣的攻擊，尤其是能否在$\log e$的多項式時間中找到上述$g_{1}$和$g_{2}$的GCD？

4.4 Coppersmith短填充攻擊

Franklin-Reiter的攻擊可能看起來有點人為。畢竟，為什么Bob要給Alice發送相關消息的加密呢？Coppersmith加強了攻擊，并證明了一個關于填充攻擊的重要的結論。

隨機填充算法可以通過將一些隨機位附加到其中一個端來填充明文$M$，但是以下攻擊指出了這種簡單填充的危險。假設Bob向Alice發送了正確填充的$M$加密。攻擊者Marvin攔截密文并阻止其到達目的地。Bob注意到Alice沒有回復他的消息，并決定將$M$重新發送給Alice。他隨機填充$M$并傳輸生成的密文。Marvin現在有兩個密文，對應于使用兩種不同隨機填充對同一消息的兩次加密。以下定理表明，雖然他不知道使用的填充算法，但Marvin仍能夠算出明文。

定理8

設$\left\langle N,e \right\rangle$為RSA公鑰，其中$N$的長度為是$n$位。令集合$m = \left\lbrack n/e^{2} \right\rbrack$。設$M \in Z_{N}^{*}$是長度最長為$n - m$位的消息。定義$M_{1} = 2^{m}M + r_{1}$和$M_{2} = 2^{m}M + r_{2}$，其中$r_{1}$和$r_{2}$是分別為$0 \leq r_{1},r_{2} \geq 2^{m}$的整數。如果Marvin知道了$\left\langle N,e \right\rangle$和$M_{1},M_{2}$的加密$C_{1},C_{2}$(但不知道$r_{1}$或$r_{2}$)，則他可以有效地計算出M。

證明

定義$g_{1}\left( x,y \right) = x^{e} - C_{1}$和$g_{2}\left( x,y \right) = x^{e} - C_{2}$，我們知道當$y = r_{2} - r_{1}$時，這些多項式有相同的根$M_{1}$。換句話說，$\Delta = r_{2} - r_{1}$是結式$h(y) = \text{res}_{x}(g_{1},g_{2}) \in \mathbb{Z}_{N}\left\lbrack y \right\rbrack$的根。$h$的次數最多是$e^{2}$。此外有$\left| \Delta \right| < 2^{m} < N^{\frac{1}{e^{2}}}$，因此$\Delta$是$h$模$N$的一個小根，而Marvin可以利用Coppersmith定理（定理3）有效地求出這個根。一旦$\Delta$已知，便可以使用上一節的Franklin-Reiter攻擊算出$M_{2}$，從而得到$M$。

當$e = 3$時，只要填充長度小于消息長度的$\frac{1}{9^{th}}$，就可以進行攻擊。這是一個重要的結論。注意，對于建議值$e= 65537$，對于標準的模數大小來說，這種攻擊是無用的。

4.5 部分密鑰泄露攻擊

設$\left\langle N,d \right\rangle$為RSA私鑰，假設Marvin通過某種方式知道了$d$的一部分，比如說四分之一。他能得到$d$剩下的部分嗎？當相應的公鑰指數很小時，答案是肯定的，令人驚訝吧。最近，Boneh，Durfee和Frankel證明了只要$e < \sqrt{N}$，就有可能從它的一小部分位算出$d$的所有部分。可見結論說明了保護整個RSA私鑰的重要性。

定理9 (BDF)

設$\left\langle N,d \right\rangle$為RSA私鑰，其中$N$長度為$n$位.。給定$d$的$\left\lceil \frac{d}{4} \right\rceil$最小有效位，Marvin可以在$\text{e}\log_2e$的線性時間算出$d$。

證明依賴于另一個完美精妙的Coppersmith定理。

定理10 (Coppersmith)

設$N = PQ$是一個$n$位RSA模。然后，給定$p$的$n/4$最小有效位或$p$的$n/4$最有效位，可以有效地將$N$分解。

定理9很容易從定理10推理出來，事實上，根據$e$和$d$的定義，存在一個整數$k$，使得：

$$ed - k(N - p - q + 1) = 1$$

由于$d < \sqrt{N}$，我們必有$0 < k \leq e$。對方程模$2^{\frac{n}{4}}$進行約化，設$q = \frac{N}{p}$，得到：

$$\left( ed \right)p - kp\left( N - p + 1 \right) + kN = p(\mathrm{\ \text{mod}}\ 2^{\frac{n}{4}})$$

由于Marvin知道了$d$的$n/4$最小有效位，他知道$ed\ \text{mod}\text{}2^{\frac{n}{4}}$的值，因此，他得到了一個關于$k$和$p$的方程。對于$k$的每一個$e$的可能值，Marvin求解$p$的二次方程，并能得到了$p\ \text{mod}\text{}2^{\frac{n}{4}}$的一些候選值。對于這些候選值，他運用定理10嘗試去分解$N$。可以證明$p\ \text{mod}\text{}2^{\frac{n}{4}}$的候選值的總數最多為$\text{e}\log_2e$，因此，在最多$\text{e}\log_2e$次嘗試之后，$N$將被分解。

定理9被稱為部分密鑰泄露攻擊，對于更大的$e$值，只要$e < \sqrt{N}$，也存在類似的攻擊，不過，要實現此種攻擊的技術有點復雜。有趣的是，基于離散日志的密碼系統，如ELGamal公鑰系統，似乎不容易受到部分密鑰泄漏攻擊的影響。事實上，如果給出$g^{x}\mathrm{\ \text{mod}}\ p$和$x$的常數部分，則沒有已知的多項式時間算法來計算$x$的其余部分。

為了總結這一節，我們將證明當加密指數$e$很小時，RSA系統會泄漏相應私鑰$d$一半的最高有效位。要了解這一點，再考慮一個方程$ed - k(N - p - q + 1) = 1$，其中$k$是$0 < k \leq e$的整數。給定$k$，Marvin可以很容易地計算出：

$$\widehat{d} = \left\lfloor (kN + 1)/e \right\rfloor$$

之后：

$$\left| \widehat{d} - d \right| \leq \frac{k\left( p + q \right)}{e} \leq \frac{3k\sqrt{N}}{e} < 3\sqrt{N}$$

因此，$\widehat{d}$是$d$的很好的近似值。該界表明，對于大多數$d$，$\widehat{d}$中一半的最高有效位與$d$相同。由于$k$只有$e$個可能的值，因此Marvin可以構造一個大小$e$的小集合，使得集合中的一個元素等于$d$的一半最高有效位的。$e = 3$的情況特別有趣，在這種情況下，可以知道$k = 2$，系統完全泄漏了$d$的一半最高有效位。

5 執行攻擊

我們將注意力轉向另一類完全不同的攻擊。這些攻擊不是攻擊RSA函數的底層結構，而是專注于RSA的實現。

5.1 時序攻擊

想一下存儲RSA私鑰的智能卡，由于卡是防篡改的，攻擊者Marvin可能無法審閱其內容并使其泄露出密鑰。然而，Kocher的一個巧妙攻擊表明，通過精確測量智能卡執行RSA解密（或簽名）所需的時間，可以快速發現私有解密指數$d$。

我們將解釋如何使用"重復平方算法"對一個簡單的RSA實現進行攻擊。設$d = d_{n}d_{n - 1}\ldots d_{0}$是$d$的二進制表示（即$d = \sum_{i = 0}^{n}{2^{i}d_{i}},其中d_{i} \in \left\{ 0,1 \right\}$）。基于$C = \prod_{i = 0}^{n}M^{2^{i}d_{i}}\mathrm{\ \text{mod}}\ \ N$的觀察基礎，我們可以知道用重復平方算法來計算$C = M^{d}\mathrm{\ \text{mod}}\ \ N$最多使用$2n$次模乘，算法是如下工作的：

令$z$等于$M$，$C$等于1，對于$i = 0,\ldots,n$，執行以下步驟：

（1）如果$d_{i} = 1$，令$C$等于$C \bullet z\mathrm{\ \text{mod}}\ \ N$，

（2）令$z$等于$z^{2}\mathrm{\ \text{mod}}\ \ N$。

最后，$C$有值為$M^{d}\mathrm{\ \text{mod}}\ \ N$。

當$i = 0,\ldots,n$時，變量$z$遍歷$M^{2^{i}}\ \text{mod}\ N$值的集合，變量$C$在集合中"收集"適當冪以獲得$M^{d}\mathrm{\ \text{mod}}\ \ N$。

為了發起攻擊，Marvin要求智能卡在大量隨機消息$M_{1},\ldots,M_{k} \in \mathbb{Z}_{N}^{*}$上生成簽名，并測量每個簽名生成所需的時間$T_{i}$。

攻擊從最低有效位開始一次一個地算出$d$的比特位。我們知道$d$是奇數，因此$d_{0} = 1$。考慮第二次迭代。最初$z = M^{2}\mathrm{\ \text{mod}}\ \ N$且$C = M$。如果$d_{1} = 1$，則智能卡會計算乘積$C \bullet z = M \bullet M_{i}^{2}\mathrm{\ \text{mod}}\ \ N$，否則，它是不會計算的。設$t_{i}$是智能卡計算$M_{i} \bullet M_{i}^{2}\mathrm{\ \text{mod}}\ \ N$所花費的時間。由于計算$M_{i} \bullet M_{i}^{2}\mathrm{\ \text{mod}}\ \ N$的時間取決于$M_{i}$的值，因此$t_{i}$彼此不同（簡單模約化算法需要不同的時間，取決于所減少的值）。一旦Marvin獲得智能卡的物理規格，之后他便會測量得到$t_{i}$（在發起攻擊之前）。

Kocher觀察到當$d_{1} = 1$時，兩個集合$\left\{ t_{i} \right\}$和$\left\{ T_{i} \right\}$是相關的。例如，如果，對于某些$i$，$t_{i}$比預期的要大得多，那么$T_{i}$也可能大于預期。另一方面，如果$d_{1} = 0$，則兩個集合$\left\{ t_{i} \right\}$和$\left\{ T_{i} \right\}$表現為獨立的隨機變量。通過測量相關性，Marvin可以確定$d_{1}$是0還是1。繼續使用這個方法，他可以很快得到$d_{2}$，$d_{3}$。注意，當使用低公鑰指數$e$時，上一節的部分密鑰泄露攻擊表明，使用Kocher的時序攻擊，只需要知道$d$的四分之一的位就行。

有兩種方法可以抵御攻擊。最簡單的是添加適當的延遲，以使模冪運算總是要花費一定的時間。第二種方法是由Rivest提出的基于盲化的方法。在解密M之前，智能卡選擇一個隨機的$r \in \mathbb{Z}_{N}^{*}$并計算$M^{'} = M \bullet r^{e}\mathrm{\ \text{mod}}\ \ N$，然后將$d$應用于$M^{'}$上并獲得$C^{'} = \left( M^{'} \right)^{d}\mathrm{\ \text{mod}}\ \ N$，最后，令$C = \frac{C^{'}}{r}\text{modN}$。通過這種方法，將$d$應用于Marvin不知道的隨機消息$M^{'}$上，這樣的話，Marvin就不能發起攻擊了。

Kocher最近在這些線路上發現了另一種叫做功率密碼分析的攻擊。 Kocher表明，通過在簽名生成過程中精確測量智能卡的功耗，Marvin通常可以輕松發現密鑰。事實證明，在多精度乘法期間，卡的功耗高于正常值。通過測量高消耗周期的長度，Marvin可以很容易地確定在給定的迭代中卡是執行一次還是兩次乘法，從而暴露出$d$的比特位。

Kocher最近發現了另一種類似的攻擊，稱為能量分析攻擊。Kocher指出通過精確測量智能卡在簽名生成過程中的功耗，Marvin通常可以很容易地得到秘密密鑰。結果表明，在多精度乘法過程中卡的功耗會高于正常值，通過測量高消耗周期的長度，Marvin可以很容易地確定在給定的迭代中卡是否執行一次或兩次乘法，從而得到$d$的比特位。

5.2 隨機故障

RSA的解密和簽名的實現經常使用中國剩余定理來加速$M^{d}\mathrm{\ \text{mod}}\ \ N$的計算，簽名者Bob為了替換模$N$的工作，先計算簽名模$p$和$q$的結果，然后利用中國剩余定理將結果結合起來。更準確地說，Bob首先計算：

$$C_{p} = M^{d_{p}}\mathrm{\ \text{mod}}\ p和C_{q} = M^{d_{q}}\mathrm{\ \text{mod}}\ q$$

其中$d_{p} = d\mathrm{\ \text{mod}}\ (p - 1)$和$d_{q} = d\mathrm{\ \text{mod}}\ (q - 1)$。然后，他得到簽名$C$通過令：

$$C = T_{1}C_{p} + T_{2}C_{q}\left( \mathrm{\ \text{mod}}\ \ N \right)$$

其中：

$$T_{1} = \left\{ \frac{1\mathrm{\ \text{mod}}\ p}{0\mathrm{\ \text{mod}}\ q} \right\} 和T_{2} = \left\{ \frac{1\mathrm{\ \text{mod}}\ p}{0\mathrm{\ \text{mod}}\ q} \right\}$$

與$d_{p}$和$d_{q}$兩個指數相比，CRT最后一步的運行時間可以忽略不計。注意$p$和$q$是$N$的一半長，然后由于乘法的簡單實現需要平方時間，所以模$p$的乘法速度是模$N$的4倍，而且，$d_{p}$是$d$的一半長，計算$M^{d_{p}}\mathrm{\ \text{mod}}\ p$的速度是計算$M^{d}\mathrm{\ \text{mod}}\ \ N$的8倍，因此，整個簽名時間減少了四倍，許多實現都使用這種方法來提高性能。

Boneh，DeMillo和Lipton觀察到使用CRT方法有內在的危險。假設在生成簽名時，Bob的計算機上的一個小故障導致它在一條指令中錯誤計算。例如，在將寄存器中的值從一個位置復制到另一個位置時，其中一個比特位被翻轉了。(故障可能是由環境電磁干擾引起的，也可能是由于罕見的硬件缺陷造成的，比如早期版本的奔騰芯片。)

Marvin得到了無效的簽名給定之后可以很容易地對Bob的模數$N$進行分解。

正如A. K. Lenstra所說，我們發現了一個新的攻擊。假設在Bob生成簽名時發生單個錯誤，那么，$C_{p}$或$C_{q}$中將有一個被錯誤地計算。如果說$C_{p}$是正確的，那么${\widehat{C}}_{q}$就會不正確，得到的簽名為$\widehat{C} = T_{1}C_{p} + T_{2}{\widehat{C}}_{q}$。一旦Marvin獲取到了$\widehat{C}$，通過計算${\widehat{C}}^{e} \neq M\mathrm{\ \text{mod}}\ \ N$，他就知道這是一個錯誤的簽名。然而注意到：

$${\widehat{C}}^{e} = M\mathrm{\ \text{mod}}\ p當{\widehat{C}}^{e} \neq M\mathrm{\ \text{mod}}\ q$$

因此，$\mathrm{\gcd}(N,{\widehat{C}}^{e} - M)$便是$N$的一個非平凡因子。

要使攻擊奏效，Marvin必須對$M$有充分的了解。也就是說，我們假設Bob不使用任何隨機填充方法，簽名前的隨機填充可以防御此種攻擊，對于Bob來說，一個更簡單的防御方法是在將生成的簽名發送給全世界之前檢查生成的簽名。當使用CRT加速方法時，檢查是特別重要的。隨機故障攻擊對許多密碼系統都是有害的，許多系統，包括RSA的非CRT實現，都可以使用隨機故障進行攻擊。不過，這些結論更多的是理論性的。

5.3 Bleichenbacher對PKCS 1的攻擊

設$N$是$n$位RSA模，$M$是$m$位消息，其中$m < n$。在應用RSA加密之前，一般會通過向其添加隨機位，將消息$M$填充到$n$位。公鑰加密標準1（Public Key Cryptography Standard 1, PKCS 1）的舊版標準就是使用的這種方法。填充后，消息如下所示：

02 隨機位 00 M

生成的消息長度為$n$位，并直接使用RSA加密。包含"02"的初始塊長度為16位，從上圖可看出已在消息中添加了隨機填充。

當運行在Bob的機器上應用程序(例如，Web瀏覽器)接收到消息時，會對其進行解密，檢查初始塊，并去掉隨機填充。但是，一些應用程序會檢查"02"初始塊，如果不存在，就會返回一條錯誤消息，說明"無效的密文"。Bleichenbacher表示這個錯誤消息可能導致災難性的后果：攻擊者Marvin可以使用錯誤消息解密他所選擇的密文。

假設Marvin截獲了一個針對Bob的密文$C$，并希望對其進行解密。為了發動攻擊，Marvin隨機挑選了一個$r \in \mathbb{Z}_{N}^{*}$，計算$C^{'} = rC\mathrm{\ \text{mod}}\ \ N$，并將$C^{'}$發送到Bob的機器。運行在Bob的機器上的應用程序接收$C^{'}$并嘗試解密它。它要么用錯誤消息進行響應，要么根本不響應(如果$C^{'}$的格式正確的話)。因此，Marvin知道$C^{'}$解密過程中16位最高有效位是否等于02。實際上，Marvin有這樣的諭言，對于他選擇的任何$r$，他都可以測試$\text{rC}\ \text{mod}\ N$解密的16位最高有效位是否等于02。Bleichenbacher證明了這樣的諭言足以解密$C?$。

6 結論

對RSA系統進行了20年的研究以來，產生了一些有見地的攻擊，但還沒有發現破壞性的攻擊。到目前為止發現的攻擊主要說明了在實現RSA時需要避免的陷阱，目前看來，可以信任正確的RSA密碼系統實施來提供數字世界中的安全性。我們將針對RSA的攻擊分為四類：(1)利用系統公然誤用的基本攻擊；(2)低私鑰指數攻擊，此種攻擊非常嚴重，絕不能使用低私鑰指數；(3)低公鑰指數攻擊；(4)對RSA系統執行時的攻擊。這些持續不斷的攻擊說明，我們對基本數學結構的研究還是不夠的。另外，Desmedt和Odlyzko、Joye和Quisquater以及DeJonge和Chaum還提出了一些額外的攻擊。在整篇論文中，我們觀察到通過在加密或簽名之前正確填充消息可以防御許多攻擊。

致謝

我要感謝Susan Landau鼓勵我撰寫調查問卷，感謝Tony Knapp幫忙編輯手稿。我還要感謝在早些時候Mihir Bellare、Igor Shparlinski和R. Venkatesan對草案發表的評論。

本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/727/