RSA算法的研究與實(shí)現(xiàn)

弋改珍

（咸陽(yáng)師范學(xué)院計(jì)算機(jī)學(xué)院，咸陽(yáng) 712000）

0 引言

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的加密和解密算法。

1 RSA中的密碼學(xué)基礎(chǔ)知識(shí)

密碼學(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)

2 RSA算法描述

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：

3 RSA算法詳細(xì)設(shè)計(jì)

3.1 大素?cái)?shù)的產(chǎn)生和測(cè)試

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ù)生成流程圖

3.2 密鑰e生成模塊

通過(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生成流程圖

3.3 密鑰d生成模塊

通過(guò)大素?cái)?shù)生成模塊得到大素?cái)?shù)p和q，密鑰e生成模塊，根據(jù)1=edmod( )p-1(q-1)。利用中國(guó)剩余定理計(jì)算e的乘法逆元d。

3.4 快速指數(shù)算法

得到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。

3.5 RSA加密和解密算法設(shè)計(jì)

根據(jù)2節(jié)的RSA算法描述和前面描述的大素?cái)?shù)產(chǎn)生算法、密鑰e生成算法、求乘法逆元算法、快速指數(shù)算法，實(shí)現(xiàn)RSA加密/解密算法流程圖如圖3所示。

圖3 RSA算法的流程

4 運(yùn)行結(jié)果與結(jié)論

開(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é)果圖

5 結(jié)語(yǔ)

本文研究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)，成為今后研究的重要課題。