非對稱加密體制中RSA算法的研究

靳麗君

（西安鐵路職業(yè)技術學院評估與建設辦公室陜西西安710014）

在數(shù)字媒體上進行交換的數(shù)據(jù)進行加密的方法稱為信息交換加密技術，分別為對稱加密和非對稱加密。在對稱加密技術中，信息的加密和解密都使用相同的密鑰。這種加密方法可簡化加密處理過程，信息交換雙方都不必彼此研究和交換專用的加密算法，目前在國際上，非機要部門的數(shù)據(jù)加密標準常采用由IBM公司研制的名為DES的分組加密算法。盡管對稱加密體制以高效快速的加密特點得到廣泛的應用，但在網(wǎng)絡環(huán)境下它的缺點卻尤為突出，那就是密鑰的交換和分發(fā)問題。在現(xiàn)代電子政務、電子商務應用中，如果不能解決密鑰在網(wǎng)上分布的問題，那就需要大量的成本通過離線解決，這樣，對于只需要通過雙方知曉的對稱密鑰，如果通過第三方傳送密鑰，那么通信的安全性就成為一大隱患。

1976年，由Whitfield Diffie和Martin Hellman提出了非對稱加密體制（也稱作公鑰加密體制），不同于以往的加密算法，非對稱加密技術的思想不是建立在位方式的操作之上，而是建立在數(shù)學函數(shù)的基礎之上的。更重要的是，與只使用單一密鑰的傳統(tǒng)加密技術相比，每一個通信方都擁有一對密鑰，其一公鑰是可以公開的，其二私鑰是保密的，只有自己才知道。在進行加密時，加密方使用對方的公鑰，而解密時使用自己的私鑰進行解密，這樣就保證只有私鑰持有者才能進行解密[1]。

1 非對稱加密體制的思想

非對稱加密體制必須滿足以下條件：

1）公鑰和私鑰之間具有緊密的聯(lián)系，即公鑰和私鑰源自同一數(shù)學推導關系。

2）用公鑰加密的信息只能由相應的私鑰進行解密，反之亦然。而由公鑰推知私鑰，在計算上是不可能的。

利用非對稱加密方案進行通信的過程是：發(fā)送方A先查找接收方B的公鑰，因為公開公鑰并不影響通信的保密性，B可以將自己的公鑰公布在公共數(shù)據(jù)中，然后，A采用公鑰加密算法用B的公鑰對原始信息進行加密，并通過非安全信道將密文發(fā)送給B，當B接收到密文后，通過自己持有的私鑰對密文進行解密而還原出明文。在這種情況下有：

E（K1,M）=C

D（K2,C）=M

D[K2,E（K1,M）]=M

其中，K1為加密密鑰，K2為解密密鑰，C為密文，M為明文，E為加密算法，D為解密算法[2]。

2 RSA加密算法

非對稱加密體制只是一種思想，1978年，由美國麻省理工學院的Rivest、Shamir和Adleman在《獲得數(shù)字簽名和公開鑰密碼系統(tǒng)的方法》的論文中提出了一個基于數(shù)論的非對稱密碼體制，它是一種分組密碼體制。實現(xiàn)該體制的核心是RSA算法，其名稱來自于3個發(fā)明者的姓名首字母。為提高保密強度，RSA密鑰至少為500位長，一般推薦使用1 024位。非對稱加密技術的安全性是基于大整數(shù)因子分解的困難性，而大整數(shù)因子分解問題是數(shù)學上的著名難題，至今沒有有效的方法予以解決，因此可以確保RSA算法的安全性[3]。

RSA算法需要以下相關的數(shù)學概念：

素數(shù)：素數(shù)是比1大，其因子只有1和它本身，沒有其他數(shù)可以整除它的數(shù)，素數(shù)是無限的，例如，2，3，5，7……等。

兩個數(shù)互為素數(shù)：指的是它們除了1之外沒有共同的因子，也可以說這兩個數(shù)的最大公因子是1，例如，4和9，13和27等。

模運算：如A模N運算，它給出了A的余數(shù)，余數(shù)是從0到N－1的某個整數(shù)，這種運算稱為模運算。

RSA加密算法：

1）先找出一對足夠大的、不同的素數(shù)p和q。

2）計算公開的模數(shù)r=pq。

3）計算歐拉函數(shù)φ（r）=（p－1）（q－1），兩個素數(shù)p和q不再需要，應該丟棄，不要讓任何人知道。

4）找一個與φ（r）互質(zhì)的數(shù)e，且1＜e＜φ（r），整數(shù)e即為加密密鑰。

5）計算d，滿足de≡1（modφ（（r）），d為解密密鑰，要保密。

公式中，“≡”是數(shù)論中表示同余的符號，符號≡的左邊必須和符號右邊同余，也就是兩邊作模運算的結果相同。很顯然，無論φ（r）取什么值，符號右邊1modφ（r）的結果都等于1；符號左邊d與e的乘積作模運算后的結果也必須等于1，這就需要計算d的值，讓同余等式可以成立。

（6）將明文x（其值的范圍在0到r－1之間）按模為r自乘e次冪以完成加密操作，從而產(chǎn)生密文y（其值也在0到r－1范圍內(nèi)）

y=xe（mod r）

(7)將密文y按模為r自乘d次冪，完成解密操作。

x=yd（mod r）

由于RSA算法的公鑰和私鑰的長度（模長度）要達到1 024甚至2 048方可保證安全，因此，p、q、e的選取、公鑰與私鑰的生成、加密解密模指數(shù)運算都需要一定的計算機程序才能完成[4－5]。

3 RSA算法的安全性

在RSA密碼應用中，公鑰K1是公開的，即e和r的值可以被第三方竊聽到，破解RSA密碼的問題就是從已知的e和r的值想辦法求出d的值，這樣就可以得到私鑰來破解密文。從RSA算法可以看出，密碼破解的實質(zhì)是從p、q的值，求出（p－1）和（q－1）。也就是只要求出p、q的值，就能得到d的值而得到私鑰。但當p、q是大素數(shù)的時候，從二者的乘積去分解因子p、q，這是一個公認的數(shù)學難題。比如當p、q大到1024bit時，目前還沒有人可以利用任何計算工具完成這一分解任務，因此RSAS算法經(jīng)受住了各種攻擊的考驗，逐漸為人們所接受，被認為目前最優(yōu)秀的公鑰方案之一。

其他的安全問題包括：

1）公共模數(shù)攻擊。每個人具有相同的r，但有不同的指數(shù)e和d，這是不安全的。

2）低加密指數(shù)攻擊。如果選擇了較低的e值，雖然可以加快計算速度，但存在不安全性。

3）低解密指數(shù)攻擊。如果選擇了較低的d值，這是不安全的。

4）選擇密文攻擊。如A想讓T對一個T不愿意簽名的消息m’簽名，A首先選擇一個任意值x，計算y=xe（mod r），然后要求T對m=ym’簽名，A最后計算（mdmodr）x－1modr=（ym’）dx－1mod r=m’d mod r。因此一般不要對別人提交的隨機消息進行簽名[6]。

4 RSA的缺點

由于進行的都是大數(shù)計算，使得RSA最快的情況也比DES慢上倍，無論是軟件還是硬件實現(xiàn)。速度一直是RSA的缺陷。

此外，RSA算法產(chǎn)生密鑰的過程很麻煩，受到素數(shù)生成技術的限制，因此很難做到一次一密。分組長度太大，為保證達到安全性，r至少要有600 bit，使運算的的代價很高。一般來說RSA算法只用于少量數(shù)據(jù)加密。為了解決速度問題,目前人們廣泛使用對稱加密和非對稱加密結合使用的方法，這樣，RSA與DES的優(yōu)缺點正好互補。RSA的密鑰很長，加密速度慢，而采用DES，正好彌補了RSA的缺點。即DES用于明文加密，RSA用于DES密鑰的加密。由于DES加密速度快，適合加密較長的報文；而RSA可解決DES密鑰分配的問題。美國的保密增強郵件（PEM）就是采用了RSA和DES結合的方法，目前已成為E－MAIL保密通信標準[7]。

5 結論

本文針對解決對稱密碼體制安全隱患這一問題，深入研究了非對稱加密體制的基本思想，以及實現(xiàn)該體制的核心算法（即RSA算法）的基本原理和實現(xiàn)過程，并分析了RSA算法的安全性及其缺點。密碼領域的實際應用要求遠比單一使用某一種加密算法復雜，因此，多種加密算法綜合使用，取長補短，以達到更好的保障數(shù)據(jù)的安全之目的。

[1]StinsonD R.密碼學原理與實踐[M].北京:電子工業(yè)出版社,2003.

[2]鄧安文.密碼學－加密演算法[M].北京：高等教育出版社，2006.

[3]楊波.現(xiàn)代密碼學[M].2版.北京:清華大學出版社,2007.

[4]龔力.密碼技術與應用[M].北京:高等教育出版社，2008.

[5]步山岳.計算機信息安全技術[M].北京：高等教育出版社，2005.

[6]步山岳.RSA加密算法分析與實現(xiàn)[J].信息安全與通信保密，2007（10）：80－81.BU Shan-yue.RSA encryption algorithm analysis and implementation[A].Information Security and Communications,2007（10）：80－81.

[7]管占明.RSA加密算法分析與應用[J].科技廣場，2009（7）：45－46.GUAN Zhan-ming.Analysis and Application of RSA encryption algorithm[J].Technology Square,2009（7）：45－46.