Application And Research Of Fast Algorithm Of Large Number Divide In RSA

As network technologies are widely applied in various fields, communication is becoming more and more convenient. However, in the process of information transmission, security is an inevitable problem which challenges information technology. To response the challenges, cryptographic technology is necessary. In cryptographic technology applications, we should pay attention not only to the security of a cryptographic system but also to its efficiency. In many public key cryptosystems, RSA is most widely applied. Compared with the symmetric encryption algorithms, the computation overhead of RSA algorithm is huge, and this makes the encryption and decryption of RSA very inefficient. Optimizing RSA algorithm is of great significance.Modular operation of great integers is a basic one in RSA public key cryptosystem. To do modular operation, it is necessary to do division in advance, so the division is also a basic operation of the public key cryptosystems. The division efficiency deadly affects the efficiency of the public key cryptosystems. In this dissertation, we discuss the time and space complexity of some widely applied great integer division algorithm, and propose a fast great integer division algorithm, apply the improved large integer division algorithm to the RSA encryption algorithm.The main works are as follows:First, we introduce the background and the state of the art of public key cryptosystems, summarize the theory of RSA public key cryptosystem, and analyze the security of it. And then introduce some basic knowledge of number theory that is applies in some cryptographic algorithms.Second, we analyze the reasons why the RSA encryption algorithm is inefficient and great integer division. At the cost of storage, we improve the Newton iteration and trial method bp preprocessing and finally improve large integer division. We also implement the improved algorithm on computer. Test results show that the number of iteration algorithm is greatly reduced. And the improved division algorithm can reduce the multiplications for dividing, and thus obviously promote the division efficiency.Apply the improved large integer division algorithm to the RSA encryption algorithm. According to the rationale of modular and modular exponentiations,we improve the storage form and data structure of large integers, and the architecture of RSA algorithm. We further implement the improved algorithm by programming. Test results demonstrate that using improved division algorithm, the efficiency of both key generation algorithm and data encryption can be greatly improved. A future development and research toward this problem has also been discussed.