RSA算法的研究與實現

弋改珍

（咸陽師范學院計算機學院，咸陽 712000）

0 引言

RSA算法是一種迄今為止理論上比較成熟和完善的公鑰密碼體制，是非對稱密碼體制的典型代表[1]。在網絡、信息安全等許多方面都使用RSA算法，特別是RSA算法典型應用在通信中的數字簽名，可實現對手的身份、不可抵賴性驗證。在身份認證、信息安全、電子商務中有著廣泛的應用前景。

本文介紹了應用于RSA算法中的密碼學基礎知識，分析了RSA算法的原理與實現步驟，詳細分析了RSA實現過程中用到的算法，并在VC環境下，用C++開發語言實現了RSA的加密和解密算法。

1 RSA中的密碼學基礎知識

密碼學實質上體現了數論知識的應用，每一個加密算法體現了不同加密理論，而加密理論又涉及了數論知識。所以，數論知識是加密算法的基礎。

定義1（互質關系）[2]：如果兩個正整數，除了1以外，沒有其他公因子，則稱這兩個數是互質關系，即互素。

性質1兩個正整數互素的性質[3]：

①任意兩個質數構成互質關系；

②假設有個質數，后面找到一個數不和前面那個質數成倍數關系，則它們就互質；

③所有的自然數和1都互質；

④p是大于 1的整數，則p-1和p構成互質關系；

⑤p是大于 1的奇數，則p和p-2構成互質關系。

定義2（歐拉函數）[3]：設n為正整數，以φ()n表示不超過n且與n互素的正整數的個數，φ()n稱為n的歐拉函數值。

定理1（歐拉定理）[4]：如果a和n兩個正整數是互質關系，那么n的歐拉函數φ(n)滿足：

上式說明，a的φ(n)次方除n后的余數是1。

定理2（中國剩余定理）[4]：若a與p1互質，a＜p1；b與p2互質，b＜p2；c與p1p2互質，c＜p1p2。那么，c與數對(a,b)是一一對應關系。由于a的值有φ(p1)種可能，b的值有φ(p2)種可能，那么數對(a,b)有φ(p1)φ(p2)種可能，而c的值有φ(p1p2)種可能。則φ(p1p2)=φ(p1)φ(p2)。

定理3（費馬小定理）[4]:若a是正整數，n是質數，質數n滿足φ(n)等于p-1，a和n互質，則：

an-1≡1(modn)

定義3（模反元素）[4]：如果兩個整數a和n互質，那么一定可找到整數b，使得ab-1被n整除，即：

ab≡1(modn)

2 RSA算法描述

RSA算法由密鑰的產生、加密算法和解密算法3個部分組成[1]：

（1）密鑰的產生

①產生兩個大素數p和q；

②計算n=p×q，歐拉函數φ(n)=(p-1)(q-1)

③選擇整數e，使其滿足條件：1＜e＜φ(n)，且gcd(e,φ(n) )=1（注：gcd()函數計算兩個數的最大公約數）；

④計算e的逆元d：d?e≡1 modφ(n)（注：由于gcd(e,φ(n) )=1，則d一定存在）；

⑤取序對(e,n)為公鑰，可公開；(d,n)為私鑰，對外保密。

（2）加密算法

將要發送的字符串分割為長度為m＜n的分組，然后對分組mi執行加密運算，得到密文ci：

（3）解密算法

收到密文ci后，接收者使用自己的私鑰執行解密運算，得到明文mi：

3 RSA算法詳細設計

3.1 大素數的產生和測試

Miller-Rabin算法是一種基于概率的素數測試方法，在密碼學的素數產生中，由于該算法的速度快、原理簡單、易于實現，成為進行素數檢測的最佳選擇[5]。

Miller-Rabin算法[6]是對費馬算法改進，它的操作步驟如下：

（1）計算m，滿足n=(2r)m+1；

（2）選擇隨機數a∈[1,n]；

（3）若ammodn=1，或滿足aimmodn=n-1，則n通過隨機數a的測試；

（4）再取不同a要的值對n進行t=5次測試，如果每次測試結果為n是素數，則以高概率判定n是素數。假設n通過t次測試，則判定結果錯誤的概率是1/4t；若只通過一次測試，素數判定的錯誤概率是25%。

生成大素數算法的實現流程圖，如圖1所示。

圖1 大素數生成流程圖

3.2 密鑰e生成模塊

通過3.1節的大素數生成模塊，可以得到大素數p和大素數q，根據歐拉函數φ(n)=(p-1)(q-1)，同時密鑰e與φ(n)互質，根據中國剩余定理可以計算密鑰e。生成密鑰e的算法流程圖如圖2所示。

圖2 密鑰e生成流程圖

3.3 密鑰d生成模塊

通過大素數生成模塊得到大素數p和q，密鑰e生成模塊，根據1=edmod( )p-1(q-1)。利用中國剩余定理計算e的乘法逆元d。

3.4 快速指數算法

得到e后，就可以通過公鑰(e,n)進行加密得到密文C。在RSA加密過程中，為了計算ci≡(mi)emodn，采用快速指數算法[7]。將快速指數算法描述為三元組(M,E,Y)，其初始值為(M,E,Y)=(mi,e,1)。重復執行以下操作：

①若E是奇數，則Y=M*Ymodn，E=E-1;

②若E是偶數，則X=X*Xmodn，E=E/2。

最終，當E=0時，則Y=X^Emodn。

3.5 RSA加密和解密算法設計

根據2節的RSA算法描述和前面描述的大素數產生算法、密鑰e生成算法、求乘法逆元算法、快速指數算法，實現RSA加密/解密算法流程圖如圖3所示。

圖3 RSA算法的流程

4 運行結果與結論

開發環境是VC6.0，使用的語言是VC++，基于對話框應用程序的前提下，完成了RSA算法的加密解密操作，先導入加密密鑰，也就是公鑰(e,n)，然后選擇要加密的.txt文本文件，按下生成密文的按鈕后，就對文本進行了加密，轉化成了另一種不能得知的信息，如4圖中生成密文后面文本框的信息是字母和數字的組合。再按下導入解密密鑰，即通過(d,n)進行解密。從圖4中可以看出密文通過解密恢復了我們能夠看得懂的文本信息。

圖4 RSA加密系統運行結果圖

5 結語

本文研究RSA算法所涉及到的密碼學基礎概念，在此基礎上，分析了RSA算法的基本原理，詳細設計了RSA算法實現的各個子模塊，并在VC環境下，采用C++語言實現了RSA算法。結果表明，使用加密算法產生的密文，能夠被解密算法正確解密。

RSA算法的設計與實現是基于RSA組件的基本算法，隨著通信速率不斷提高，對加密算法的運行效率也有新的要求。只有有效地改進RSA算法各個組成部分的效率，才能適應通信需求，適應新的網絡安全條件。因此，對于RSA算法各組成部分進一步改進，成為今后研究的重要課題。