Acceleration of the RSA Processes based on Parallel Decomposition and Chinese Reminder Theorem

ABSTRACT Within current advancement in computer architecture, the trends nowadays involve re-design and re-implement of algorithms to take the advantages of currently available hardware and the applicability of composition. This paper reviews the parallelizing of the RSA Algorithm and adopting the Chinese Remainder Theorem (CRT) to accelerate the decryption process. In addition, this paper proposes variant decompositions to gain extra speed up. The proposed algorithms are implemented using C# programming language. Finally, the practical results demonstrate the many cores' GPU implementation obtained the highest speedup results for both encryption and decryption processes for variant key size and different workload; for the decryption process with CRT, it is noticed that the adopting CRT sequential version gives a speed up gains ~14X. The multi–core gains ~119X speed up; while the many core GPU gains ~433X speed. Thus, CRT gives a significant speed up for the decryption process for all three variant implementations. In addition, in both cases for Multi-cores and Many-cores, the speed up is super due to composition of parallel processing and CRT. Keywords: RSA, GPU, CRT, DLP, TLP