一种改进的快速RSA 密钥生成算法

陈 燕

(贵阳学院计算机科学系，贵州贵阳 550002)

0 引言

21 世纪，全世界的计算机都将通过Internet联到一起，网络安全成为至关重要的问题。为了保证计算机信息传递的安全性，需要生成密钥将信息安全传送，因此，密钥生成技术是网络安全中的关键技术，也是难点技术［1］。随着网络的普及，人们相互间的通信量日益增多，使得密钥的需求量大大增加，这就使得对密钥生成的效率要求更高了。因此，如何快速生成高质量的密钥，保证人们使用网络的安全需要，成为人们关注的热点问题。

密钥生成技术中，关键问题就是高质量的素数生成问题。传统的密钥算法在生成密钥的寻找大素数过程中，为了得到准确性较高的素数，需要不断进行单一幂乘运算循环，循环次数越高，素数的准确性越高［2－4］。这样多次循环的结果是得到了准确性高的素数，生成了高质量的密钥，但是，在生成大素数时，需要依序进行多次循环运算，本次循环需用上一次循环的生成结果计算出更精准的素数，这样不仅幂运算的计算量很大，而且只能依序进行单一循环使得素数生成耗时过长，多次循环直接导致生成密钥的耗时长、效率不高，无法满足计算机网络迅速发展对密钥生成量的需要。寻找素数是密钥生成的关键步骤，素数能否快速准确查找，直接关系到密钥生成的速率和质量，因此，如何改进传统密钥生成方法中，对素数寻找的低效耗时长问题，成为密钥生成问题的一个难点。

针对传统的算法素数寻找耗时长，密钥生成效率不高的缺点，本文提出一种改进的快速RSA密钥生成算法。通过使用改进的滑动窗口算法结合Montgomery模乘和模平方算法，同时生成多组素数并利用窗函数从中选取更有效的素数，避免了传统方法中多次计算单一循环而造成密钥生成效率不高的缺点。实验证明，这种改进算法能够快速寻找出素数，高效生成密钥，满足了现代网络通信对密钥的需求，取得了满意的结果。

1 密钥生成原理

密钥是在信息传递中明文转换为密文或将密文转换为明文的算法中输入的数据，是传递安全信息的重要保障。密钥生成主要分为如下几个步骤。

1 )采用大素数筛选算法，产生出一个公开的大素数p。通过构造一个小的素数集合Su(k)={pi|pi≤k，k∈N}，其中，k是正整数;pi是第i个小的素数，采用试除法，如文献［5］中所述，对生成的奇数d进行筛选，如果不能通过筛选，则对该奇数d进行递增2的操作，通过筛选后进入素性测试，即可得到公开大素数p。

2 )循环运算产生保密的大素数q，令n－1=2km，其中，m和n均为正奇数，n为待测的正奇数且n＞1。选择一个随机整数a满足1＜a＜n－1，计算 b0≡ am(mod n)［6］。

5 )销毁p，q及φ(n)。至此完成了密钥的生成。

由上述步骤可知，传统算法需在第2)步生成保密大素数时，依次进行单一循环，每次循环必须用上一循环中产生的结果bi继续进行计算，直至产生符合要求的素数即结束循环。由此可知，这种产生保密素数的方法不仅需要进行多次单独循环，而且在每次循环计算中都要进行大量的幂乘运算，即实现bi≡(mod n)中的大量幂乘运算［8］，这样使得寻找大素数时计算量过大，耗时长，直接导致了密钥生成效率低的问题。

针对传统算法的缺点，我们设想如果将单一循环分配给多个循环同时进行计算，并优化幂乘算法，将能有效提高密钥生成的效率。因此，本文提出一种改进的快速RSA密钥生成算法。通过使用改进的滑动窗口算法结合Montgomery模乘和模平方算法，同时进行多个循环生成多组素数并利用窗函数从中选取更有效的素数，这样就能避免多次计算单一循环耗时长、计算量大而造成密钥生成效率不高的缺点。

2 改进的快速RSA密钥生成算法

根据密钥生成算法的原理，对传统方法进行改进，利用窗函数和模乘优化算法，得到快速RSA密钥生成算法的方法，下面详细叙述快速RSA密钥生成算法的具体步骤。

2.1 公开大素数

寻找大素数的通常方法是:随机生成一个奇数，然后用概率素性测试算法对该奇数进行素性测试，反复此步骤直至寻找到为止。

素数预筛选算法如下

1 )计算机随机产生n位奇整数d，令i=0，随机产生的n位整数为

5 )按照公式q=q+2，i=i+1计算出其值，然后将循环流程转向步骤2)继续进行循环，直至满足条件循环即结束。

经过上述多步运算，到循环结束后就完成了大素数的筛选，最终生成公开大素数p。

2.2 保密大素数

在进行模幂运算时，先求幂然后求模，将会出现一个巨大的中间结果，会使实际运算操作变得非常复杂，在此采用模乘操作代替求模幂算法中的乘法操作，保证中间结果的长度不大于模的长度。同时使用改进的滑动窗口算法结合Montgomery模乘和模平方算法来优化模幂算法。

优化的模幂算法描述如下。

其中，MontMul()和 MontSqu()分别是 Montgomery算法中的模乘函数及模平方函数。在传统的模乘算法中，通常使用大整数乘法和除法求模乘，这种方法包含除法操作，所以比较耗时且速度较慢，如果将Montgomery求模算法及大整数乘法算法组合使用，则在2n(n+1)步单精度乘法内即可完成模乘算法。组合改进的滑动窗口算法和Montgomery算法，便可得到较优的模幂算法

在生成保密大素数时，将传统方法中的单一循环进行改进，分配成多个循环同时进行运算，利用上文给出的幂乘优化算法，在每个循环中进行幂乘运算产生出多组大素数，接着将产生的多组大素数输入窗函数中进行筛选，满足素数即为满足条件的保密大素数，最终将产生的保密大素数输出。具体的保密大素数生成流程图如图1所示。

图1 保密大素数生成流程图Fig.1 Confidential big primes generating flow chart

通过将单一循环分配为多个同时运行的循环，并优化循环中的幂乘运算，这样就解决了传统算法中多次进行单一循环和大量幂乘运算带来的耗时长、效率低的问题，快速产生出了高质量的保密大素数q。

2.3 密钥生成算法

利用上节中计算产生的公开大素数和保密大素数生成密钥，密钥生成分为3个部分:初始密钥的生成、中间密钥的生成和子密钥生成。

1 )初始密钥的生成。根据公开大素数p计算出密钥位数为256位，然后根据保密大素数生成密钥，若密钥的位数小于256位，则需在最后的有效位后面加一个字符“1”，然后再用字符“0”将密钥补全为256位。将扩充后得到的256位密钥等分成8等分ω－8，ω－7，…，ω－1，…。

2 )中间密钥的生成。利用(5)式将上一步骤中的8等分密钥扩展到132个32位的中间密钥ω0，ω1，…，ω131。

3 )子密钥的生成。通过第2)步中产生的132个中间密钥后，利用8个四位输入输出的S盒生成33个子密钥，分别记为S0，S1，…，S7。具体生成过程为

对于想得到密钥保护信息的外来入侵者来说，他只能得到一轮密钥，要想向前计算找出信息，不但需要对初始密钥、中间密钥进行猜测，而目还需要对后一轮的子密钥进行多次猜测。

改进的密钥生成算法采用中间密钥，先经过密钥生成算法步骤扩充初始密钥，再经过多次运算得到132个中间密钥，最后将中间密钥经过S盒变换后得到子密钥。可以看出中间密钥的生成是根据多项式x8+x7+x5+x3+1生成的，每一个中间密钥的生成全都依靠该多项式，即每个中间密钥的生成，不再只是依赖于单独一轮循环计算，而是依赖于在此中间密钥之前的两轮循环，这样即使攻击者通过某种方法窃取得到某一轮循环的密钥，但是由于没有前一轮循环的密钥，因而也无法继续向后计算推导，从而保证了向后推导的不可能性，保证了数据信息的安全。

2.4 解密密钥生成

基于上两节的内容，计算n=pq(公开)以及欧拉函数Ψ(n)=(p－1)(q－1)，随机选取整数e作为加密密钥，加密密钥必须满足gcd(e，ψ(n))=1(公开)。存在一正整数k，使得de－kφ(n)=1，根据Derome方法，解密密钥d可以由(6)式求出。

所以，ψ(ei)远远小于ψ(e)。因此，此算法计算量比较小，准确产生出了解密密钥d。

最后，将之前产生的p，q及ψ(n)销毁，至此完成了密钥生成的整个过程。

3 实验结果

在快速RSA密钥生成组合算法中，主要是通过提高大素数寻找速度，快速生成解密密钥d，来提高密钥的生成速度。在进行素数寻找时，先通过预筛选算法筛选可能的素数，其中应用了迭代来减少计算量，这样整体上减少了幂乘算法的调用，提高了速度;之后通过改进算法，来提高产生速度，主要是通过减少模幂算法中的模乘操作以及优化模乘操作来优化算法质量，采用模乘操作代替求模幂算法中的乘法操作，同时使用改进的滑动窗口算法结合Montgomery模乘和模平方算法将传统方法中的单一循环分配成多个循环同时进行循环计算，大大提高了计算效率。在生成解密密钥d时，将加密密钥e分解为n个独立子加密密钥项，利用并行计算，减少了运算次数，从而提高生成速度。

为了验证本文算法的准确性，本文采用传统的Miller－Rabin算法和本文算法作对比。将2种方法的整体计算量统计并进行对比，表1给出了2种方法的计算量比较结果。

表1 2种方法中幂乘算法比较表Tab.1 Twomethods by algorithm in comparison

由表1可知，改进的RSA生成算法的模乘次数和模平方运算量远远小于传统方法的计算量，说明改进方法克服了传统方法计算量过大的缺点。

分别用2种密钥生成方法，在10 s内生成密钥，记录生成密钥的个数，并分别对2种方法的生成密钥合格率进行对比。具体比较结果如表2所示。

表2 生成密钥个数及合格率对比Tab.2 Qualified generate the keys number and contrast

由表2可以看出，在相同的10 s的时间内，改进的RSA密钥生成方法产生的密钥数量多于传统方法产生的数量，且密钥的合格率也远高于传统方法。将2种方法生成的密钥质量作出如图2所示的质量波状图，由图2中曲线的走势比较可知，同样的耗时，改进RSA算法生成的密钥保密性能更优;要达到相同的密钥保密性能，传统Miller－Rabin算法需要花费更多的时间。由此可知，改进的RSA密钥生成算法解决了传统Miller－Rabin算法由于多次进行单一循环带来的密钥生成耗时长、效率低的缺点，提高了素数生成效率，最终更快速地得到了性能较优的密钥。

图2 2种方法密钥质量对比曲线Fig.2 Twomethods key quality comparison curve

4 结论

本文提出了一种改进的快速RSA密钥生成算法，通过使用改进的滑动窗口算法结合Montgomery模乘和模平方算法，同时生成多组素数并利用窗函数从中选取更有效的素数，避免了传统方法中多次计算单一循环而造成密钥生成效率不高的缺点。实验证明，该算法能够快速寻找出素数，高效生成密钥，满足了现代网络通信对密钥的需求，取得了满意的结果，具有很高的使用价值。

［1］秦晓东，辛运帏，卢桂章.Miller_Rabin算法研究与优化实现［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，FAN 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－hui.Based on Internet voice communications technology problem analysis［J］.Computer Engineering and Applications，2002，38(18):159－162.

［6］谭永铨，戴逸民.资源共享的并行AES加密解密算法及其实现［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］周玉洁，冯登国.公开密钥密码算法及其快速实现［M］.北京:国防工业出版，2005:116－153.

ZHOU Yu－jie，FENG Deng－guo.Implements and Its Rapid Public－Key Cipher Algorithm ［M］.Beijing:National Defense Industry Press，2005:116－153.

(编辑:魏琴芳)