In a bid to provide an effective way of providing confidentiality, researchers have invented a new promising form of encryption called homomorphic encryption to improve the security level and running time of RSA public-key cryptosystem. RSA algorithm is known for its security but execution speed is a demerit. This speed is due to the involvement of large bits of numbers in the three stages of its operations (key generation, encryption and decryption processes). In overcoming this obstacle, several approaches have been deployed in the past to enhance the execution speed by improving one or more stages of RSA cryptosystem. In this paper, an illustrative and provable fast variant of the RSA scheme coined RSA+ is designed to show how a hybridized algorithm that be deployed to improve RSA speed at the decryption stage. RSA+ variant employed the generalized MultiPower RSA with the combination of both Hensel lifting and Chinese Remainder Theorem to achieve its objective of speed enhancement. In this work, suitable illustrations and systematic proof of the speedy RSA+ algorithm is demonstrated. Implementation and performance evaluation of RSA+ running time is done using Python programming language. Results of which are compared with classical RSA and two other variants of MultiPower RSA with different modulus. It is discovered that speedy RSA+ gives a large speed up over the classical RSA scheme while preserving a prescribed security level.

Keywords: Cryptography; Chinese Remainder; Hensel Lifting; Homomorphic encryption; MultiPower RSA; Classical RSA