弋改珍
(咸陽(yáng)師范學(xué)院計(jì)算機(jī)學(xué)院,咸陽(yáng) 712000)
RSA算法是一種迄今為止理論上比較成熟和完善的公鑰密碼體制,是非對(duì)稱(chēng)密碼體制的典型代表[1]。在網(wǎng)絡(luò)、信息安全等許多方面都使用RSA算法,特別是RSA算法典型應(yīng)用在通信中的數(shù)字簽名,可實(shí)現(xiàn)對(duì)手的身份、不可抵賴(lài)性驗(yàn)證。在身份認(rèn)證、信息安全、電子商務(wù)中有著廣泛的應(yīng)用前景。
本文介紹了應(yīng)用于RSA算法中的密碼學(xué)基礎(chǔ)知識(shí),分析了RSA算法的原理與實(shí)現(xiàn)步驟,詳細(xì)分析了RSA實(shí)現(xiàn)過(guò)程中用到的算法,并在VC環(huán)境下,用C++開(kāi)發(fā)語(yǔ)言實(shí)現(xiàn)了RSA的加密和解密算法。
密碼學(xué)實(shí)質(zhì)上體現(xiàn)了數(shù)論知識(shí)的應(yīng)用,每一個(gè)加密算法體現(xiàn)了不同加密理論,而加密理論又涉及了數(shù)論知識(shí)。所以,數(shù)論知識(shí)是加密算法的基礎(chǔ)。
定義1(互質(zhì)關(guān)系)[2]:如果兩個(gè)正整數(shù),除了1以外,沒(méi)有其他公因子,則稱(chēng)這兩個(gè)數(shù)是互質(zhì)關(guān)系,即互素。
性質(zhì)1兩個(gè)正整數(shù)互素的性質(zhì)[3]:
①任意兩個(gè)質(zhì)數(shù)構(gòu)成互質(zhì)關(guān)系;
②假設(shè)有個(gè)質(zhì)數(shù),后面找到一個(gè)數(shù)不和前面那個(gè)質(zhì)數(shù)成倍數(shù)關(guān)系,則它們就互質(zhì);
③所有的自然數(shù)和1都互質(zhì);
④p是大于 1的整數(shù),則p-1和p構(gòu)成互質(zhì)關(guān)系;
⑤p是大于 1的奇數(shù),則p和p-2構(gòu)成互質(zhì)關(guān)系。
定義2(歐拉函數(shù))[3]:設(shè)n為正整數(shù),以φ()n表示不超過(guò)n且與n互素的正整數(shù)的個(gè)數(shù),φ()n稱(chēng)為n的歐拉函數(shù)值。
定理1(歐拉定理)[4]:如果a和n兩個(gè)正整數(shù)是互質(zhì)關(guān)系,那么n的歐拉函數(shù)φ(n)滿(mǎn)足:
上式說(shuō)明,a的φ(n)次方除n后的余數(shù)是1。
定理2(中國(guó)剩余定理)[4]:若a與p1互質(zhì),a<p1;b與p2互質(zhì),b<p2;c與p1p2互質(zhì),c<p1p2。那么,c與數(shù)對(duì)(a,b)是一一對(duì)應(yīng)關(guān)系。由于a的值有φ(p1)種可能,b的值有φ(p2)種可能,那么數(shù)對(duì)(a,b)有φ(p1)φ(p2)種可能,而c的值有φ(p1p2)種可能。則φ(p1p2)=φ(p1)φ(p2)。
定理3(費(fèi)馬小定理)[4]:若a是正整數(shù),n是質(zhì)數(shù),質(zhì)數(shù)n滿(mǎn)足φ(n)等于p-1,a和n互質(zhì),則:
an-1≡1(modn)
定義3(模反元素)[4]:如果兩個(gè)整數(shù)a和n互質(zhì),那么一定可找到整數(shù)b,使得ab-1被n整除,即:
ab≡1(modn)
RSA算法由密鑰的產(chǎn)生、加密算法和解密算法3個(gè)部分組成[1]:
(1)密鑰的產(chǎn)生
①產(chǎn)生兩個(gè)大素?cái)?shù)p和q;
②計(jì)算n=p×q,歐拉函數(shù)φ(n)=(p-1)(q-1)
③選擇整數(shù)e,使其滿(mǎn)足條件:1<e<φ(n),且gcd(e,φ(n) )=1(注:gcd()函數(shù)計(jì)算兩個(gè)數(shù)的最大公約數(shù));
④計(jì)算e的逆元d:d?e≡1 modφ(n)(注:由于gcd(e,φ(n) )=1,則d一定存在);
⑤取序?qū)?e,n)為公鑰,可公開(kāi);(d,n)為私鑰,對(duì)外保密。
(2)加密算法
將要發(fā)送的字符串分割為長(zhǎng)度為m<n的分組,然后對(duì)分組mi執(zhí)行加密運(yùn)算,得到密文ci:
(3)解密算法
收到密文ci后,接收者使用自己的私鑰執(zhí)行解密運(yùn)算,得到明文mi:
Miller-Rabin算法是一種基于概率的素?cái)?shù)測(cè)試方法,在密碼學(xué)的素?cái)?shù)產(chǎn)生中,由于該算法的速度快、原理簡(jiǎn)單、易于實(shí)現(xiàn),成為進(jìn)行素?cái)?shù)檢測(cè)的最佳選擇[5]。
Miller-Rabin算法[6]是對(duì)費(fèi)馬算法改進(jìn),它的操作步驟如下:
(1)計(jì)算m,滿(mǎn)足n=(2r)m+1;
(2)選擇隨機(jī)數(shù)a∈[1,n];
(3)若ammodn=1,或滿(mǎn)足aimmodn=n-1,則n通過(guò)隨機(jī)數(shù)a的測(cè)試;
(4)再取不同a要的值對(duì)n進(jìn)行t=5次測(cè)試,如果每次測(cè)試結(jié)果為n是素?cái)?shù),則以高概率判定n是素?cái)?shù)。假設(shè)n通過(guò)t次測(cè)試,則判定結(jié)果錯(cuò)誤的概率是1/4t;若只通過(guò)一次測(cè)試,素?cái)?shù)判定的錯(cuò)誤概率是25%。
生成大素?cái)?shù)算法的實(shí)現(xiàn)流程圖,如圖1所示。
圖1 大素?cái)?shù)生成流程圖
通過(guò)3.1節(jié)的大素?cái)?shù)生成模塊,可以得到大素?cái)?shù)p和大素?cái)?shù)q,根據(jù)歐拉函數(shù)φ(n)=(p-1)(q-1),同時(shí)密鑰e與φ(n)互質(zhì),根據(jù)中國(guó)剩余定理可以計(jì)算密鑰e。生成密鑰e的算法流程圖如圖2所示。
圖2 密鑰e生成流程圖
通過(guò)大素?cái)?shù)生成模塊得到大素?cái)?shù)p和q,密鑰e生成模塊,根據(jù)1=edmod( )p-1(q-1)。利用中國(guó)剩余定理計(jì)算e的乘法逆元d。
得到e后,就可以通過(guò)公鑰(e,n)進(jìn)行加密得到密文C。在RSA加密過(guò)程中,為了計(jì)算ci≡(mi)emodn,采用快速指數(shù)算法[7]。將快速指數(shù)算法描述為三元組(M,E,Y),其初始值為(M,E,Y)=(mi,e,1)。重復(fù)執(zhí)行以下操作:
①若E是奇數(shù),則Y=M*Ymodn,E=E-1;
②若E是偶數(shù),則X=X*Xmodn,E=E/2。
最終,當(dāng)E=0時(shí),則Y=X^Emodn。
根據(jù)2節(jié)的RSA算法描述和前面描述的大素?cái)?shù)產(chǎn)生算法、密鑰e生成算法、求乘法逆元算法、快速指數(shù)算法,實(shí)現(xiàn)RSA加密/解密算法流程圖如圖3所示。
圖3 RSA算法的流程
開(kāi)發(fā)環(huán)境是VC6.0,使用的語(yǔ)言是VC++,基于對(duì)話(huà)框應(yīng)用程序的前提下,完成了RSA算法的加密解密操作,先導(dǎo)入加密密鑰,也就是公鑰(e,n),然后選擇要加密的.txt文本文件,按下生成密文的按鈕后,就對(duì)文本進(jìn)行了加密,轉(zhuǎn)化成了另一種不能得知的信息,如4圖中生成密文后面文本框的信息是字母和數(shù)字的組合。再按下導(dǎo)入解密密鑰,即通過(guò)(d,n)進(jìn)行解密。從圖4中可以看出密文通過(guò)解密恢復(fù)了我們能夠看得懂的文本信息。
圖4 RSA加密系統(tǒng)運(yùn)行結(jié)果圖
本文研究RSA算法所涉及到的密碼學(xué)基礎(chǔ)概念,在此基礎(chǔ)上,分析了RSA算法的基本原理,詳細(xì)設(shè)計(jì)了RSA算法實(shí)現(xiàn)的各個(gè)子模塊,并在VC環(huán)境下,采用C++語(yǔ)言實(shí)現(xiàn)了RSA算法。結(jié)果表明,使用加密算法產(chǎn)生的密文,能夠被解密算法正確解密。
RSA算法的設(shè)計(jì)與實(shí)現(xiàn)是基于RSA組件的基本算法,隨著通信速率不斷提高,對(duì)加密算法的運(yùn)行效率也有新的要求。只有有效地改進(jìn)RSA算法各個(gè)組成部分的效率,才能適應(yīng)通信需求,適應(yīng)新的網(wǎng)絡(luò)安全條件。因此,對(duì)于RSA算法各組成部分進(jìn)一步改進(jìn),成為今后研究的重要課題。