淺析RSA加密算法

任遠(yuǎn)芳　劉志杰　高玉明　瞿仁麗

摘要：RSA算法不但能用于數(shù)據(jù)加密，也能用于數(shù)字簽名，還能檢測(cè)素?cái)?shù)的算法，所以它是目前最有影響力的公鑰加密算法，能夠抵抗到目前為止已知的所有密碼攻擊。其安全性依賴于大素?cái)?shù)因數(shù)分解的困難性。文章主要介紹RSA的加密算法原理、加密與解密過(guò)程，存在的攻擊，以及參數(shù)選擇。

關(guān)鍵詞：非對(duì)稱密碼；RSA算法；加密；素?cái)?shù)；參數(shù)；量子算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）09-2062-02

近年來(lái)，網(wǎng)絡(luò)的發(fā)展和普及，解除了人們傳統(tǒng)意義上的時(shí)間和空間上的束縛，真正實(shí)現(xiàn)了全球信息化。但與此同時(shí)，由于網(wǎng)絡(luò)的開放性、互動(dòng)性和全球性等特性，信息篡改、假冒和竊取等不安全問(wèn)題也日益增多。因此，信息安全成為當(dāng)今社會(huì)一個(gè)熱門的話題。

在傳輸信息過(guò)程中，為確保信息的安全性和保密性，信息加密成為一種主要措施。加密算法的種類不勝枚舉。從2012年為期5天的RSA大會(huì)中，可見RSA已經(jīng)運(yùn)用到社會(huì)中的各個(gè)領(lǐng)域，受到了全世界的關(guān)注。這主要基于RSA加密算法不僅易于理解和實(shí)現(xiàn)，而且安全性好。

1 RSA加密算法

1.1算法原理

文獻(xiàn)[1]中描述RSA算法是在1977年由Rivest、SchaMir和AdleMan發(fā)明的。RSA算法是一種既用于數(shù)據(jù)加密也可以數(shù)字簽名的非對(duì)稱密碼算法，其安全性依賴于因子分解大數(shù)問(wèn)題。

RSA密碼算法是利用陷門單向函數(shù)的一種可逆模指數(shù)運(yùn)算，它的安全性是基于大數(shù)分解的困難性。下面給出RSA體制的算法流程：

1）RSA加解密算法的初始化

第一，加解密系統(tǒng)隨機(jī)地選取兩個(gè)非公開的大素?cái)?shù)p和q。

第二，計(jì)算出公開的模數(shù)N和非公開的歐拉函數(shù)，[N=pq]，[φN=p-1q-1]。

第三，隨機(jī)生成一個(gè)整數(shù)e作為加密秘鑰，并使成立。

第四，計(jì)算d（私鑰），使得）成立，即，為安全起見立即銷毀p、q及e。

2 RSA算法存在攻擊

盡管對(duì)于RSA的密碼分析已經(jīng)研究了三十多年，但它依然是流行和可靠的?？墒?，在RSA算法實(shí)現(xiàn)的細(xì)節(jié)上存在一些缺陷，這導(dǎo)致了RSA的安全性下降，從而使RSA被攻擊者攻破。下面簡(jiǎn)單地概述一下目前對(duì)RSA算法攻擊的幾種主要方法。

2.1 數(shù)學(xué)攻擊

實(shí)質(zhì)上就是直接對(duì)兩個(gè)素?cái)?shù)乘積N的因式分解。這是一種最直接和最困難的的方法。一旦對(duì)N進(jìn)行分解成功，就很容易得到密鑰e。大整數(shù)因子分解一直是數(shù)論和密碼學(xué)理論研究中的主要課題。根據(jù)目前的研究表明，目前最快的因式分解算法的復(fù)雜度為[Ο2（log2n）log2log2n]。此外，在文獻(xiàn)[4]中，作者提出了用于分解強(qiáng)素?cái)?shù)乘積構(gòu)成的RSA模數(shù)N的算法，能夠進(jìn)一步提高了運(yùn)算效率。

2.2時(shí)間攻擊

依賴解密算法的運(yùn)行時(shí)間。P.Kocher提出，利用測(cè)定RSA解密所進(jìn)行的模指數(shù)的運(yùn)算時(shí)間來(lái)估計(jì)解密指數(shù)d，然后再確定d的值；可以通過(guò)將解密運(yùn)算量與參數(shù)d無(wú)關(guān)來(lái)挫敗時(shí)間攻擊；不斷強(qiáng)力窮舉密鑰。

2.3密文攻擊

攻擊者非法獲取密文通，過(guò)對(duì)密文反復(fù)用公開密鑰加密，可以使明文出現(xiàn)。例：如果取RSA參數(shù)（N，e）為（35，17），明文M為33，加密明文：[c=3317mod35=3]；再次加密：[317mod35=33]，從而得到明文。

2.4 RSA的部分明文攻擊

另外，攻擊者不僅對(duì)可以密文進(jìn)行攻擊，也可以通過(guò)獲取明文消息的部分信息進(jìn)行破譯或恢復(fù)整個(gè)明文。這也是RSA存在的另一個(gè)安全性的重要問(wèn)題。

2.5對(duì)RSA小指數(shù)的攻擊

此攻擊方法主要針對(duì)RSA算法實(shí)現(xiàn)中的細(xì)節(jié)。如果為了加快加密和驗(yàn)證，選較小的e，并且用這些e向多個(gè)用戶加密同一個(gè)消息（N不同），利用中國(guó)剩余定理可以聯(lián)立方程求解明文。

2.6公用模攻擊

如果需要多個(gè)密鑰對(duì)，有一種做法：不再重新尋找p、q，而只是重新選d、e，即若干對(duì)密鑰使用同一個(gè)模N。這時(shí)可以不用重新分組，也方便管理。但可能遭到公用模攻擊。這樣，如果同一信息用兩個(gè)不同的指數(shù)e加密，并且兩個(gè)指數(shù)e是互素的，則不需要任何解密密鑰便能恢復(fù)出明文。設(shè)M是明文，兩個(gè)互素的加密密鑰分別是[e1、e2]，共同的模數(shù)為N，兩個(gè)密文分別[c1=Me1modN]、[c2=Me2modN]。由于[e1、e2]互素，根據(jù)擴(kuò)展Euclid算法可以找到a和b，使其滿足[ae1+be2=1]。假設(shè)a是負(fù)數(shù)（在a、b中，肯定有一個(gè)是負(fù)數(shù)），再次使用Euclid算法可以計(jì)算出c1-1故可得到[（（c-11）-rc2s）≡MmodN]。

3 參數(shù)的選擇

RSA體制是將安全性基于因子分解的第一個(gè)系統(tǒng)。雖然無(wú)法證明因子分解等于破解RSA系統(tǒng)，但若能分解因子N，便能破解RSA系統(tǒng)，所以RSA對(duì)公開的N的選擇是很關(guān)鍵的。對(duì)于公開密鑰e和解密密鑰d也需要加以限制，否則會(huì)使RSA不安全。選擇參數(shù)會(huì)影響RSA整個(gè)系統(tǒng)的安全，常用的參數(shù)選擇應(yīng)注意要求如下：

3.1 p，q的選擇

要想提高RSA的效率和安全性，可以從p、q兩個(gè)參數(shù)以下兩個(gè)方面著手：素?cái)?shù)的檢測(cè)算法和對(duì)p、q的破解。

素?cái)?shù)的檢測(cè)算法。在RSA算法中，首先要產(chǎn)生兩個(gè)大素?cái)?shù)。但是要判斷一個(gè)大整數(shù)是否為素?cái)?shù)卻一直是個(gè)難點(diǎn)。素?cái)?shù)檢測(cè)算法有確定性素?cái)?shù)檢測(cè)法和概率性素?cái)?shù)檢測(cè)法兩類。目前，在RSA密碼的應(yīng)用中都使用概率性檢測(cè)法來(lái)判斷一個(gè)大數(shù)是否是素?cái)?shù)。但是通過(guò)概率性監(jiān)測(cè)算法的檢測(cè)，還是存在偽素?cái)?shù)的情況。

對(duì)p、q的破解。從RSA算法原理中，我們知道歐拉函數(shù)[φN]和模數(shù)N：[φN=p-1q-1]和[N=pq]。那么根據(jù)這兩個(gè)式子可以構(gòu)造關(guān)于p、q的一元二次方程，即[χ2-N-φ（N）+1χ+N=0]。其中p、q滿足：

[[N=pq]p+q=N-φN+1]

解之得 p，q= [1/2N+1-φ（N）±（N+1-φ（N））2-4N]

由文獻(xiàn)[4]提出的一種強(qiáng)素?cái)?shù)的量子算法，可求得[φN]，這樣就可以得到p、q的值，即分解了模數(shù)N，RSA就被破解了。

總之，為了抗窮舉，p、q都要大；p、q的差要大，如果p、q的差不大，可以用N開方估算p、q；p-1、q-1要有大的素因子，p、q要為強(qiáng)素?cái)?shù)；p-1、q-1的公因數(shù)要小。

3.2 模數(shù)N取幾個(gè)素?cái)?shù)乘積

從RSA算法原理，我們知道模數(shù)N是由兩個(gè)素?cái)?shù)相乘得到的。那么模數(shù)N可以由多個(gè)素?cái)?shù)相乘得到嗎？答案是肯定的。Euler函數(shù)[φ（N）]表示小于N并且與N互素的正整數(shù)個(gè)數(shù)。如果模數(shù)N可因式分解為[N=Piai]（其中，[ai>0]，[ai]互不相同），則[φ（N）=Piai×（1-1/Pi）]即：[φ（N） =N（1-1/p1）（1-1/p2）...（1-1/pn）]。文獻(xiàn)[1]已經(jīng)證明了該推斷的正確性。

無(wú)論取多個(gè)素?cái)?shù)還是兩個(gè)素?cái)?shù)相乘，一旦計(jì)算出模數(shù)N的值，就會(huì)都被丟掉。所以這多個(gè)素?cái)?shù)和兩個(gè)素?cái)?shù)的保密性是一樣的，RSA的加密和解密過(guò)程是相同的。那么在確定N時(shí)應(yīng)盡可能的選擇多個(gè)素?cái)?shù)相乘。但是如果通過(guò)量子算法[4]來(lái)對(duì)多個(gè)素?cái)?shù)乘積的模數(shù)N進(jìn)行分解的話，那么就不能構(gòu)成一元二次方程，分解模數(shù)N的難度就更大。

3.3 e，d的選擇

e不能太小，如果e小，則可能而未取模，這樣可以直接對(duì)密文開方求出明文；e太小易遭低指數(shù)攻擊。為了有效防止被攻擊，同時(shí)有較快的加解密速度，通常加密密鑰e選取16位的素?cái)?shù)，并且為[modφ（N）]的階數(shù)，即i要達(dá)到[（p-1）（q-1）/2]。

d不能太小，應(yīng)該[d>N14]。解密密鑰d的值越小，系統(tǒng)簽名和解密運(yùn)算的速度越快，這對(duì)于我們常用的智能卡的加密、銀行系統(tǒng)的簽名特別重要。

4 小結(jié)

綜上所述，RSA是一種安全性較好的非對(duì)稱密碼算法。它的安全性依賴于對(duì)模數(shù)N的因式分解。在日常生活中，RSA算法已廣泛地運(yùn)用到各個(gè)領(lǐng)域。那么對(duì)RSA算法的攻擊無(wú)時(shí)不在。特別地，當(dāng)選擇的參數(shù)不當(dāng)時(shí)，RSA很容易被攻擊。要確保RSA的效率和保密性，我們應(yīng)注意以下幾點(diǎn)：對(duì)素?cái)?shù)檢測(cè)算法進(jìn)行改進(jìn)；用量子算法來(lái)研究RSA算法。

參考文獻(xiàn)：

[1] 武亞寧.RSA 公鑰算法的新探討及改進(jìn)[J].信息安全與技術(shù)，2012（9）：27-28.

[2] 白潔.RSA大會(huì)，安全領(lǐng)袖眼中的世界[J].信息安全與通信保密，2010（4）：16-19.

[3] 張宏，劉方圓.四素?cái)?shù)RSA加密算法的研究與分析[J].2010：29-30.

[4] 潘峰，申軍偉.一種強(qiáng)素?cái)?shù)因式分解的量子算法[J].2010，46（10）：73-74.

[5] 陳磊.RSA算法的改進(jìn)[J].信息安全與技術(shù)，2011：24-26.