Optimization of Montgomery multiplication algorithm for public key cryptography

Abstract

Information security is the essential need of the today s digital world. Cryptography process is used to provide high information security when a data is transferred between transmitter and receiver. Private key and public key cryptography are the two types of cryptography which are classified based on the key distribution among the sender and receiver. In private key cryptography, sender and receiver will use the same key for encrypting and decrypting the message. Therefore, the key which is used for encryption and decryption should be known only to the corresponding users newlineand also it should be transferred among the users only through the secured communication path. Otherwise the data can be misused by the hackers. To overcome this drawback of key distribution problem, public key cryptography is introduced by Diffie and Hellman in 1976 and it is also the most widely used cryptographic technique. In public key cryptography, two different keys are used for encryption and decryption. So the secured communication channel is not necessary and the possibility of data hacking is less. Various techniques such as RSA, ECC, Digital Signature Algorithm and ElGamal cryptosystems are followed to perform the cryptographic functions and all the techniques require the modular exponentiation function. In previous years, modular exponentiation is done by using the trial division method but it incurs high area and time consumption. Peter L. Montgomery introduced the Montgomery algorithm in 1985 and it replaces the trial division method thereby reduces the area and time consumption. Montgomery multiplication newlinealgorithm is used to obtain the modular exponentiation by using the modular multiplication. Addition is the basic function for performing modular multiplication and hence the adders play a vital role in Montgomery multiplication algorithm. Different adder structures are used and analyzed to choose the suitable adder for performing modular multiplication. newline newline newline