一種公開密鑰ＲＳＡ算法的實現(xiàn)

石瑩瑩　李　濤

（安徽理工大學(xué)計算機科學(xué)與工程學(xué)院，安徽淮南232001）

摘要： 主要針對公開密鑰RSA算法在面向?qū)ο缶幊谭椒╒isual C++ 6.0下的實現(xiàn)，系統(tǒng)地給 出了類的定義、核心函數(shù)的實現(xiàn)流程和使用的主要計算機算法。使算法實現(xiàn)較傳統(tǒng)的實現(xiàn) 方法代碼更容易重用、數(shù)據(jù)有更好的封裝性和安全性、實現(xiàn)流程更清晰。通過算法的選取 和優(yōu)化，獲得了較傳統(tǒng)實現(xiàn)方法更好的系統(tǒng)性能。

關(guān)鍵詞：公鑰；私鑰；RSA；面向?qū)ο缶幊谭椒?/p>

中圖分類號：TP301.6文獻標(biāo)識碼：A[WT]文章編號：16721098(2008)02007003

The Realization of RSA Algorithm for Public Encryption Key

SHI Yingying,LI Tao

(School of Computer Science and Engineering,Anhui University of Science and Tec hnology,Huainan Anhui 232001,China) Abstract: In the paper the realization of RSA algorithm for public encryption ke y based onVisual C++ 6.0 was presented. Class definition, flow charts of kerne l functions and the computer algorithm were given. Realization of RSA in OOP mak es the code easier to be reused, dataencapsulation better and safer, and flowcharts clearer than the previous realization methods. By optimized algorithm bet ter system performance than the previous realization methods was obtained.

Key words:public encryption key; private key; RSA; object oriented programming

隨著計算機的普及和網(wǎng)絡(luò)的飛速發(fā)展，數(shù)據(jù)的安全性問題顯得日益重要，數(shù)據(jù)的破壞和泄密 會造成重大損失。數(shù)據(jù)加密算法可以很好地保護數(shù)據(jù)。加密算法可以分為兩大類，對稱加密 算法和公開密鑰算法。公開密鑰算法主要被用來解決網(wǎng)上密鑰的交換問題和身份認證、數(shù)字 簽名。

公開密鑰算法的概念是密碼學(xué)發(fā)展史上具有里程碑意義的一件大事［1］，與傳統(tǒng)對 稱密碼體制（即加、解密密碼相同）相同，公鑰系統(tǒng)使用兩個密鑰：加密密碼可以 公開，稱為公鑰；解密密鑰保密為私鑰。產(chǎn)生公鑰體制的內(nèi)在動力有兩個：第一傳統(tǒng)對稱體 制下密碼的分配問題；第二信息的數(shù)字簽證問題，即如何為數(shù)字化的消息或文件提供一種類 似于為書面文件手寫簽證的方法。

RSA算法已經(jīng)經(jīng)受了多年深入的密碼分析，雖然密碼分析者目前既不能證明其安 全性 但也不能否定其安全性，這恰恰說明該算法有很高的實用可信度。本文主要討論RSA算 法在面向?qū)ο缶幊谭椒ㄏ碌木唧w計算機算法實現(xiàn)。

1RSA算法的基本原理簡介

在公鑰系統(tǒng)觀點之后，文獻［2］提出了第一個比較完善的公鑰密碼算法，這就是著名的RSA 算法。RSA算法描述

(1)選取兩個大素數(shù),玴q；

(2)計算,玭=pq,φ(n)=(p-1)(q-1)；

(3)隨機選擇玠∶1＜d＜φ(n),((d,φ(n))=1；

(4)計算玡∶ed≡1(mod φ(n))；

(5)加密運算對任意明文玬∈zn=｛0,1,…,n-1｝，加密后的密文為c，這里c= m琫玬od n；

(6)解密對密文玞∈zn，明文m=c琩玬od n。

在上面六個步驟中，玭，e公開，n稱為模數(shù)，e稱為加密指數(shù)即公鑰；p，q，φ(n)，d保密 ，φ(n)為Euler函數(shù)，玠稱為解密指數(shù)，即私鑰。解密的正確性證明［3］93略 。

2RSA算法的安全性分析

公鑰體制的安全性是指計算上的安全性。RSA算法的安全性建立在大數(shù)的因數(shù)分解是困難的 這一現(xiàn)實之上，竊聽者要解密密文玞，除了窮舉攻擊外，只能是像合法用戶一樣擁有d，而 求d應(yīng)先求φ(n)，而求φ(n)應(yīng)先求p和q，而求p和q就要分解n，因此破解RSA算法相當(dāng)于 做大數(shù)的因數(shù)分解。

3RSA算法的實現(xiàn)細節(jié)

結(jié)合上面1中的六個步驟，下面討論RSA的實現(xiàn)過程中應(yīng)考慮的細節(jié)問題。

3.1大素數(shù)和的選擇

(1) 玴和q多大合適從安全性角度考慮，選擇多大的素數(shù)，取決于因數(shù)分解的能力。目 前已經(jīng)能夠分解130位的十進制數(shù)，所以用戶應(yīng)當(dāng)選擇玴,q數(shù)為100位的十進制數(shù)，這樣 玭將達到200位，從而使現(xiàn)有的分解攻擊失效。

(2) 大素數(shù)的生成目前生成大素數(shù)的方法都是概率型的合數(shù)檢測算法，其原理是 ：對生成的隨機數(shù)進行合數(shù)測試，若該數(shù)通過測試，說明其為合數(shù)，否則該數(shù)可能為素數(shù)， 當(dāng)進行多次測試后，該數(shù)均未通過測試，那么這個數(shù)為素數(shù)的概率將非常大。

既然是概率算法，就有可能有把一個合數(shù)當(dāng)作一個素數(shù)用于RSA系統(tǒng)，此時所關(guān)心的問題 是：解密可否進行及系統(tǒng)的安全性會否降低［4］。因此，應(yīng)該首選不受影響系統(tǒng)的 素數(shù)生成算法，如可選用SolovayStrassen算法、MillerRabin算法。

(3) ｜p-q｜要適當(dāng)大因為[SX(](p+q)2[]4[SX)]-n=[SX(](p-q)2[]4[SX)] ，如果｜p-q｜較小，則[SX(](p-q)2[]4[SX)]也較小，因此[SX(](p+q)2[]4[SX)] 稍大于n，也即[SX(]p+q[]2[SX)]稍大于[KF(]n[KF)]，可得如下分解nУ牟街瑁孩 順 序檢查大于[KF(]n[KF)]的每一個整數(shù)x，使得x2-n為某一整數(shù)y的完全平方，即 x2-n=y2В虎 由x2-n=y2可得n的分解形式n=(x+y)(x-y)，б話愣言，玴和q的二進制表示應(yīng)當(dāng)相差幾個比特。

(4) 玴-1和q-1都應(yīng)當(dāng)有大的素因子這一選擇要求是針對RSA的模數(shù)玭的Pollard玴 -1因子分解攻擊和循環(huán)加密攻擊。一般的解決方法是：先生成大素數(shù)玴1，q1,然后 令p=2p1+1，q=2q1+1，這樣生成的p，q均為素數(shù)且p-1和q-1都有大的素因子。

(5) (p-1,q-1)應(yīng)較小假若(p-1,q-1)較大，從而p-1和q-1的最小公倍數(shù)，記做u，將會較??；另外滿足：ed≡ 1(mod φ(n))的d一定滿足ed≡1(mod u)，所以在u較小的情況下可以窮舉方法找到d 。

3.2玠,e的選擇

玠不能太小，以免窮舉攻擊。研究結(jié)果表明：一般e＜n,d＜[KF(S]4[]n[KF)]時，d是較 容易確定的，這也是實現(xiàn)RSA系統(tǒng)時應(yīng)先選擇玠的原因，選擇完d后，可以用擴展的歐幾里 德算法計算出e，其依據(jù)是［5］：若(d,φ(n))=1，則存在整數(shù)s,t使得sd+tφ(n)=1 成立。d,e的選擇要在安全性和系統(tǒng)性的有效性之間做出折中。

3.3模指數(shù)運算

在加、解密過程中要考慮形如：玿瑀(mod 玭)的模指數(shù)運算，為提高運算速度和 節(jié)約存儲空間，一般采用如下快速算法［3］124

(1) 玜←x,b←r,c←1；

(2) 如果玝=0則輸出c，結(jié)束；

(3) 若玝(mod2)≠0，則轉(zhuǎn)(5)；

(4) 玝←[SX(]b[]2[SX)],a←(a?a)(mod 玭)轉(zhuǎn)(3)；

⑤ 玝←[SX(]b[]1[SX)],c←(c?a)(mod 玭)轉(zhuǎn)(2)。

3.4不同用戶應(yīng)當(dāng)使用不同的模數(shù)

這樣要求的原因是存在著對RSA的如下攻擊方法：設(shè)兩個用戶共用一個模數(shù)玭，公鑰分別為 e1,e2，且(e1,e2)=1，用RSA為他們加密同一消息玬，則密文分別為c1=m琫1(mod n),c2=m琫2(玬od n)；竊聽者截獲密文c1,c2后，可 以 如下恢復(fù)出m：① 用擴展的歐幾里德算法求出，滿足玶e1+se2=1的兩個整數(shù)r,s（不妨設(shè)r＜0 以及c在(mod n)下的逆元c-11；② 計算(c-11)-rc 瑂2(mod n)就可得到明文m。

當(dāng)用戶的私鑰玠泄露后，不僅要更換d，而且要更換模數(shù)n。這是因為：如果某人獲得了 一個求玠的算法A，則可構(gòu)造一個以A為子程序的算法［6］ 來分解n，因此在泄露私鑰d后僅僅簡單的更換d而保留原來的n是不安全的。

4主要成員函數(shù)實現(xiàn)流程及其算法

求最大公約數(shù)可以使用歐幾里德算法，它是幸存到現(xiàn)在的最古老的非凡算法，至今還是可用 的。下面給出算法的Visual C++語言描述：

int god(int 玿,int 珁){

int 玤;

判斷取相反數(shù);

if(玿+y==0)

ERROR;

玤=y;

while(玿>0){

取模;}return 玤;}

這個算法可以推廣成返回由玬個數(shù)組成的god數(shù)組。

求模逆元問題等價于尋找一個玿使得： (A?x)玬od n=1，x就是A模n 的逆元?？捎脕砬竽Ｄ?元的算法很多，使用擴展的歐幾里德算法求模逆元。下面給出算法的Visual C++語言描述：

main(int arg 玞,char **arg 玽){

int 玜,b,god;

if(arg 玞<3){ヅ卸鮮涑;

}int 玼=atoi(atg 玽［1］);int 玽=atoi(arg 玽［2］);

判斷輸出;}ExtBinEuclid(&玼,&玽,&玜,&玝,&玤od);

cout<<玜<<"*"<<玼<<"+(-"<<玝<<")*<<玽<<"="<<玤od<

if(玤od==1)

輸出結(jié)果;

return 0;

}ゴ慫惴ㄍü迭代運算來實現(xiàn)的，對于大的整數(shù)，其運行可能較慢。Knuth指出這個算法完成 的除法的平均數(shù)目是［7］0.843×log2 n+1.47。

5總結(jié)

面向?qū)ο蟮母拍钤缭谏蟼€世紀60年代就已經(jīng)被提出了，發(fā)展至今已經(jīng)相當(dāng)成熟。面向?qū)ο缶?程方法提出了類的封裝概念、代碼重用的繼承性和對象一致操作的多態(tài)性。這些特性使在實 現(xiàn)RSA算法時，可以更好地對敏感數(shù)據(jù)進行封裝、代碼得到重用、獲得更清晰的程序流程。 從而使算法實現(xiàn)更加安全、更短的開發(fā)周期、更好的系統(tǒng)可展性。多態(tài)性可以對算法對象進 行一致性操作，使代碼更規(guī)范、一致。

一個密碼系統(tǒng)的設(shè)計不僅要有好的算法，實現(xiàn)過程中的細節(jié)同樣不可忽視。此外，在具體的 應(yīng)用時還應(yīng)當(dāng)考慮到協(xié)議的設(shè)計細節(jié)，因為敵手除了攻擊算法外，還可能攻擊協(xié)議。密碼學(xué) 是一個不斷發(fā)展的學(xué)科，多年來加密算法設(shè)計者和密碼分析家在不停地努力，促進密碼科學(xué) 的進步。一個好的密碼學(xué)算法可以經(jīng)得起多年的密碼分析，但如果沒有一個好的實現(xiàn)方法， 其安全性也是無從談起的。好的實現(xiàn)方法可以使用戶得到近似密碼算法理論上的安全性和更 高效的性能。

參考文獻：

［1］周玉潔，馮登國.公開密鑰算法及其快速實現(xiàn)［M］.北京：國防工業(yè)出版社 ，2002：78.

［2］R L RIVEST,A SHAMIR,L ADLEMAN.A Mehod for Obtaining DigitalSignatures and Publickey Cryptosystem［J］.CommACM,1978,21(2):120126.

［3］陳魯生, 沈世鎰. 現(xiàn)代密碼學(xué)［M］.北京:科學(xué)出版社,2002：5772.

［4］ARTO SALOMAA.公鑰密碼學(xué)［M］. 吳世忠，譯.北京: 國防工業(yè)出版社,1998：7096.

［5］閔嗣鶴, 嚴士健. 初等數(shù)論［M］.第2版.北京:高等教育出版社,1988 ：3642.

［6］馮登國, 林東岱, 吳文玲. 密碼學(xué)導(dǎo)引［M］.北京:科學(xué)出版社,1999：23 55.

［7］BRUCE SCHNEIER(美),應(yīng)用密碼學(xué)［M］.吳世忠，譯.北京:機械工業(yè)出 版社,2006：102118.

(責(zé)任編輯：李麗)