A promising parallel algorithm to manage the RSA decryption complexity

Abstract

In the field of cryptography, public key algorithms are widely known to be slower than symmetric key alternatives for the reason of their basis in modular arithmetic. The modular arithmetic in RSA (short for Ron Rivest, Adi Shamir, and Leonard Adleman) and Diffie Hellman schemes is computationally heavy when compared to symmetric algorithms relying on simple operations like shifting of bits and XOR. Therefore, it has become a serious concern to implement public key algorithms in a faster way. In this work, we explore the impact of compute unified device architecture (CUDA) and Pthread on decryption in RSA when large numbers are created by homomorphic encryption. RSA decryption is based on a power and module operations and produces a very large ciphertext. We introduce a parallel algorithm that splits RSA power operations into different threads and makes use of the large number of processing cores available in graphics processing unit (GPU) cards to reduce the time required in RSA decryption. Experimental results indicate that the proposed CUDA-accelerated multithreaded implementation has potential to effectively deal with the RSA decryption complexity.