改进的负载均衡RSA算法

廖彬宇

摘要：随着科技快速发展，人们非常重视信息安全。而RSA密码体制是信息安全领域使用非常广泛的算法。由于RSA算法的安全性是依靠大整数幂乘，所以在安全性和效率之间存在着一定的问题。为了提高算法的效率，该文提出了一种对负载均衡RSA算法的改进方法。与负载均衡RSA算法相比，改进的负载均衡RSA算法在计算速度上有着一定程度的提升。

关键词：RSA算法；效率；安全；负载均衡RSA算法；提升

中图分类号：TP309 文献标识码：A 文章编号：1009-3044（2018）25-0025-02

The Improved Load-balancing RSA Algorithm

LIAO Bin-yu

（College of Computer ， China West Normal University ， Nanchong 637009 ， China）

Abstract：With the rapid development of science and technology， people attach great importance to information security. The RSA cryptosystem is a very widely used algorithm in the field of information security. Because the security of the RSA algorithm relies on large integer power， there is a certain problem between security and efficiency. In order to improve the efficiency of the algorithm， this paper proposes an improved method for load-balancing RSA algorithm. Compared with the load-balancing RSA algorithm， the improved load-balancing RSA algorithm has a certain degree of improvement in calculation speed.

Key words： RSA algorithm； efficiency； security： load-balancing RSA algorithm：improvement

随着科技的发展，社会的进步，在网络中产生了异常庞大的数据量，而信息的安全性则变得越来越重要，因此对信息进行保密的密码正在飞速发展。由美国 MIT 的 Rivest、Shamir 和Adleman 在 1978 年提出来的RSA加密解密算法[2]是使用最广泛的密码之一，该密码是属于非对称密码体制，公钥是公开的，私钥是保密的，且两个密钥不一致。RSA算法[4]的安全性是由大整数因子分解的困难程度来保障的，整数越大，分解难度越大，也越能保障安全性，但是提升安全性的同时却降低了计算的速度，针对这一问题，负载均衡RSA算法能够有效提升计算速度，而本文提出了一种对负载均衡RSA算法的改进方法来进一步提升效率。

1 RSA算法描述

算法具体运算过程如下[5]：

1.1 密钥的产生

①选择两个随机大素数p和q；

②然后计算 n = p × q，Φ （ n） = （ p - 1） （ q - 1） ；

③接着随机选择一个整数 e，满足 gcd（ e，Φ（ n） ） = 1；

④其次利用欧几里得扩展算法来计算e关于模n的乘法逆元d，即 ed≡1 mod （Φ （ n）） ；

⑤最后公开 n、e 作为加密密钥，保密 p、q、d、Φ （ n） ，将 n、d 作为解密密钥。

1.2 加密算法

对明文M进行加密，利用公钥（n，e）进行计算得到密文 C= Me mod n。

1.3 解密算法

经过加密算法得到了密文C，然后利用解密密钥（n，d）计算得到明文 M = Cd mod n。

2 负载均衡RSA算法

为了改进大整数幂乘，在文献[9]中提出了一种负载均衡算法，以加密过程来说明负载均衡算法的操作过程：

（1）假设明文M可以分解为多个小整数相乘的形式，形式为 M=M1×M2×…×Mn，那么加密过程C=Me（mod n）就变为C=（M1×M2×…×Mn）e（mod n），进一步变形为C=M1eM2e… Mne（mod n）。

（2）經过变换之后，明文M被分解为多个部分，这样就可以把每个部分均衡地分配到计算进程中，然后每个进程独立完成运算。

（3）假设明文分解为12个子明文（M1，…，M12），现有3个进程（K1，K2，K3），每个进程平均分配4个任务。那么进程 K1 进行 M1，M2，M3 ，M4的幂乘运算，K2 进行 M5，M6，M7，M8 的幂乘运算，K3则进行 M9，M10，M11，M12 的幂乘运算。

（4）由于分解后各个数的大小不一致，所以这样分配存在一个问题，有可能较大的四个整数分配到了同一个进程中，较小的四个整数分配到了同一个进程中。那么就会导致其中一个或几个进程的计算量巨大，而其他的进程计算量较小，这就使任务分配不够均衡。而最终的乘积运算要等到所有任务结束之后才会进行，那么计算量较小的任务就会一直等待计算量较大的任务完成运算，徒增等待时间。

（5）因此对分解后的数进行排序，满足M1≤M2≤M3≤......≤M12，把M1分配给第一号进程，把M2分配给第二号进程，把M3分配给第三号进程，M4分配给第一号进程，M5分配给第二号进程，分配规则为Mi分配给i（mod k）。

（6）所有进程完成计算后，再对各个任务的计算结果进行乘积运算。

3 改进的负载均衡RSA算法

这里对负载均衡RSA算法的分配方法进行改进，开始步骤和上文一致，首先需要把明文M分解为M1，M2，M3.....Mn，然后按照从小到大的顺序排列好，顺序如M1≤M2≤…≤Mn。接着开始分配，把M1分配给第一个进程，M2分配给第二个进程，按照顺序逐个分配。最后在原来分配方法的基础上提出改进，这个分配方法能够提升计算效率。

该算法步骤如下：

（1）把明文M分解成多个小素数的乘积形式，即 M=M1×M2×…×Mn。

（2）然后对各个小整数进行排序，排序满足M1≤M2≤…≤Mn。

（3）排序结束后开始给进程分配任务，分配规则为：假设有n个小素数，有k个进程，令a=n （mod k），然后先放置从M1开始的a个数，剩下的n-a个数刚好可以使k个进程完全分配。接着从第（a+1）个数开始分配给第一个进程，第（a+2）个数分配给第二个进程，逐个分配，直到第n个数分配结束。最后把从M1开始的a个数从第一个进程开始依次往后分配给进程。

（4）每个进程独立完成任务的计算。

（5）必须等到所有进程计算结束之后，才能把各个进程的幂乘结果进行最后的乘积运算得出结果。

4 改进的负载均衡RSA算法性能分析

我们可以通过列举简单的例子来说明两个算法的实用性。假设M分解成10个素数（7，11，19，23，37，43，59，71，83，97），现在有4个进程（k1，k2，k3，k4）。M=7*11*19*23*37*43*59*71*83*97，未改进的负载均衡算法分配如下：

k1（7，37，83），k2（11，43，97），k3（19，59），k4（23，71）。改进的负载均衡算法分配如下：k1（19，59，7），k2（23，71，11），k3（37，83），k4（43，97）。

则未改进的负载均衡算法的任务如下：

k1=（7*37*83）e=21497e ，k2=（11*43*97）e=45881e，

k3=（19*59）e=1121e，k4=（23*71）e=1633e，

所以最大任务为k2=45881e 。

改进的负载均衡算法的任务如下：

k1=（19*59*7）e=7847e，k2=（23*71*11）e=17963e，

k3=（37*83）e=3071e，k4=（43*97）e=4171e。

所以最大任务为k2==17963e。

由于最终的乘积运算要等到所有进程的计算任务结束之后才会进行，所以决定执行时间的关键是最大任务的计算时间。从两个例子可以看出未改进的负载均衡算法最大任务为k2=45881e，改进的负载均衡算法最大任务为k2==17963e。由于改进的负载均衡算法的最大任务相对较小，很明显可以得出改进的负载均衡算法可以提升计算效率。

5 结语

本文分析了RSA负载均衡算法，在此算法基础上，对算法的任务分配进行了改进。通过列举的例子得出该改进算法能在一定程度上提升算法的计算效率，具有一定的实际意义。但是还可以继续提升算法的计算速度，未来还要继续致力于研究提升RSA算法的计算速度。

参考文献：

[1] 黄健.RSA公钥加密体制的安全性分析与改进[J].计算机与网络，2016，42（01）：70-73.

[2] 陈春玲，齐年强，余瀚.RSA算法的研究和改进[J].计算机技术与发展，2016，26（08）：48-51.

[3] 陈鹏飞，何小东.RSA算法的分析与改进[J].电子世界，2015（13）：111-113.

[4] 王树天.RSA算法的改进和实现[J].内蒙古科技与经济，2015（16）：93-94.

[5] 贾美娟，孔靓，李梓，等.RSA算法研究及其计算技巧分析[J].大庆师范学院学报，2012，32（6） ： 14-16.

[6] 赵悦.基于RSA加密解密的即時通讯系统的设计与实现[D].吉林大学，2016.

[7] 孙伟.公钥RSA加密算法的改进与实现[D].安徽大学，2014.

[8] 程晓荣，马力，何壮壮.公钥RSA加密算法的分析与改进[J].网络安全技术与应用，2015（08）：44-45.

[9] 唐笑林.高效RSA算法的研究与并行实现[J].计算机工程，2013，39（02）：164-167+171.

[10] Mahaveerakannan R， Dhas C S G. Customized RSA public key cryptosystem using digital signature of secure data transfer natural 22 number algorithm[J]. International Journal of Computer Technology & Applications， 2016， 9（5）： 2627-2632.

【通联编辑：代影】