基于MPI的RSA改进算法研究

发布时间：2019-01-01 17:27

【摘要】：信息安全问题越来越引发整个社会的广泛关注,带来了信息安全技术的飞速发展。根据各种信息技术和相关应用的需求,人们提出了许多加密算法,而非对称加密体制的出现标志着加密体制的逐步完善。RSA算法是非对称加密算法的代表性算法,曾被认为是公钥密码体制研究的一个标准模板。模幂运算是RSA公钥密码算法中最基本也是最耗时的运算。为了保证加密数据的安全性,需要增加RSA的密钥位数,随着密钥位数的增加,加密和解密速度变慢,因此需要对RSA算法进行改进,从而提升速度。通过使用MPI消息传递并行接口可以启用多个节点来共同完成计算,从而缩短计算时间。本文从RSA算法的数论基础开始研究。首先,将明文分解以得到因子。本文基于能被互质的两个整数整除的大整数必然能够被这两个整数的乘积相除的性质,设计了一种快速的大整数分解方法。然后,对分解得到的因子进行分组。由于大整数分组后的并行运算时间取决于运行时间最长的进程,因此可以对分解后得到的小整数进行排序,并实现平均分组。最后,对分出的各组进行并行运算,使得大整数幂运算转换为小整数幂运算。对于因子分组过程,本文通过对分解后得到的小整数排序并平均分组,得到更为均衡的多个子任务,利用MPI实现并行运算,从而节省运算时间。实验结果表明,基于MPI的RSA并行改进算法能够有效的提高算法的计算速度。
[Abstract]:The problem of information security has attracted more and more attention of the whole society and brought about the rapid development of information security technology. According to the needs of various information technologies and related applications, many encryption algorithms have been put forward, and the appearance of asymmetric encryption system marks the gradual improvement of encryption system. RSA algorithm is the representative algorithm of asymmetric encryption algorithm. It was once regarded as a standard template for the research of public key cryptosystem. Modular power operation is the most basic and time-consuming operation in RSA public key cryptography. In order to ensure the security of encrypted data, we need to increase the number of key bits of RSA. With the increase of the number of key bits, the speed of encryption and decryption becomes slower, so we need to improve the RSA algorithm to improve the speed. By using the MPI messaging parallel interface, multiple nodes can be enabled to complete the calculation together, thus shortening the computing time. This paper starts with the study of the number theory of RSA algorithm. First, the plaintext is decomposed to obtain the factor. Based on the property that large integers which can be divisible by two integers of mutual prime can be divisible by the product of these two integers, a fast decomposition method of large integers is designed in this paper. Then, the decomposed factors are grouped. Because the parallel operation time after grouping large integers depends on the process with the longest running time, we can sort the small integers after decomposition and realize the average grouping. Finally, the large integer power operation is converted to the small integer power operation. For the process of factorial grouping, by sorting the small integers and grouping them evenly, we can get more balanced subtasks, and use MPI to realize parallel operation, thus saving the time of operation. Experimental results show that the improved RSA parallel algorithm based on MPI can effectively improve the computational speed of the algorithm.
【学位授予单位】：天津工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TN918.4

【相似文献】