A novel accelerated implementation of RSA using parallel processing

Abstract

Past research has evidently proved that public key cryptosystems are usually slower than symmetric key cryptosystems due to the reason that they use one additional cryptographic key and different methods for encryption and decryption. RSA is one of the most common asymmetric key cryptography algorithms. Recent research has focused on speeding up RSA using various techniques. With the introduction of distributed computing, parallelization of algorithms enables them to run on multiple cores concurrently at a time. RSA consists of two resource intensive operations namely Modular Exponentiation of up to 1024-bit exponents and repeated calculation of Greatest common divisor. Thus, RSA lays the perfect base for application of Montgomery Reduction algorithm to optimize the Repeated Modular multiplication in exponentiation. In this paper we proposed a parallel scheme for RSA using a new parallel data structure known as Concurrent Indexed List of character blocks. The aim of our research was to improve the speed of RSA encryption and decryption using parallelism and also make it compatible with leading industry cryptography standards. We have simulated four different approaches namely both parallel and sequential with and without Montgomery. We have also integrated our parallel paradigm with renowned C++ Crypto library and achieved a speed-up of upto four times than sequential approach. Unlike any other previous approaches, our implementation got easily integrated with any external library and thus can be adopted by any other algorithmic scheme.

Keywords:

• RSA
• Parallel Algorithms
• Montgomery Reduction
• Hyperthreading