RSA算法的攻擊方法研究

李家蘭

（廣東石油化工學院計算機系，廣東 茂名 525000）

1 RSA算法描述

RSA 算法是由 R.Rivest、A.Shamir和 L.Adlernan 三人于 1978 年研究提出的，是迄今得到最廣泛應用的非對稱密碼算法。RSA算法理論完善，安全性良好，可用于數據加密、數字簽名與身份認證，滿足網絡安全的多方面需求，同時算法易于實現，得到了廣泛的應用和深入的研究，其實現技術日趨成熟。RSA算法的初始化與應用描述如下：

1.1 RSA算法的初始化

（1）選取兩個非常大的、互異的質數p，q；

（2）計算 n=pq 及 φ(n)=(p-1)(q-1)；

（3）在開區間(0,φ(n))上取素數 e，滿足 gcd(φ(n),e)=1；

（4）計算 d 使得 de≡1modφ(n)；

（5）公布（e,n）為公鑰，保密（d,n）為私鑰，銷毀 p、q。

1.2 RSA 算法用于加/解密

如需對明文m（二進制表示）加密，須先把m分成等長s的數據塊m1，m2，…，mi，2s＜=n，加密 mi得到密文：ci=mie(modn)。

對密文ci解密得明文：mi=cid(modn)。

1.3 RSA算法用于數字簽名

發送者如需對信息m進行數字簽名，須使用私鑰d對m作運算：s=md(modn)得到簽名，然后將信息m和簽名s一起發送給接收方。

2 RSA算法的攻擊方法

RSA算法的安全性依賴于大整數分解的困難性。最直接的攻擊方法是分解n得到p,q，進而基于e計算d，隨著計算機運算能力的不斷提高，通過二次篩法已能分解180多位的十進制素數，增加p,q的長度已成為許多安全應用系統的加密要求。另一方面，利用系統設計和實現的缺陷，人們也提出了一些基于非因子分解方式破解RSA算法的方案。目前，對RSA算法的攻擊主要有以下幾種：

2.1 對模數n的因子分解

分解模數n是最直接的攻擊方法，也是最困難的方法。攻擊者可以獲得公鑰e和模數n；如果n=pq被成功分解，則攻擊者可以計算出φ(n)=(p-1)(q-1)，進而從 ed≡1modφ(n)解得私鑰 d。

2.2 對RSA的公共模數攻擊

若一個多用戶系統中只采用一個模數n，不同的用戶擁有不同的e和d，系統將是危險的。在此系統中，若有同一消息用不同的公鑰加密，這些公鑰共模且互質，那該信息無需私鑰就可解密。舉例來說，設P為信息明文，兩個加密公鑰為e1和e2，公共模數是n，有：

如果攻擊者獲得 n、e1、e2、C1和 C2，就能得到 P。 因為 e1和 e2互質，故用歐幾里德(Euclid)算法能找到r和s，滿足：r*e1+s*e2=1，設r為負數，則如果 P＜n，則P被獲取。

2.3 對RSA的小指數攻擊

如果RSA系統的公鑰e選取較小的值，可以使加密和驗證簽名的速度有所提高。但如果e取得太小，就容易受到小指數攻擊。例如，有同一系統的三個用戶，分別使用不同的模數n1，n2，n3，但都選取e=3；另有一用戶欲將同一明文消息P發送給以上三人，使用各人的公鑰加密得：

一般地，n1，n2，n3互素（否則，會比較容易求出公因子，降低安全性），根據中國剩余定理，可由 C1，C2，C3計算：C=P3(modn1n2n3)

如果 P＜n1,P＜n2,P＜n3,有 P3＜n1n2n3，可得

2.4 對RSA的選擇密文攻擊

選擇密文攻擊指的是攻擊者能選擇不同的密文，并擁有對應的明文，由此推出想要的信息。一般攻擊者會偽裝若干信息，讓擁有私鑰的用戶簽名，由此獲得有用的明文-密文對，然后推算想要的信息。

例1 攻擊者想要偽造用戶u對消息x的簽名。他可以先計算x1,x2，使得 x≡(x1x2)(modn)，并騙取 u對 x1和 x2的簽名和(modn)，則對x的簽名可計算如

例2 攻擊者獲得了用戶u使用公鑰e加密的密文y=xe(modn)，想要得到 x。 他可以先計算 y′=re(modn)（r是小于 n 的隨機數），y″=(yy′)(modn)，然后騙取 u 對 y″的簽名 s=y″d(modn)。 則通過計算(r-1s)(modn)可以恢復出x，這是因為：

3 對RSA算法的攻擊的防御建議

對于以上幾種攻擊，防御方案各不相同。

攻擊1源于RSA算法的數學安全基礎，增加初始化參數長度是有效的提高安全度的方法。

而攻擊2和攻擊3源于應用RSA算法的系統的設計缺陷，改進方法為：1）在多用戶系統中必須采用多個模數；2）避免為了圖求方便而使用取值太小的公鑰e。[1-2]

攻擊4最為復雜，從算法上無法解決這一問題，主要對應策略有兩條：1）私鑰持有者不對不信任的信息簽名；2）簽名信息時，先使用Hash函數生成的摘要，再對摘要簽名，避免直接對信息的簽名。[3]

以上防御方案并不能解決所有的RSA安全問題，我們建議利用RSA算法的系統仔細審核安全需求，投入使用先進行測試，并對系統安全做一個全面的審核。必須對各種安全策略及程序進行合理優化，才能盡可能地降低風險，RSA算法才能發揮最大的效用。

［1］閆洪亮,牛軍濤.實現RSA算法應注意的問題[J].計算機應用與軟件,2008(5):253-254.

［2］謝建全,陽春華.RSA算法中幾種可能泄密的參數選擇[J].計算機工程,2006(16):118-119.

［3］李志敏.基于RSA密碼體制的選擇密文攻擊的研究[J].網絡安全技術與應用,2009(1):12-13.