Improving the key generation process of the RSA algorithm

Abstract

RSA Algorithm is the mostly used public key cryptography and the demand for a better security is one of the challenges faced to continue the reliance of the users. RSA is a well- known cryptosystem which supports data security by use of data encryption without necessarily having users to share their private keys with one another. It works on the base of multiplication of two prime numbers. Currently, different kinds of attacks have been identified against RSA by cryptanalysis, which come as a result of the random selection of small prime numbers during the key generation process of the RSA key pair. The study specifically focused on improving the RSA algorithm during key generation process and it was guided by different objectives which included to identify the weaknesses in the use of the RSA algorithm for data security such as random selection of prime numbers to be used in the encryption key generation process, to build an improved procedure for generating a key in RSA algorithm and to test the strength of the new improved key generation algorithm. In an attempt to contribute in the fixing one of the security gaps identified within the working of RSA, a quantitative research study was conducted. A Primality test that provides a faster method for excluding a number was conducted using Fermat’s little theorem . The theorem states that for a prime integer p and 1 a p, then ap􀀀1 1 (mod p). In this study, cryptool was adopted to analyse the RSA cryptosystem without FLT implementation and RSA cryptosystem with FLT implementation. The results from the cryptool were used to identify the difference in the public key generation and in factorization of the modulus in both simulations. The study findings showed that the modified RSA Algorithm with implementation of FLT, mersenne primes, checking of the bit length with logarithmic and prime number theorem approaches, compared to the original RSA Algorithm, is better in terms of security. This was based on the fact that, the modification of RSA Algorithm utilized exclusively large prime numbers in generating modulo n to improve the security against factorization attack. It was important to affirm that this cryptographic system, ensures that security is guaranteed by implementing a robust number theorem that exclusively generates large prime numbers. The study recommended that, in addition to Fermat’s little theorem, Miller–Rabin primality test should also be applied in RSA cryptosystem due to the existence of Carmichael number which can pass a Fermat primality test.