Fast Implementation Of RSA Public Key Cryptosystem

Since 1990, with the rapid development of computer and internet, the network technology has been applied to all the field in people's daily life. In such an environment, how to protect the sensitive information becomes an important problem. A secure and robust information system needs all kinds of information security technology. A lot of central security technology which is widely used in computer network derives from modern cryptography. The research and development of this technology is an important safeguard of the computer technology.The security and performance of RSA public key cryptosystem which is proposal by R. L. Rivest, A. Shamir and L. Adleman in 1977 has been accepted, and it has become the most famous cryptosystem. However, inefficiency is still a problem in the encryption and decryption process. This disadvantage has become a bottleneck problem of RSA. Hence, how to implement RSA algorithm faster is a research content of modem cryptography.In this paper, we mainly study multiple-precision modular exponentiation algorithm in the implementation of RSA algorithm. This algorithm can be transformed as multiplication, modular multiplication and modular exponentiation algorithm. We can use the software Visual C++ to implement them.This paper consists of seven chapters:The first chapter introduces RSA encryption/decryption algorithm, RSA digital signature and its security.The second chapter describes detailed algorithm of RSA's implementation, the arithmetic method of multiple-precision numbers, and how to denote, save, load and compute big integers.The third chapter discusses multiple-precision multiplication algorithm and gives a comparision among school-book algorithm, Karatsuba algorithm and Comba algorithm. After implemention, we get some experiment data.The fourth chapter gives some Montgomery modular multiplication algorithm and their analysis and comparision. We think CIOS algorithm is the best one in computer software implementation, while FIPS algorithm has a wide application in hardware implementation.The fifth chapter describes square-multiplication, Right-to-left binary exponentiation and sliding-window exponentiation.The sixth chapter introduces an "inline assemble" technology in software implementation. That is to say, write some assemble code into C code. This technology can integrate the convenience of C language with the efficiency of assemble language.The seventh chapter gives some method and an example of program optimization.