RSA加密算法中MPI的应用

陆玉阳

摘要：RSA加密算法在进行复杂判断和大数运算时，计算时间往往花费较多，对计算机的运行速度、存储容量等方面具有较高的要求。MPI能够提供较快的数值计算和数据处理能力，提供高性能并行计算。该文通过在RSA加密算法中MPI的应用，通过实践证明MPI并行计算可以改进RSA算法，提高加密速度、减少容量需求等。

关键词：RSA；MPI；加密；并行计算

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）28-0040-03

Application of MPI in RSA encryption algorithm

LU Yu-yang

（Xuzhou College of Industrial Technology， Xuzhou 221140， China）

Abstract： RSA encryption algorithm in the complex judgment and operation of large Nbers， calculating the time tend to spend more， the computer run faster， have higher requirements in terms of storage capacity. MPI provides fast Nerical calculation and data processing capability， providing high performance parallel computing. Based on RSA encryption algorithm in application of MPI， MPI parallel computing can improve the RSA algorithm proved by practice， increase speed， reduce capacity requirements， and so on.

Key words： RSA；MPI； encryption； parallel computing

公钥密码算法包括RSA算法、Diffie-Hellman算法、ElGamal算法、背包算法以及椭圆曲线密码算法等，RSA加密算法作为公开密钥密码体现中的一个典型，其应用最为广泛，RSA加密算法既可加密，也可用于数字签名。RSA加密算法在进行复杂判断和大数运算时，计算时间往往花费较多，对计算机的运行速度、存储容量等方面具有较高的要求，针对RSA加密算法的运行速度而且尽可能少耗费资源一直是密码学领域研究的热点问题。

MPI（消息传递接口Message Passing Interface），MPI是一个库，而不是一门语言，具有巨大的数值计算和数据处理能力，提供高性能并行计算，即通过把一个大的计算问题分解成许多彼此独立且有相关的子问题，然后把他们散列到各个节点机上并行执行从而最终解决问题的一种方法。并行计算的提示有效地改进了RSA加密算法的缺点。本文以RSA加密算法为出发点，通过MPI的应用，通过实验有效地证明了在RSA加密算法中MPI能够提升加密速度、降低容量需求，提高数据的安全性。

1 RSA加密算法

RSA（RonaldRivist、AdiShamir和LenAdlemar三人的名字共同命名）是一种应用较为广泛的公钥算法，也是他们开发出的第一个公钥密码体制，并在未来的20多年时间内得到了充分肯定。RSA是以分组的方式对明文进行加密，RSA密钥产生过程如下：

①它随机地选择两个大质数p和q（需保密）；

②p*q=n；

③在任找一个数m，要求满足m

④计算得到d=m-1mod[（p-1）*（q-1）]；这里d是私密指数，m代表公开指数；

⑤获得公匙（n，m），私匙（n，d）；

⑥删除p和q；

加密算法实现原理就是将明文数据分解成比n小的数据块用公开指数作乘方取模运算：c=me mod n（其中m代表明文块，c代表密文块）；解密过程恰恰相反：即把密文数据块依托私密指数进行乘方取模运算：m=cd mod n。网络攻击者有公匙：e和n，为了获得私匙d，则会对n行因数分解来获得p、q，最终算出d是最好的RSA攻击方法。若采用推断（p-1）（q-1）或直接穷举d则会慢很多。因此实现RSA加密算法的运行速度而且尽可能少耗费资源一直是待解决的问题。

2 并行计算环境MPI

MPI（Message Passing Interface）是一个消息传递编程标准，它是一个全球性质的参考标准。MPI的制定整合了几乎所有消息传递系统的优点，并在相关方面做了较大的改进和发展，最终获得一个为并行程序的开发使用的平台。MPI系统是一个由所有具有标准接口说明的消息传递函数所构成的函数库，MPI标准中定义了一组函数接口用于进程间的消息传递，通信的性能对基于消息传递的应用来说至关重要，若不全力实现MPI，造成通信开销会十分昂贵，程序并行将豪无放逐意义。MPI标准的制定仅解决了并行程序的可移性问题，而最为关键的问题是在为MPI实现的高效与否。

针对网络中已经确定带宽上限和延迟下限，不同的协议和API向用户提供的功能和性能不同。根据API、协议，可将带宽、延迟空间划分为以下五类：

高延迟/窄带宽（存在较多拷贝和缓冲的标准TCP/IP协议栈）

高延迟/中等带宽（改进的TCP/IP协议栈）

中等延迟/中等带宽（建立在相对较慢的驱动之上，采用无拷贝TCP/IP协议栈的MPI实现，如MPICH）

④ 低延迟/宽带宽（有硬件支持的优化了的MPI实现）

⑤ 超低延迟/窄带宽（主动消息，远程put/get）

在TCP/IP协议之上无法建立高速的MPI，为了实现MPI的高效，put/get协议往往会被人们所选择。

3 RSA加密算法中MPI的应用

由于RSA加密算法在实现时有一定的困难，结合并行计算环境MPI在并行处理方面的优点，提出对RSA加密算法进行改进，采用基于MPI的消息传递系统，实现算法运行的速度以及其安全性的提高。具体改进后的RSA算法实现如下：

RSA算法在实现过程中后继操作基本上都依赖于前一步的运算结果，因此在实现数据交换和通信过程中如果全部采用并行计算，往往导致系统开销消耗增大，实现起来相对较难，最终影响系统效率。鉴于以上问题在实现过程中建议采用更加实际的局部并行处理方法。即主要对随机产生质数过程、计算逆元的过程、欧拉函数的计算以及加密时的大数取模过程采用并行处理。RSA加密中有两个关键问题：

1）选定互质P和Q

判定素数，一般定义是：素数是除了能被1和它本身整除而不能被其他任何数整除的数。用2到n-1这些数去除n，如果所有数除不尽，即判定n是素数，否则只要其中有一个数能整除，即判定n不是素数。该办法适用范围较小，对于判定大素数来说，则结果不可取，故对于大数（超过百位以上的整数）p和整数q（q

2）计算逆元

逆元算法：如果ab≡1（modm）， 则称b是a的模m逆，记作a的模m逆是方程ax≡1（modm）的解，两个数互质一定有逆元。求逆元可以使用辗转相除法，但是只有两个数都是质数的时候才有逆元。逆元计算相对困难，本文计算逆元以欧几里得算法为例。

#include

voidmain（）

{ Int temp；int a，b；

scanf（"%d"，&a）；

scanf（"%d"，&b）；

printf（"the greatest common factor of%dand%dis"，a，b）；

while（b！=0）

{

temp=b；b=a%b；a=temp；

}

printf（"%d＼n"，a）；

getchar（）；

getchar（）；

}

分析发现，有4个调用单元在系统中被确定，通过单元模块的有效组合来实现系统。建立系统时，为了让消息传递及计算简便，每一位数据存放都采用数组，每个整型数组的一位都存放一个需要计算的数的每一位。以系统模块中2个随机大素数的乘积为例：

在实现大数相乘时，通过MPI消息传递的方式将乘数和被乘数发送给每1个进程上，接着设置1个步长，用于每台机器在并行计算时计算相应位。以ABCD×EFGH为例。

第一阶段：初始化

经过消息发送，使得每个进程中都存放了乘数和被乘数：ABCD及EFGH。

第二阶段：计算

设定MPI步长，步长等于乘数的位数/开设的进程数所得的商。本例为4除以2得2，即步长为2.具体计算过程是：用第1个进程与2求模余1的位数上的数，第2个进程计算与2求模余0的位数上的数，单个进程单独计算后得到各自的结果。

第三阶段：汇总

通过MPI消息将单个进程的结果发送至1号进程完成汇总，接着进行进位的调整，得到最终结果。

以下为MPI主要代码：

MPI_Init（&argc，&argv）； /*MPI初始化*/

MPI_Comm_rank（MPI_COMM_WORLD，&rank）； /* 获得标识*/

MPI_Comm_size（MPI_COMM_WORLD，&size）； /*MPI系统大小*/

If（rank==0）） /* 假设是0进程*/

……

MPI_Barrier（MPI_COMM_WORLD）；

T1=realtime（）；

MPI_Bcast（FirstArray，N*N，MPI_INT，0，MPI_COMM_WORLD）；

MPI_Bcast（SecondArray，N*N，MPI_INT，0，

MPI_COMM_WORLD）；

……

for（j=0；j

for（k=0；k

{

Int myresult，result；

Result=ResultArray[j][k]；

MPI_Reduce（&myresult， &result，1，MPI_INT，MPI_SUM，0，MPI_COMM_WORLD）；

/*反馈计算结果到1号进程*/

ResultArray[j][k]=result；

}

其他几个功能函数的设计思想与上述类似，就是充分利用MPI在多台机器或多个进程中的消息传递机制，将本来需要在1台机器上或1个进程上完成的作业，分发到多台机器或多个进程中，提高整体加密速度。如图1所示 算法流程图。

4 结论

在现实的工作中，往往需要处理较多的保密数据，在网络上进行传输时必须充分考虑其安全性。MPI在为运行并行程序和用户构造时提供了便利的程序开发平台，特别是其采用的消息传递机制，适应于各种同构或异构网络平台。通过在RSA加密算法中MPI的应用，不仅达到了高效、准确、安全的数据传输、数据加密等要求，而且对于MPI的数据传送的快速、资源利用率的提高等优点也充分得到体现。

参考文献：

[1] 都志辉.高性能计算并行编程技术_MPI并行程序设计[M].北京：清华大学出版社，2001.

[2] 韩健，张乐，蔡瑞英.计算环境MPI在RSA加密中的应用[J]. 南京工业大学学报，2003，3：49-51，61.

[3] 黄光明.基于DES_RSA加密算法的改进与实现[D].东北师范大学，2013.

[4] 吴明航.DES和RSA混合加密算法的研究[D].哈尔滨工业大学，2013.

[5] 高雪寒.大数相除快速算法在RSA中的应用与研究[D].陕西师范大学，2014.

[6] 贺令亚.RSA加密算法的研究与实现[D].中南大学，2009.

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