Improvement in Performance of RSA Cryptosystem

Abstract

Cryptography is used to communicate the critical information over an insecure network. Symmetric key cryptographic algorithms are used to encrypt the information so that the intruder cannot get the information of the original message. These algorithms are fast due to small (secret) key size, say 128 bits. As the secret key between the sender and receiver is communicated over insecure channel, one cannot use symmetric key algorithms for complete communication. Shared key can be compromised over insecure network. Public key cryptographic algorithms are needed at least to communicate the shared key used by the symmetric key algorithms. In public key algorithms, key used is very large to secure the message to be communicated. The large sized key comes at its own cost. The key size a ects the computational performance of the cryptosystem. Also, due to the large key size, it creates storage problem. In resource constrained devices, large key size in public key algorithms becomes bottleneck for the performance. RSA is the most popular and widely studied public key algorithm. As with the other public key algorithms, it also requires very large key size. This drawback of RSA prompts one to shift from this public key cryptosystem to other having smaller key size for resource constrained devices. Also, the use of other public key cryptosystems with smaller key size comes with their own shortcomings. Hence there is a need to improve RSA cryptosystem so that it results in better e ciency when used in resource constrained devices. This thesis proposes methods to improve the computational e ciency and memory consumption for di erent RSA variants. Thesis includes the study of di erent existing RSA variants. The variants are studied in terms of their encryption and decryption e ciency. Some of the variants work on encryption performance and some on decryption performance. Based on the computational e ciency, comparative analysis of these variants is carried out to better understand the performance of RSA variants. Memory consumption of di erent variants is also studied One of the variant, Rebalanced RSA CRT Scheme (RRCS), can be used in any scenario where the user requires selection among the gain in encryption or decryption performance. In this thesis, work is done to improve the decryption speed of RRCS by using multiple primes. While maintaining the same encryption speed, the decryption speed of RRCS increases by a factor of 1.8. Implementation of the scheme is shown to re ect the performance gain. Dual RSA (another variant of RSA cryptosystem) is studied and analyzed for further improvement. Three schemes of Dual RSA are improved to design three new schemes; i.e. RC RSA-I, RC RSA-II and RC RSA-III. In RC RSA-I, multiple primes are used in Dual RSA Small-e to improve the decryption performance. In RC RSA-I the computational performance as well as memory consumption improves as compared to Dual RSA Small-e. In RC RSA-II, slow computations involved in Dual RSA Small-d are performed o ine when the computing device is relatively free; this improves the on-line encryption performance. In RC RSAIII, the use of multiple primes in Dual Generalized Rebalanced RSA improves the decryption performance. These three schemes are implemented and compared to refect the better results.