ABSTRACT

Cryptography is the study that provides security service. It concerns with confidentiality, integrity, and authentication. Public key cryptography provides an enormous revolution in the field of the cryptosystem. It uses two different keys where keys are related in such a way that, the public key can use to encrypt the message and private key can be used to decrypt the message. This paper proposed an enhanced and modified approach of RSA cryptosystem based on “n” distinct prime number. This existence of “n” prime number increases the difficulty of the factoring of the variable “N” which increases the complexity of the algorithm. In this approach, two different public key and private key generated from the large factor of the variable “N” and perform a double encryption-decryption operation which affords more security. Experiment on a set of a random number provided that the key generation time, analysis of variable “N”, encryption and decryption will take a long time compared to traditional RSA. Thus, this approach is more efficient, highly secured and not easily breakable.

Keywords:

RSA Algorithm, Encryption, Decryption, Cryptosystem, Security, Public Key, Private Key

1. Introduction

Security refers to the process of keeping information confidential by protecting it from unauthorized users. According to security goal, confidentiality means to keep a data secured. It must be hidden from unauthorized access. Integrity proposes prevention of modifications. Availability means data being available to authorized persons when needed the data. Confidentiality, integrity, and availability are three security goals [1] . Security goal can achieve using cryptography which is a widely used method around the world.

Cryptography is a Greek word which means secret writing. It ensures secure communication and prevents the public from reading private messages. The cryptographic system is usually characterized by three main dimensions. They are, the operations involved in the transformation of plain text to cipher text, the number of secret keys used and the method of processing the plaintext [2] . Based on that property, cryptography is classified into two broad classifications. One of them is symmetric key and another is asymmetric key. Symmetric key cryptosystem uses the same key for encrypting and decrypting a message. Asymmetric key cryptosystem uses two different keys, the Public key for encrypting the message and private key for decrypting the message.

The Public key cryptosystem is based on two related keys, one is a public key and another is a private key. The sender generates a public key and encrypts the message. Sender shares one key which is called a private key and receiver decrypts the message using that key. The encrypted message cannot be decrypted by unwanted people, who know the public key only. In public key cryptography, the private key is always link with mathematically to the public key. It is always possible to attack public key system to generate a private key. This attack can be opposed by creating problem to generate a private key from the public key. Some public key algorithms designed such that deriving the private key from public key need to factorize large number by the attacker. RSA is known for such type of algorithm [3] . It takes two large prime number “p” and “q” and multiplies them to get a big number “N”. The idea behind RSA is some mathematical operation easier to do but the inverse is very difficult without any additional information.

This research presents a new modification of RSA algorithm which is Modified RSA (MRSA) based on “n” distinct prime numbers with double encryption and decryption process. The weakness of RSA algorithm is the use of two prime numbers, small encryption exponent and use the same key for encryption and signing. This schema is based on “n” distinct prime numbers instead of two prime numbers which give an opportunity to select a big encryption exponent from large product “N” to enhance the security. Numerous prime numbers and big encryption exponent increase the factoring time comparing to RSA algorithm. The double encryption and decryption process make the algorithm stronger than RSA.

The rest of the paper is structured as follow. In Section 2, the proposed scheme represents some related work. In Section 3, there is a discussion about research methodology. The RSA algorithm and proposed model for RSA modification is described in Section 4 and 5. Section 6 represents implementation and result. Conclusion and future work are discussed in Section 7.

2. Related Works

This section involves the work done by various researchers in the field of RSA cryptosystem. The discussion is based on the Modification of RSA algorithm through the recent past. M. Thangavel et al. [4] proposed a modified RSA key generation algorithm which uses four primes instead of two primes and thereby increasing the time needed to find these primes. While increasing the security, the key generation time of the proposed algorithm is higher than original RSA. According to [5] , encryption and decryption are not only dependent on “N” but also other new factors computed. The encryption and decryption technique is very complex and several factors are introduced without clearly justified. H. M. Sun et al. [6] came up with an algorithm which is known as dual RSA having two aspects from RSA with decreasing the needs of the storage for keys. It has two applications, first one is known as blind signature and other is known as security. Segar’s [7] introduced a new idea to determine the private key without using the factoring approach using Pell’s equation. Pell’s RSA increases the strength that taking the private key “d” above the Wiener’s possible range [8] .

A Modified RSA introduced in the paper [9] that usage of three prime numbers instead of two prime numbers. The encryption and decryption process is the same as original RSA algorithm. Paper [10] ensures higher security by reducing modulus and private exponent in modular exponentiation. The performance of the decryption and signature generation are improved by this approach. A modification in encryption and decryption which involves magic rectangle and randomness of ciphertext which is calculated from the plain text was proposed in paper [11] . The main drawback of this approach is the need of additional time for constructing a magic rectangle. Chhabra and et al. [12] introduced an approach that eliminated the requirement of transferring “N” making it difficult for hackers to derive at the prime numbers used. Though the system can be cracked with the value of “k_p” and “d” unknown. Security is ensured by using dual modulus based double encryption and decryption with the use of Jordan function in the paper [13] . A new concept of adding a third prime number in the paper [14] increases the divisible time of modulo “N”. The speed of encryption and decryption is increased compared to traditional RSA. Kong et al. [15] came up with an attack on the Encinas-Masqu’e-Dios algorithm. This algorithm uses two prime number “s”, “t” and “N” represents the multiplication of these two prime numbers. The algorithm is insecure when the “public key” e satisfies the conditions e > s + t and e > N^1/4. Rui’s paper [16] developed a method which surpasses the original RSA algorithm in term of encryption and decryption speed. This algorithm is known as k-RSA algorithm combined k^th power residue theory and RSA algorithm.

This research focuses on to modify RSA algorithm and enhance the security. The schema is based on “n” prime numbers instead of two prime numbers with double encryption and decryption process. Multiple prime numbers increase the factoring time to get the private key. The encryption and decryption process is considered a pair of a random number and their modular multiplicative inverse to increase the security of RSA to a great extent.

3. Research Methodology

A modify RSA algorithm is proposed using “n” distinct prime numbers. A pair of a random number and their modular multiplicative inverse is used to increase the security of the RSA algorithm. Key generation, encryption and decryption time of Modified RSA (MRSA) algorithm to break the system is significantly higher. An observation has been performed using JAVA programming language. Modified RSA (MRSA) is implemented using JAVA Big Integer library functions for simulation purpose [17] . It is possible for the user to enter a prime number or set the bit length of prime numbers to generate automatically using the secure random function. Big Integer library provides various functions such as modular arithmetic, GCD calculation, primality testing, prime generation, bit manipulation and some other operations. Various bit length prime numbers are generated by using the prime generator function of Java Big Integer library to calculate key generation, encryption and decryption time. The Modified RSA (MRSA) model performs a comparison for key generation, encryption and decryption time between RSA and Modified RSA (MRSA) based on these calculated times for specific bit length.

4. RSA Cryptosystem

RSA is a public key algorithm based on the assumption that some mathematical operation easier to do in one direction but the inverse is very difficult. The idea behind RSA is that it is easier to multiply but difficult to factor the large number. Multiplication can be computed in polynomial time whereas factoring time can grow exponentially proportional to the size of the number.

RSA KEY GENERATION

RSA_key_gen()

Input:

Two prime numbers p and q

Output:

Public key exponent: {e, N}

Private Key exponent: {d, N}

Procedure:

$N\leftarrow p\ast q$

Compute Euler phi value of N

$\Phi \left(N\right)\leftarrow \left(p-1\right)\ast \left(q-1\right)$

Find a random variable e, satisfying $1<e<\Phi \left(N\right)$ and $\gcd \left(e,\Phi \left(N\right)\right)=1$

Compute a random number d, such that $d\ast e\equiv 1\mathrm{mod}\Phi (\; N\; )$

RSA ENCRYPTION AND DECRYPTION

The encryption is done with the help of public key exponent and the decryption is done with the help of private key exponent.

RSA_Encryption()

Input:

Plain text message, M (

Public key exponent: {e, N}

Output:

Cipher text, X

Procedure:

$X\leftarrow \left(M^e\mathrm{mod}N\right)$

RSA_Decryption()

Input:

Ciphertext message, X

Private key exponent: {d, N}

Output:

Decrypted plain text, Y

Procedure:

$Y\leftarrow \left(X^d\mathrm{mod}N\right)$

5. Proposed Model

The proposed Modified RSA (MRSA) scheme focuses on mitigating the major issues of RSA system. Most cases the major issue is, it is breakable because of easily computation of keys based on “N”. Since it is the only product of two prime numbers, “N” can be easily traceable [18] . Once the value of “N” is obtained, a hacker can find the keys and break the system. The major modifications which make the system efficient and secure are discussed in the below section.

MRSA KEY GENERATION

The proposed model involves “n” distinct prime numbers. In this paper, all calculation and performance analysis is performed using four large prime numbers. The public and private key exponent consists of three components. “N” is the product of four prime numbers “w”, “x”, “y”, and “z”. The public key exponent consists of three components (e, f, N) where “e” and “f” are randomly taken. It further adds more complexity along with the factoring of “N”. Since only the value of “N” is kept as a public and private component, an attacker with the knowledge of “N” cannot determine the value of four prime numbers which are the basis for finding the value of “N” and subsequently “e” and “f”. The private key exponent consists of three components (d, g, N). For security purpose, the bit length of all four-chosen prime is of the same length as in case of traditional RSA. The algorithm is presented below.

MRSA_key_gen()

Input:

Four prime numbers w, x, y, and z

Output:

Public key exponent: {e, f, N}

Private Key exponent: {d, g, N}

Procedure:

$N\leftarrow w\ast x\ast y\ast z$

Compute Euler phi value of N

$\Phi \left(N\right)\leftarrow \left(w-1\right)\ast \left(x-1\right)\ast \left(y-1\right)\ast \left(z-1\right)$

Find a random variable e, satisfying $1<e<\Phi \left(N\right)$ and $\gcd \left(e,\Phi \left(N\right)\right)=1$

Find another random variable f, satisfying $1<f<\Phi \left(N\right)$ and $\gcd \left(f,\Phi \left(N\right)\right)=1$

Compute a random number d, such that $d\ast e\equiv 1\mathrm{mod}\Phi (\; N\; )$

Compute another random number g, such that $f\ast g\equiv \text{1}\mathrm{mod}\Phi (\; N\; )$

MRSA ENCRYPTION AND DECRYPTION

The encryption is done with the help of public key exponent and the decryption is done with the help of private key exponent. The encryption and decryption are not only related to “N” which consists of four large prime numbers making it difficult to factor but also four random components “e”, “f”, “d”, “g” are involved to make it even more difficult to break the system.

MRSA_Encryption()

Input:

Plain text message, M (

Public key exponent: {e, f, N}

Output:

Cipher text, X

Procedure:

$X\leftarrow {\left(M^e\mathrm{mod}N\right)}^f\mathrm{mod}N$

MRSA_Decryption()

Input:

Ciphertext message, X

Private key exponent: {d, g, N}

Output:

Decrypted plain text, Y

Procedure:

$Y\leftarrow {\left(X^g\mathrm{mod}N\right)}^d\mathrm{mod}N$

Figure 1 present flow chart representation of Modified RSA (MRSA) algorithm. Four distinct prime number is taken as input to calculate N and Φ(N). A Pair of the random number (e, f) is selected from the range 1 < e < Φ(N) as the public key exponent. The modular multiplicative inverse of those random numbers (d, g) is calculated to use as the private key exponent. Encryption and decryption is done by using those private key and public key exponents.

Let us discuss an example problem using the proposed Modified RSA (MRSA) algorithm.

MRSA example

・ Take four distinct prime numbers $w=53,x=41,y=43,z=47$ .

・ Compute $N=w\ast x\ast y\ast z$ .

・ $N=53\ast 41\ast 43\ast 47=4391633$ .

・ Compute Euler phi value of N

$\Phi \left(N\right)=\left(w-1\right)\ast \left(x-1\right)\ast \left(y-1\right)\ast \left(z-1\right)$

$\Phi \left(N\right)=\left(53-1\right)\ast \left(41-1\right)\ast \left(43-1\right)\ast \left(47-1\right)=4018560$

・ Find a random number e, satisfying $1<e<\Phi \left(N\right)$ and $\gcd \left(e,\Phi \left(N\right)\right)=1$ .

$e=41$

・ Compute a random number d, such that, $d\ast e\equiv 1\mathrm{mod}\Phi \left(N\right)$ .

$d=294041$

・ Find a random number f, satisfying $1<f<\Phi \left(N\right)$ and $\gcd \left(f,\Phi \left(N\right)\right)=1$ .

$f=97$

・ Compute a random number g, such that, $g\ast f\equiv 1\mathrm{mod}\Phi \left(N\right)$ .

$g=455713$

・ Input message, $M=12321$

・ Encryption, $X={\left(M^e\mathrm{mod}N\right)}^f\mathrm{mod}N=1081588$

・ Decryption, $Y={\left(X^g\mathrm{mod}N\right)}^d\mathrm{mod}N=12321$

6. Implementation and Result

The algorithm is implemented in JAVA 8 running on an Intel (R) Core (TM) i5-3230M CPU @ 2.60 GHz machine and 4.00 GB RAM. The algorithm (RSA and MRSA) have different important parameter affecting its level of security and speed. Increasing the modulus length invoke complexity of decomposing it into factor. Thus, also increase the length of the private key and hence difficult to detect the key. The RSA and Modified RSA (MRSA) parameter changes depend on time and others remain fixed to study the relative emphasis.

6.1. Performance Analysis

The proposed Modified RSA (MRSA) algorithm is examined on varying bit sizes of input.

Performance of original RSA algorithm by Rivest, Shamir, and Adleman [3] are depicted in Table 1. Also the performance of Modified RSA (MRSA) scheme in terms of key generation, encryption time and decryption is shown in Table 2.

Comparing the above tables, it can be concluded that the time of key generation of Modified RSA (MRSA) is higher than that of RSA. The higher key generation time of Modified RSA (MRSA) can be seen as an advantage by the fact that the time to break the system is high because of the extra complexity added.

Figure 2 depicts the encryption time comparison between RSA and proposed Modified RSA (MRSA) scheme. It illustrates that, for the lower bit length of prime numbers, two algorithms consume the almost identical amount of time. But with the increase of bit length, the difference between curves rises rapidly.

For example, input primes of bit length 2048, encryption time in Modified RSA (MRSA) is 21.9 ms and RSA takes 3.32 ms.

Figure 3 shows the decryption time comparison between RSA and proposed Modified RSA (MRSA) scheme. It demonstrates the almost identical amount of time consumed by RSA and Modified RSA (MRSA) for the lower bit length of prime numbers. With the increase of bit length, the difference between curves elevates rapidly. For example, input primes of bit length 4096, decryption time in Modified RSA (MRSA) is 19,983.37 ms and original RSA takes 1116.24 ms

From the above graphs, it can be easily seen that encryption and decryption times are higher than RSA. The increase in time is adaptable because it increases the security to a great extent in the proposed Modified RSA (MRSA) method.

6.2. Complexity Analysis

Comparison between complexity analysis of RSA algorithm and Modified RSA (MRSA) algorithm is discussing in below.

6.2.1. Complexity of RSA Algorithm

Complexity for Random selected two prime numbers:

・ The complexity of MILLER-RABIN gives the above-mentioned complexities for finding a prime number is $O\left(s\ast {\left(\log 2p\right)}^2\ast \ln p\right)$ [19] .

・ Similarly, the complexity of the second number is $O\left(s\ast {\left(\log 2q\right)}^2\ast \ln q\right)$ .

Complexity for calculation of N:

・ The complexity of computation of N is $O\left(\log 2p\ast \log 2q\right)$ .

Complexity of Computing Euler phi value of N

・ By MODULAR-EXPONENTIATION, the complexity for the second part is (N) −1. The complexity of compute Euler phi value of N is [19] : $O\left({\left(\log 2\left(p-1\right)\ast \left(q-1\right)\right)}^2\ast \left(\left(p-1\right)\ast \left(q-1\right)-1\right)\right)$ .

Complexity for random variables e:

・ The complexity of finding the random variable e is $O\left(\log 2\left(p-1\right)\ast \left(q-1\right)+\gcd \left(e,\left(p-1\right)\ast \left(q-1\right)\right)\right)$ , as it is known that e and (N) are coprime to each other so $\gcd \left(e,\left(p-1\right)\ast \left(q-1\right)\right)=1$ , and so complexity is $O\left({\left(\log 2\left(\log 2p-1\right)\ast \left(\log 2q-1\right)\right)}^2+1\right)$ .

6.2.2. Complexity of Modified RSA (MRSA) Algorithm

The complexity will increase based on the number of the prime numbers conceded for the proposed algorithm.

Complexity for Random Selected prime numbers:

・ Complexities for finding first prime number is $O\left(s\ast {\left(\log 2w\right)}^4\ast \ln w\right)$ .

・ Similarly, the complexity of the second number is $O\left(s\ast {\left(\log 2x\right)}^4\ast \ln x\right)$ .

・ The complexity of the third number is $O\left(s\ast {\left(\log 2y\right)}^4\ast \ln y\right)$ .

・ Similarly, the complexity of the fourth number is $O\left(s\ast {\left(\log 2z\right)}^4\ast \ln z\right)$ .

Complexity for calculation of N:

・ The complexity of computation of n is $O\left(\log 2w\ast \log 2x\ast \log 2y\ast \log 2z\right)$ .

Complexity of Computing Euler phi value of N

・ Complexity of compute Euler phi value of N is: $O\left({\left(\log 2\left(w-1\right)\ast \left(x-1\right)\ast \left(y-1\right)\ast \left(z-1\right)\right)}^4\ast \left(\left(w-1\right)\ast \left(x-1\right)\ast \left(y-1\right)\ast \left(z-1\right)-1\right)\right)$ .

Complexity for random variables e and f:

・ The complexity of finding the random variable e is $O\left(\log 2\left(w-1\right)\ast \left(x-1\right)\ast \left(y-1\right)\ast \left(z-1\right)+\gcd \left(e,\left(w-1\right)\ast \left(x-1\right)\ast \left(y-1\right)\ast \left(z-1\right)\right)\right)$ , as it is known that e and (N) are coprime to each other so $\gcd \left(e,\left(w-1\right)\ast \left(x-1\right)\ast \left(y-1\right)\ast \left(z-1\right)\right)=1$ , andso complexity is $O\left({\left(\log 2\left(\log 2w-1\right)\ast \left(\log 2x-1\right)\ast \left(\log 2y-1\right)\ast \left(\log 2z-1\right)\right)}^4+1\right)$ .

・ Similarly, Complexity of finding the random variable f is $O\left({\left(\log 2\left(\log 2w-1\right)\ast \left(\log 2x-1\right)\ast \left(\log 2y-1\right)\ast \left(\log 2z-1\right)\right)}^4+1\right)$ .

Comparing the above complexity it depicts that Modified RSA (MRSA) is more complex than RSA algorithm. The complexity will increase depending on the number of primes considered for the algorithm.

6.3. Security Analysis

A wide variety of attacks are possible on RSA which includes brute force attack, timing attack etc. [20] . The time needed to break an RSA system is equivalent to the time needed for finding the prime numbers used.

This introduces the requirement of factoring the product “N”. Elliptic Curve factorization Method (ECM) [18] and General Number Field Sieves (GNFS) [21] is used commonly for factoring “N”. These are the fastest known factoring methods. Even though an attacker can factorize “N” by using those methods but it is still not sufficient enough in the computation of two arbitrary component “e” and “f”. Above factorization technique can be used to find “w”, “x”, “y”, “z” but “e” and “f” can only be found by an exhaustive brute force attack. In other words,

${\Omega }_{\text{system}}={\Omega }_{w,x,y,z}+{\Omega }_{\text{bruteforce}}$

Here,

Ω_system = Time needed to break the system

Ω_w,x,y,z = Time needed to find w, x, y, z using GNFS or ECM

Ω_{brute force} = Time needed for brute force attack for finding e, f

The important observation is, Modified RSA (MRSA) involves four primes “w”, “x”, “y”, “z” and two random numbers “e”, “f” for encryption whereas the original RSA involves only two prime numbers “w”, “x” and only one random number “e” for encryption. So, the time needed to break Modified RSA (MRSA) algorithm will be greater than the time needed to break the original RSA at least by a factor of 2. And this will make the proposed Modified RSA (MRSA) algorithm more secure than the original RSA algorithm.

7. Conclusion and Future Work

The security of RSA depends on factoring the large number. This research works based on “n” distinct prime numbers instead of two prime numbers and it increases the attacking time to find the large prime number. The key generation of Modified RSA (MRSA) depends on large factor value “N” thus it needs higher key generation time. The higher the key generation time increases the time need to break the system which makes the system stronger. The double encryption and decryption procedure of Modified RSA (MRSA) is simple compared to the RSA algorithm thus it is not overhead on the system. Encryption and decryption also take more time than RSA algorithm. The accomplishment of the algorithm is measured with reference to time taken for brute force attack. Limitation of this proposed schema is it will not work properly unless “n” distinct prime numbers are considered. To enhance the security of RSA algorithm by adding some extra factors in encryption and decryption process can be a good future work.

Cite this paper

Islam, M.A., Islam, Md.A., Islam, N. and Shabnam, B. (2018) A Modified and Secured RSA Public Key Cryptosystem Based on “n” Prime Numbers. Journal of Computer and Communications, 6, 78-90. https://doi.org/10.4236/jcc.2018.63006

References