The High-Speed RSA Implementation

In 1976 year,Diffie and Hellman gave the public-key encryption system and in 1977 3'ear,Rivest,Shamir and Adleman give the first public-key cryptosystem the RSA public-key encryption.From then,people give a large of public-key cryptosystem. Public-key cryptosystem is widely used to provide both secrecy and digital signature.But public-key cryptosystem is based on number-theoretic computational problems,so compute them is slow,which restrict theirs use.So the public-key cryptosystem efficient implementation is a hot topic.The exponentiation in Z_m need much of time in RSA implementation.Modular exponentiation is the key problem in RSA implementation.In this paper,we will discuss the operations of modular exponentiation for multiple-precision integers.To compute exponentiation g~e is to do a serial of multiplication and square.There are two ways to reduce the time required to do exponentiation.One way is to decrease the time to multiply two elements int the group;the other is to reduce the number of multiplications used to compute g~e.So in this paper we will discuss the two ways.For the second way,we mostly analyze the sliding window exponentiation techniques,and we will introduce a useful way for finding the optimization window.For the first way,we analyze the Montgomery multiplication and its improving method.Through the analysis of Montgomery multiplication and exponentiation,we propose the the Montgomery square.Afer analysis and experimental we found the time required to do Montgomery square is about 74.6%of the time required to do Montgomery multiplication.In the sliding window exponentiation,the time required to do exponentiation using Montgomery square and multiplication is about 78.9%compare to only using Montgomery multiplication.In the end we propose a better method for computing the modular exponentiation.