一種改進的快速RSA 密鑰生成算法

陳 燕

(貴陽學院計算機科學系，貴州貴陽 550002)

0 引言

21 世紀，全世界的計算機都將通過Internet聯(lián)到一起，網(wǎng)絡安全成為至關重要的問題。為了保證計算機信息傳遞的安全性，需要生成密鑰將信息安全傳送，因此，密鑰生成技術是網(wǎng)絡安全中的關鍵技術，也是難點技術［1］。隨著網(wǎng)絡的普及，人們相互間的通信量日益增多，使得密鑰的需求量大大增加，這就使得對密鑰生成的效率要求更高了。因此，如何快速生成高質量的密鑰，保證人們使用網(wǎng)絡的安全需要，成為人們關注的熱點問題。

密鑰生成技術中，關鍵問題就是高質量的素數(shù)生成問題。傳統(tǒng)的密鑰算法在生成密鑰的尋找大素數(shù)過程中，為了得到準確性較高的素數(shù)，需要不斷進行單一冪乘運算循環(huán)，循環(huán)次數(shù)越高，素數(shù)的準確性越高［2－4］。這樣多次循環(huán)的結果是得到了準確性高的素數(shù)，生成了高質量的密鑰，但是，在生成大素數(shù)時，需要依序進行多次循環(huán)運算，本次循環(huán)需用上一次循環(huán)的生成結果計算出更精準的素數(shù)，這樣不僅冪運算的計算量很大，而且只能依序進行單一循環(huán)使得素數(shù)生成耗時過長，多次循環(huán)直接導致生成密鑰的耗時長、效率不高，無法滿足計算機網(wǎng)絡迅速發(fā)展對密鑰生成量的需要。尋找素數(shù)是密鑰生成的關鍵步驟，素數(shù)能否快速準確查找，直接關系到密鑰生成的速率和質量，因此，如何改進傳統(tǒng)密鑰生成方法中，對素數(shù)尋找的低效耗時長問題，成為密鑰生成問題的一個難點。

針對傳統(tǒng)的算法素數(shù)尋找耗時長，密鑰生成效率不高的缺點，本文提出一種改進的快速RSA密鑰生成算法。通過使用改進的滑動窗口算法結合Montgomery模乘和模平方算法，同時生成多組素數(shù)并利用窗函數(shù)從中選取更有效的素數(shù)，避免了傳統(tǒng)方法中多次計算單一循環(huán)而造成密鑰生成效率不高的缺點。實驗證明，這種改進算法能夠快速尋找出素數(shù)，高效生成密鑰，滿足了現(xiàn)代網(wǎng)絡通信對密鑰的需求，取得了滿意的結果。

1 密鑰生成原理

密鑰是在信息傳遞中明文轉換為密文或將密文轉換為明文的算法中輸入的數(shù)據(jù)，是傳遞安全信息的重要保障。密鑰生成主要分為如下幾個步驟。

1 )采用大素數(shù)篩選算法，產(chǎn)生出一個公開的大素數(shù)p。通過構造一個小的素數(shù)集合Su(k)={pi|pi≤k，k∈N}，其中，k是正整數(shù);pi是第i個小的素數(shù)，采用試除法，如文獻［5］中所述，對生成的奇數(shù)d進行篩選，如果不能通過篩選，則對該奇數(shù)d進行遞增2的操作，通過篩選后進入素性測試，即可得到公開大素數(shù)p。

2 )循環(huán)運算產(chǎn)生保密的大素數(shù)q，令n－1=2km，其中，m和n均為正奇數(shù)，n為待測的正奇數(shù)且n＞1。選擇一個隨機整數(shù)a滿足1＜a＜n－1，計算 b0≡ am(mod n)［6］。

5 )銷毀p，q及φ(n)。至此完成了密鑰的生成。

由上述步驟可知，傳統(tǒng)算法需在第2)步生成保密大素數(shù)時，依次進行單一循環(huán)，每次循環(huán)必須用上一循環(huán)中產(chǎn)生的結果bi繼續(xù)進行計算，直至產(chǎn)生符合要求的素數(shù)即結束循環(huán)。由此可知，這種產(chǎn)生保密素數(shù)的方法不僅需要進行多次單獨循環(huán)，而且在每次循環(huán)計算中都要進行大量的冪乘運算，即實現(xiàn)bi≡(mod n)中的大量冪乘運算［8］，這樣使得尋找大素數(shù)時計算量過大，耗時長，直接導致了密鑰生成效率低的問題。

針對傳統(tǒng)算法的缺點，我們設想如果將單一循環(huán)分配給多個循環(huán)同時進行計算，并優(yōu)化冪乘算法，將能有效提高密鑰生成的效率。因此，本文提出一種改進的快速RSA密鑰生成算法。通過使用改進的滑動窗口算法結合Montgomery模乘和模平方算法，同時進行多個循環(huán)生成多組素數(shù)并利用窗函數(shù)從中選取更有效的素數(shù)，這樣就能避免多次計算單一循環(huán)耗時長、計算量大而造成密鑰生成效率不高的缺點。

2 改進的快速RSA密鑰生成算法

根據(jù)密鑰生成算法的原理，對傳統(tǒng)方法進行改進，利用窗函數(shù)和模乘優(yōu)化算法，得到快速RSA密鑰生成算法的方法，下面詳細敘述快速RSA密鑰生成算法的具體步驟。

2.1 公開大素數(shù)

尋找大素數(shù)的通常方法是:隨機生成一個奇數(shù)，然后用概率素性測試算法對該奇數(shù)進行素性測試，反復此步驟直至尋找到為止。

素數(shù)預篩選算法如下

1 )計算機隨機產(chǎn)生n位奇整數(shù)d，令i=0，隨機產(chǎn)生的n位整數(shù)為

5 )按照公式q=q+2，i=i+1計算出其值，然后將循環(huán)流程轉向步驟2)繼續(xù)進行循環(huán)，直至滿足條件循環(huán)即結束。

經(jīng)過上述多步運算，到循環(huán)結束后就完成了大素數(shù)的篩選，最終生成公開大素數(shù)p。

2.2 保密大素數(shù)

在進行模冪運算時，先求冪然后求模，將會出現(xiàn)一個巨大的中間結果，會使實際運算操作變得非常復雜，在此采用模乘操作代替求模冪算法中的乘法操作，保證中間結果的長度不大于模的長度。同時使用改進的滑動窗口算法結合Montgomery模乘和模平方算法來優(yōu)化模冪算法。

優(yōu)化的模冪算法描述如下。

其中，MontMul()和 MontSqu()分別是 Montgomery算法中的模乘函數(shù)及模平方函數(shù)。在傳統(tǒng)的模乘算法中，通常使用大整數(shù)乘法和除法求模乘，這種方法包含除法操作，所以比較耗時且速度較慢，如果將Montgomery求模算法及大整數(shù)乘法算法組合使用，則在2n(n+1)步單精度乘法內(nèi)即可完成模乘算法。組合改進的滑動窗口算法和Montgomery算法，便可得到較優(yōu)的模冪算法

在生成保密大素數(shù)時，將傳統(tǒng)方法中的單一循環(huán)進行改進，分配成多個循環(huán)同時進行運算，利用上文給出的冪乘優(yōu)化算法，在每個循環(huán)中進行冪乘運算產(chǎn)生出多組大素數(shù)，接著將產(chǎn)生的多組大素數(shù)輸入窗函數(shù)中進行篩選，滿足素數(shù)即為滿足條件的保密大素數(shù)，最終將產(chǎn)生的保密大素數(shù)輸出。具體的保密大素數(shù)生成流程圖如圖1所示。

圖1 保密大素數(shù)生成流程圖Fig.1 Confidential big primes generating flow chart

通過將單一循環(huán)分配為多個同時運行的循環(huán)，并優(yōu)化循環(huán)中的冪乘運算，這樣就解決了傳統(tǒng)算法中多次進行單一循環(huán)和大量冪乘運算帶來的耗時長、效率低的問題，快速產(chǎn)生出了高質量的保密大素數(shù)q。

2.3 密鑰生成算法

利用上節(jié)中計算產(chǎn)生的公開大素數(shù)和保密大素數(shù)生成密鑰，密鑰生成分為3個部分:初始密鑰的生成、中間密鑰的生成和子密鑰生成。

1 )初始密鑰的生成。根據(jù)公開大素數(shù)p計算出密鑰位數(shù)為256位，然后根據(jù)保密大素數(shù)生成密鑰，若密鑰的位數(shù)小于256位，則需在最后的有效位后面加一個字符“1”，然后再用字符“0”將密鑰補全為256位。將擴充后得到的256位密鑰等分成8等分ω－8，ω－7，…，ω－1，…。

2 )中間密鑰的生成。利用(5)式將上一步驟中的8等分密鑰擴展到132個32位的中間密鑰ω0，ω1，…，ω131。

3 )子密鑰的生成。通過第2)步中產(chǎn)生的132個中間密鑰后，利用8個四位輸入輸出的S盒生成33個子密鑰，分別記為S0，S1，…，S7。具體生成過程為

對于想得到密鑰保護信息的外來入侵者來說，他只能得到一輪密鑰，要想向前計算找出信息，不但需要對初始密鑰、中間密鑰進行猜測，而目還需要對后一輪的子密鑰進行多次猜測。

改進的密鑰生成算法采用中間密鑰，先經(jīng)過密鑰生成算法步驟擴充初始密鑰，再經(jīng)過多次運算得到132個中間密鑰，最后將中間密鑰經(jīng)過S盒變換后得到子密鑰。可以看出中間密鑰的生成是根據(jù)多項式x8+x7+x5+x3+1生成的，每一個中間密鑰的生成全都依靠該多項式，即每個中間密鑰的生成，不再只是依賴于單獨一輪循環(huán)計算，而是依賴于在此中間密鑰之前的兩輪循環(huán)，這樣即使攻擊者通過某種方法竊取得到某一輪循環(huán)的密鑰，但是由于沒有前一輪循環(huán)的密鑰，因而也無法繼續(xù)向后計算推導，從而保證了向后推導的不可能性，保證了數(shù)據(jù)信息的安全。

2.4 解密密鑰生成

基于上兩節(jié)的內(nèi)容，計算n=pq(公開)以及歐拉函數(shù)Ψ(n)=(p－1)(q－1)，隨機選取整數(shù)e作為加密密鑰，加密密鑰必須滿足gcd(e，ψ(n))=1(公開)。存在一正整數(shù)k，使得de－kφ(n)=1，根據(jù)Derome方法，解密密鑰d可以由(6)式求出。

所以，ψ(ei)遠遠小于ψ(e)。因此，此算法計算量比較小，準確產(chǎn)生出了解密密鑰d。

最后，將之前產(chǎn)生的p，q及ψ(n)銷毀，至此完成了密鑰生成的整個過程。

3 實驗結果

在快速RSA密鑰生成組合算法中，主要是通過提高大素數(shù)尋找速度，快速生成解密密鑰d，來提高密鑰的生成速度。在進行素數(shù)尋找時，先通過預篩選算法篩選可能的素數(shù)，其中應用了迭代來減少計算量，這樣整體上減少了冪乘算法的調(diào)用，提高了速度;之后通過改進算法，來提高產(chǎn)生速度，主要是通過減少模冪算法中的模乘操作以及優(yōu)化模乘操作來優(yōu)化算法質量，采用模乘操作代替求模冪算法中的乘法操作，同時使用改進的滑動窗口算法結合Montgomery模乘和模平方算法將傳統(tǒng)方法中的單一循環(huán)分配成多個循環(huán)同時進行循環(huán)計算，大大提高了計算效率。在生成解密密鑰d時，將加密密鑰e分解為n個獨立子加密密鑰項，利用并行計算，減少了運算次數(shù)，從而提高生成速度。

為了驗證本文算法的準確性，本文采用傳統(tǒng)的Miller－Rabin算法和本文算法作對比。將2種方法的整體計算量統(tǒng)計并進行對比，表1給出了2種方法的計算量比較結果。

表1 2種方法中冪乘算法比較表Tab.1 Twomethods by algorithm in comparison

由表1可知，改進的RSA生成算法的模乘次數(shù)和模平方運算量遠遠小于傳統(tǒng)方法的計算量，說明改進方法克服了傳統(tǒng)方法計算量過大的缺點。

分別用2種密鑰生成方法，在10 s內(nèi)生成密鑰，記錄生成密鑰的個數(shù)，并分別對2種方法的生成密鑰合格率進行對比。具體比較結果如表2所示。

表2 生成密鑰個數(shù)及合格率對比Tab.2 Qualified generate the keys number and contrast

由表2可以看出，在相同的10 s的時間內(nèi)，改進的RSA密鑰生成方法產(chǎn)生的密鑰數(shù)量多于傳統(tǒng)方法產(chǎn)生的數(shù)量，且密鑰的合格率也遠高于傳統(tǒng)方法。將2種方法生成的密鑰質量作出如圖2所示的質量波狀圖，由圖2中曲線的走勢比較可知，同樣的耗時，改進RSA算法生成的密鑰保密性能更優(yōu);要達到相同的密鑰保密性能，傳統(tǒng)Miller－Rabin算法需要花費更多的時間。由此可知，改進的RSA密鑰生成算法解決了傳統(tǒng)Miller－Rabin算法由于多次進行單一循環(huán)帶來的密鑰生成耗時長、效率低的缺點，提高了素數(shù)生成效率，最終更快速地得到了性能較優(yōu)的密鑰。

圖2 2種方法密鑰質量對比曲線Fig.2 Twomethods key quality comparison curve

4 結論

本文提出了一種改進的快速RSA密鑰生成算法，通過使用改進的滑動窗口算法結合Montgomery模乘和模平方算法，同時生成多組素數(shù)并利用窗函數(shù)從中選取更有效的素數(shù)，避免了傳統(tǒng)方法中多次計算單一循環(huán)而造成密鑰生成效率不高的缺點。實驗證明，該算法能夠快速尋找出素數(shù)，高效生成密鑰，滿足了現(xiàn)代網(wǎng)絡通信對密鑰的需求，取得了滿意的結果，具有很高的使用價值。

［1］秦曉東，辛運幃，盧桂章.Miller_Rabin算法研究與優(yōu)化實現(xiàn)［J］. 計算機工程，2002，10(4):55－57.

QIN Xiao－dong，XIN Yun－wei，LU Gui－zhang.Miller－Rabin algorithm studied and optimization［J］.Computer realization process，2002，10(4):55－57.

［2］李國金，任曉奎.軟交換技術及其應 用［J］.遼寧工程技術大學學報，2004，23(5):63－65.

LIGuo－jin，REN Xiao－kui.The soft exchange technology and its using［J］.Liaoning Engineering Technology University，2004，23(5):63－65.

［3］何明星，范平志.新一代私鑰加密標準AES進展與評述［J］.計算機應用研究，2005，11(2):23－31.

HEMing－xing，F(xiàn)AN Ping－zhi.A New Generation of Private Key Encryption Standard AES Progress and Evaluated［J］.Computer Application Research，2005，11(2):23－31.

［4］LU Chih－chung，TSENG Shau－yin.Integrated design of AES(Advanced Encryption Standard)encrypter and decrypter［C］//ASAP'02 Proceedings of the IEEE International Conference on Application－Specific Systems，Architectures，and Processors.Washington，DC，USA:IEEE Computer Society，2002:277－285.

［5］林曉鵬，呂迎陽，郭東輝.基于 Internet語音通信的技術問題分析［J］.計算機工程與應用，2002，38(18):159－162.

LIN Xiao－peng，LV Ying－yang，GUO Dong－h(huán)ui.Based on Internet voice communications technology problem analysis［J］.Computer Engineering and Applications，2002，38(18):159－162.

［6］譚永銓，戴逸民.資源共享的并行AES加密解密算法及其實現(xiàn)［J］.計算機仿真，2008，25(9):134－138.

TAN Yong－quan，DAI Yi－min.Implementation of Resource Sharing and Paralleling Algorithm for AESEncryption/Decryption［J］.Journal of Computer Simulation，2008，25(9):134－138.

［7］JOAN D，VINCENTR.AESProposal:Rijindael［EB/OL］.(1999－03－09)［2010－01－21］.http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=50321435766DA7D74EA132 12E767F3D5?doi=10.1.1.36.640＆rep=rep1＆type=pdf.

［8］周玉潔，馮登國.公開密鑰密碼算法及其快速實現(xiàn)［M］.北京:國防工業(yè)出版，2005:116－153.

ZHOU Yu－jie，F(xiàn)ENG Deng－guo.Implements and Its Rapid Public－Key Cipher Algorithm ［M］.Beijing:National Defense Industry Press，2005:116－153.

(編輯:魏琴芳)