RSA算法的分析與改進(jìn)

中南林業(yè)科技大學(xué)計(jì)算機(jī)與信息工程學(xué)院 陳鵬飛 何小東

RSA算法的分析與改進(jìn)

中南林業(yè)科技大學(xué)計(jì)算機(jī)與信息工程學(xué)院 陳鵬飛 何小東

RSA算法是一種非對(duì)稱的公鑰加密算法，它廣泛應(yīng)用于數(shù)據(jù)的加密和數(shù)字簽名和身份驗(yàn)證等領(lǐng)域。針對(duì)RSA算法中尋找安全大素?cái)?shù)實(shí)現(xiàn)難度較大，運(yùn)算時(shí)間較長(zhǎng)，本文提出一種簡(jiǎn)潔的大素?cái)?shù)產(chǎn)生的改進(jìn)算法。該算法經(jīng)實(shí)驗(yàn)測(cè)試，通過提高了RSA算法中大素?cái)?shù)的生成效率，減少了RSA算法加解密時(shí)間，有效地提高了RSA算法的效率。

素?cái)?shù)；RSA算法；加密與解密

1 引言

近些年,隨著計(jì)算機(jī)的普及與計(jì)算機(jī)網(wǎng)絡(luò)的快速發(fā)展和廣泛應(yīng)用,信息安全變得越來(lái)越重要。信息安全的基礎(chǔ)是密碼學(xué)。為了保證數(shù)據(jù)的安全,通常需要對(duì)數(shù)據(jù)加密,目前常用加密算法有:對(duì)稱加密算法和非對(duì)稱加密算法。對(duì)稱加密算法體系(如DES算法、AES算法),非對(duì)稱加密的算法體系(如RSA算法、Elgamal算法,ECC算法)。RSA算法是一種非對(duì)稱的公鑰加密算法,它是目前公認(rèn)在理論和實(shí)際應(yīng)用中最為成熟和完善的一種公鑰密碼體制。從目前應(yīng)用的角度看,軟件實(shí)現(xiàn)的RSA已經(jīng)開始廣泛的運(yùn)用于計(jì)算機(jī)網(wǎng)絡(luò)數(shù)據(jù)加密,密鑰分配,數(shù)字簽名與身份認(rèn)證等領(lǐng)域[2]。

RSA算法的基礎(chǔ)是數(shù)論的歐拉定理,其安全性依賴于大數(shù)的因數(shù)分解,即依賴于RSA算法中的512bit以上的安全大素?cái)?shù),但是安全大素?cái)?shù)尋找相對(duì)困難且運(yùn)算時(shí)間較長(zhǎng)。目前,國(guó)內(nèi)外針對(duì)RSA加密算法的研究也主要集中在效率和安全性兩個(gè)方面。大素?cái)?shù)的生成在RSA算法中很重要,為了確保RSA算法的安全性,只能使素?cái)?shù)的位數(shù)增加,但素?cái)?shù)的位數(shù)增加以后,為了避免降低算法的效率,就要求加快素?cái)?shù)的生成效率[3]。本文針對(duì)RSA加密算法的特點(diǎn),提出一種簡(jiǎn)潔的大素?cái)?shù)產(chǎn)生的改進(jìn)算法。通過提高了RSA算法中大素?cái)?shù)的生成效率,以提高RSA算法的運(yùn)行速度,并在Microsoft Visual Studio 2013中編寫程序并測(cè)試與驗(yàn)證。

2 產(chǎn)生素?cái)?shù)的算法

RSA算法是建立在“大數(shù)分解和素?cái)?shù)檢測(cè)”的理論基礎(chǔ)上,素?cái)?shù)的產(chǎn)生效率也決定了RSA算法的性能。RSA算法的安全性是基于大數(shù)分解的難度,其中生成的公鑰與私鑰是一對(duì)大素?cái)?shù)的函數(shù)。從公開的密鑰和密文中恢復(fù)出明文的難度,等同于分解兩個(gè)大 素?cái)?shù)的乘積[4]。素?cái)?shù)(質(zhì)數(shù))是對(duì)于正整數(shù)p(p〉1),p的因子僅為1和p本身。RSA算法原理如下:

③隨機(jī)選取一個(gè)數(shù)作加密密鑰e(1〈e〈φ(n)),使e和φ(n)互為素?cái)?shù)。

④利用歐幾里德擴(kuò)展算法計(jì)算e的逆元,即解密私鑰d,以滿足,則(n,e)為公鑰, (n,d)為私鑰,e為加密指數(shù),d為解密指數(shù)。

圖1 RSA算法加解密過程

在RSA算法中,關(guān)鍵就在于選取兩個(gè)大素?cái)?shù)p和q,它是后面步驟的基礎(chǔ)。但是如何判別一個(gè)整數(shù)是素?cái)?shù)一直是RSA算法中的難點(diǎn)。傳統(tǒng)的素?cái)?shù)生成方法是先隨機(jī)選擇一個(gè)或者多個(gè)較大的奇整數(shù),然后來(lái)測(cè)試選取的大數(shù)是否為素?cái)?shù)。一般方法如下∶

(1)隨機(jī)生成一個(gè)大奇整數(shù)N(可以利用隨機(jī)數(shù)產(chǎn)生器)。

(2)隨機(jī)選擇一個(gè)整數(shù)a(a〈N)。

(3)然后進(jìn)行素性測(cè)試,如果N沒有通過測(cè)試,則拒絕N,并轉(zhuǎn)到步驟(1)。

(4)如果N通過測(cè)試足夠多次,則接受N;否則轉(zhuǎn)到步驟(2)。

其中,進(jìn)行素性測(cè)試主要采用的是概率性檢測(cè)方法(如Miller-Rabin素性測(cè)試),即判定一個(gè)數(shù)是素?cái)?shù)比較難,但否定它是素?cái)?shù)則要容易得多。Miller-Rabin算法描述如下:為了測(cè)試一個(gè)奇整數(shù)N是素?cái)?shù),對(duì)隨機(jī)選擇的整數(shù)a(1〈a〈N-1),重復(fù)調(diào)用Test(N),如果某個(gè)時(shí)刻Test返回“合數(shù)”,則N一定不是素?cái)?shù);如果Test連續(xù)t次返回“不確定”,當(dāng)t足夠大的時(shí)候,則可以說(shuō)明N是素?cái)?shù)。上述算法可以表示如下:Test(N)

(2)隨機(jī)選擇一個(gè)整數(shù) a(1≤a≤N-1);

(4)如果h=1或h=N-1,則N通過測(cè)試,N可能是素?cái)?shù),測(cè)試結(jié)束;

(6)若h=1,則N不是素?cái)?shù);如果h=N-1,N可能是素?cái)?shù),測(cè)試結(jié)束;

在上述Miller-Rabin素性測(cè)試算法中,當(dāng)N通過一次測(cè)試,則有25%的概率判定N不是素?cái)?shù),因此可以計(jì)算得出,如果N通過t次測(cè)試,N是素?cái)?shù)的概率為(1-()),當(dāng)t=5時(shí),N是素?cái)?shù)的概率已經(jīng)有99.90%[5]。但是傳統(tǒng)的素?cái)?shù)產(chǎn)生方法比較復(fù)雜、耗時(shí)較長(zhǎng)、不易理解,而且目前尚沒有較好的方法來(lái)生成兩個(gè)大素?cái)?shù)p和q。因此,本文對(duì)RSA中素?cái)?shù)的產(chǎn)生算法進(jìn)行改進(jìn),提出一種簡(jiǎn)潔的大素?cái)?shù)產(chǎn)生的改進(jìn)算法。算法實(shí)現(xiàn)的步驟如下:

S1∶可設(shè)置生成大素?cái)?shù)的位數(shù)nbite;

S2∶隨機(jī)產(chǎn)生一個(gè)nbite位大整數(shù)Bignumber,并設(shè)置最高位和最低位都為1(最高位為1確保素?cái)?shù)達(dá)到要求的位數(shù),最低位為1確保它是奇數(shù));

S3∶選取j(自定)個(gè)小素?cái)?shù),存儲(chǔ)到數(shù)組Primes[i]中,每次偏移量為2;

S6∶如果y=0,表示無(wú)余數(shù),表示該數(shù)不是素?cái)?shù),退出循環(huán),否則,ii+1,轉(zhuǎn)到S2。

S7∶如果y不為0,則返回輸出這個(gè)大數(shù);

S8∶然后進(jìn)行5次Miller-Rabin素性測(cè)試,通過測(cè)試,輸出這個(gè)素?cái)?shù),否則,轉(zhuǎn)到S2。

在S2中隨機(jī)產(chǎn)生一個(gè)nbite為大數(shù),本文采用了隨機(jī)遞增法:算法描述如下:

(1)隨機(jī)選取一個(gè)nbite位大數(shù)N;

(2)對(duì)N進(jìn)行素性檢測(cè),如果滿足條件則返回N,否則轉(zhuǎn)到(3);

(3)N=N+b(b是一個(gè)常數(shù)),轉(zhuǎn)到步驟(2)。

本文在Miller-Rabin素性測(cè)試中,首先分解N-1=(b為奇數(shù))時(shí),用b來(lái)替換指數(shù)(N-1)/2,來(lái)提高算法的效率。其實(shí)現(xiàn)的算法如下:

i=0,b=N-1;

While(b%2==0)

{ t=t+2;b/ =4;

if(b不為整數(shù))

{ t--;b* =2;

}

}

3 改進(jìn)后的素?cái)?shù)產(chǎn)生算法的驗(yàn)證

(1)實(shí)驗(yàn)環(huán)境:采用的主要硬件環(huán)境為:CPU Intel(R)Core(TM)i3 M 380 @2.53GHz,內(nèi)存為4GB,500G硬盤。操作系統(tǒng)∶window7旗艦版(x64)。

開發(fā)工具:Microsoft Visual Studio 2013。

用C++程序設(shè)計(jì)語(yǔ)言在Microsoft Visual Studio 2013中編寫程序并測(cè)試。

(2)實(shí)驗(yàn)結(jié)果:實(shí)驗(yàn)中可設(shè)置生成大素?cái)?shù)的位數(shù)32,64,128,256等(則可以產(chǎn)生相應(yīng)位數(shù)的密鑰)。本文測(cè)試了當(dāng)大素?cái)?shù)位數(shù)為32位和64位時(shí),所產(chǎn)生的公鑰與私鑰,并對(duì)密鑰進(jìn)行了十六進(jìn)制轉(zhuǎn)化,結(jié)果分別如圖2和圖3所示。

圖2 素?cái)?shù)為32位時(shí)生成的密鑰

圖3 素?cái)?shù)為64位時(shí)生成的密鑰

由圖2和圖3可見,本文改進(jìn)后的算法可以產(chǎn)生不同位數(shù)大素?cái)?shù)的情況下的相應(yīng)密鑰,證明該算法是可行的。

4 RSA算法測(cè)試結(jié)果與分析

在前述的實(shí)驗(yàn)環(huán)境中,本文對(duì)RSA算法進(jìn)行了實(shí)驗(yàn),對(duì)明文、密鑰和密文都進(jìn)行了16進(jìn)制的轉(zhuǎn)化,并測(cè)試了RSA算法加密與解密的時(shí)間。在實(shí)驗(yàn)中設(shè)置生成大素?cái)?shù)的位數(shù)為32位和64位,輸入明文為:“abcdefghijklmnopqr stuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789”。實(shí)驗(yàn)結(jié)果分別如圖4和圖5所示。

圖4 素?cái)?shù)為32位RSA算法加解密時(shí)間的測(cè)試

圖5 素?cái)?shù)為64位RSA算法加解密時(shí)間的測(cè)試

從圖4和圖5兩圖可見,在明文大小相同的情況下,使用同一種算法,隨著大素?cái)?shù)位數(shù)的增加,密鑰長(zhǎng)度變長(zhǎng), RSA算法加解密時(shí)間也越長(zhǎng);也可以測(cè)試出,在密鑰長(zhǎng)度相同的情況下,隨著明文長(zhǎng)度的增加,加解密時(shí)間也相應(yīng)的增加。可見,本文改進(jìn)后的算法實(shí)現(xiàn)了密鑰的產(chǎn)生和明文的加密與密文的解密,較好的實(shí)現(xiàn)了RSA算法。

RSA算法加密與解密時(shí)間分別是指對(duì)明文進(jìn)行加密與對(duì)密文進(jìn)行解密的時(shí)間。RSA算法的加解密速度一直是人們研究的重點(diǎn)。在前述實(shí)驗(yàn)環(huán)境中,采用上述的測(cè)試文本(明文)和1024位模數(shù)(大素?cái)?shù)長(zhǎng)度為512位),采用傳統(tǒng)的素?cái)?shù)產(chǎn)生算法和本文改進(jìn)后的素?cái)?shù)產(chǎn)生算法進(jìn)行了5次測(cè)試,其結(jié)果見表1。

表1 測(cè)試結(jié)果

從表1可見,采用改進(jìn)后的算法,縮短了RSA算法加解密時(shí)間,加解密效率進(jìn)一步提高。本文通過提高RSA算法中大素?cái)?shù)的生成效率,提高了整個(gè)RSA算法的加解密效率,可見,該算法是可行的。

5 結(jié)語(yǔ)

大素?cái)?shù)的生成是構(gòu)造RSA算法中密鑰的關(guān)鍵,因此素?cái)?shù)的生成和測(cè)試一直都是公鑰密碼學(xué)領(lǐng)域研究的一個(gè)重要課題。本文提出了一種改進(jìn)的素?cái)?shù)產(chǎn)生算法,實(shí)現(xiàn)了其密鑰的生成。同時(shí)測(cè)試了不同位數(shù)的大素?cái)?shù)情況下,相應(yīng)RSA算法加密與解密所用的時(shí)間。最后,與傳統(tǒng)的素?cái)?shù)產(chǎn)生算法對(duì)比,通過提高了RSA算法中大素?cái)?shù)的生成效率,使整個(gè)RSA算法的加解密時(shí)間進(jìn)一步減少,效率進(jìn)一步提高。

［1］譚浩強(qiáng).C++程序設(shè)計(jì)(第2版)［M］.北京:清華大學(xué)出版社,2011.

［2］盧秀慧,楊瑞峰,賈建芳.RSA加密算法的快速實(shí)現(xiàn)［J］.沈陽(yáng)建筑大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,28(6):1143-1147.

［3］高雪寒.大數(shù)相除快速算法在RSA中的應(yīng)用與研究［D］.西安:陜西師范大學(xué),2014.

［4］湯鵬志,李彪.基于頻率的大素?cái)?shù)高效生成算法［J］.華東交通大學(xué)學(xué)報(bào),2011,28(5):52-56.

［5］孫偉.公鑰RSA加密算法的改進(jìn)與實(shí)現(xiàn)［D］.合肥:安徽大學(xué),2014.

陳鵬飛（1990—），男，四川南充人，中南林業(yè)科技大學(xué)碩士研究生，研究方向：密碼學(xué)與網(wǎng)絡(luò)信息安全。