Efficient RSA cryptosystem decryption based on Chinese remainder theorem and strong prime

Abstract

Number theory has turned out to be one of the useful when it comes to computer security. For instance, number theory helps to protect sensitive data such as credit card numbers when you shop online, when online transactions is performed. The prime application of it is in the RSA cryptosystem. Rivest Shamir Adleman (RSA) algorithm is known to be a slower algorithm. The modular arithmetic in RSA is computationally expensive. In view of this, it has become a major challenge to implement RSA decryption in a faster way. In this paper, we proposed an efficient method to implement RSA decryption based on Chinese Remainder Theorem and Strong prime. Three different operations, primitive traditional method, Chinese Remainder Theorem method and Chinese Remainder Theorem and strong prime criterion were used for comparisons. Our proposal achieves about 60% computational cost reduction of traditional method using Chinese Remainder method. More interesting, if the method based on Chinese Remainder Theorem and strong prime is implemented, about 84% computational cost can be reduced. Also, comparing to the Chinese Remainder method, the method based on Chinese Remainder Theorem and strong prime of RSA criterion takes about 37% of computational cost, almost 3.2 times faster than the Chinese Remainder Theorem based method. Theoretically, it was observed that our scheme is faster and it is also cheaper.