石瑩瑩　李　濤

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

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

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

中圖分類(lèi)號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí)碼：A[WT]文章編號(hào)：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

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

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

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

1RSA算法的基本原理簡(jiǎn)介

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

(1)選取兩個(gè)大素?cái)?shù),玴q；

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

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

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

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

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

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

2RSA算法的安全性分析

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

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

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

3.1大素?cái)?shù)和的選擇

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

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

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

(3) ｜p-q｜要適當(dāng)大因?yàn)閇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)]的每一個(gè)整數(shù)x，使得x2-n為某一整數(shù)y的完全平方，即 x2-n=y2В虎 由x2-n=y2可得n的分解形式n=(x+y)(x-y)，б話(huà)愣言，玴和q的二進(jìn)制表示應(yīng)當(dāng)相差幾個(gè)比特。

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

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

3.2玠,e的選擇

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

3.3模指數(shù)運(yùn)算

在加、解密過(guò)程中要考慮形如：玿瑀(mod 玭)的模指數(shù)運(yùn)算，為提高運(yùn)算速度和 節(jié)約存儲(chǔ)空間，一般采用如下快速算法［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不同用戶(hù)應(yīng)當(dāng)使用不同的模數(shù)

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

當(dāng)用戶(hù)的私鑰玠泄露后，不僅要更換d，而且要更換模數(shù)n。這是因?yàn)椋喝绻橙双@得了 一個(gè)求玠的算法A，則可構(gòu)造一個(gè)以A為子程序的算法［6］ 來(lái)分解n，因此在泄露私鑰d后僅僅簡(jiǎn)單的更換d而保留原來(lái)的n是不安全的。

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

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

int god(int 玿,int 珁){

int 玤;

判斷取相反數(shù);

if(玿+y==0)

ERROR;

玤=y;

while(玿>0){

取模;}return 玤;}

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

求模逆元問(wèn)題等價(jià)于尋找一個(gè)玿使得： (A?x)玬od n=1，x就是A模n 的逆元?？捎脕?lái)求模逆 元的算法很多，使用擴(kuò)展的歐幾里德算法求模逆元。下面給出算法的Visual C++語(yǔ)言描述：

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;

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

5總結(jié)

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

一個(gè)密碼系統(tǒng)的設(shè)計(jì)不僅要有好的算法，實(shí)現(xiàn)過(guò)程中的細(xì)節(jié)同樣不可忽視。此外，在具體的 應(yīng)用時(shí)還應(yīng)當(dāng)考慮到協(xié)議的設(shè)計(jì)細(xì)節(jié)，因?yàn)閿呈殖斯羲惴ㄍ猓€可能攻擊協(xié)議。密碼學(xué) 是一個(gè)不斷發(fā)展的學(xué)科，多年來(lái)加密算法設(shè)計(jì)者和密碼分析家在不停地努力，促進(jìn)密碼科學(xué) 的進(jìn)步。一個(gè)好的密碼學(xué)算法可以經(jīng)得起多年的密碼分析，但如果沒(méi)有一個(gè)好的實(shí)現(xiàn)方法， 其安全性也是無(wú)從談起的。好的實(shí)現(xiàn)方法可以使用戶(hù)得到近似密碼算法理論上的安全性和更 高效的性能。

參考文獻(xiàn)：

［1］周玉潔，馮登國(guó).公開(kāi)密鑰算法及其快速實(shí)現(xiàn)［M］.北京：國(guó)防工業(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］. 吳世忠，譯.北京: 國(guó)防工業(yè)出版社,1998：7096.

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

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

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

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