RSA算法的攻擊方法研究

李家蘭

（廣東石油化工學(xué)院計算機(jī)系，廣東 茂名 525000）

1 RSA算法描述

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

1.1 RSA算法的初始化

（1）選取兩個非常大的、互異的質(zhì)數(shù)p，q；

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

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

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

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

1.2 RSA 算法用于加/解密

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

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

1.3 RSA算法用于數(shù)字簽名

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

2 RSA算法的攻擊方法

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

2.1 對模數(shù)n的因子分解

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

2.2 對RSA的公共模數(shù)攻擊

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

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

2.3 對RSA的小指數(shù)攻擊

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

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

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

2.4 對RSA的選擇密文攻擊

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

例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 的隨機(jī)數(shù)），y″=(yy′)(modn)，然后騙取 u 對 y″的簽名 s=y″d(modn)。 則通過計算(r-1s)(modn)可以恢復(fù)出x，這是因為：

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

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

攻擊1源于RSA算法的數(shù)學(xué)安全基礎(chǔ)，增加初始化參數(shù)長度是有效的提高安全度的方法。

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

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

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

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

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

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