The purpose of this study is to improve the strength of RSA Algorithm and at the same time improving the speed of encryption and decryption. RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977-78. The RSA crypto-system is the most widely- used public key cryptography algorithm in the world. Its security is based on the difficulty of factoring large integers. This paper presents an improved RSA algorithm which is superior to the original RSA algorithm in terms of strength of encryption and speed of encryption and decryption. This includes the strengthened form of RSA algorithm along with the architecture of the proposed algorithm. A cloud based database is used store the keys in advance. The modified RSA algorithm is compared on various aspects with the original RSA algorithm and the proposed algorithm certainly improve the strength and speed of computation.
K e ywords: Proth Numb e r , Mersenne Prime Numb e r , RSA, cryptography, cloud based da ta ba s e , balanced prime.
I. Intr o duction
The internet has intruded into everything we could imagine. Internet has emerged in such a way that we happen to use it to run our daily life in some way. Huge amount of sensitive and personal data, commercial data and economical data is being handled on the internet. Therefore, there is a need to provide security over the internet. Network security is mostly achieved through the use of cryptography, which is a science based on abstract algebra. We make our messages and data secure and immune to attacks using cryptographic techniques. In cryptography, data are secured by converting original message into cipher text. An algorithm is designed to convert original text into cipher text. A key (a number or set of numbers) on which the algorithm operates on. One of the most widely used cryptographic techniques is RSA Algorithm. In the modified algorithm that we have proposed some concepts of existing RSA algorithm is used along with certain changes of our own. We provide an improvement on the RSA algorithm by using four prime numbers instead of two and storing the key on a cloud based database (example MongoDB) before the algorithm starts.
II. Original RSA Algorithm
The RSA Algorithm is the first ever published and most widely used public key algorithm. It was developed by Ron Rivest, Adi Shamir and Len Adleman, first presented in their 1977-78 article. It was based on the Diffie-Hellman proposal. Its implementation depends on an a priori choice of two large prime numbers p and q, that are multiplied to obtain the RSA modulus N=p*q and a subsequent choice of a public and a private integer parameters, e and d, satisfying e*d = 1+k*(p − 1)*(q − 1) for some integer k. It is composed of three phases: key generation, encryption and decryption.
A. Key Generation Phase
Step 1: Choose two prime numbers, p and q, p not equal to q. Step 2: Compute n=p*q
Step 3: Compute ø (n) = (p -1) * (q-1).
Step 4: Choose an integer e such that gcd(Ø (n), e) = 1; 1 < e <Ø (n).
Step 5: Calculate private key, d such that e*d=1 mod ø (n).
The public key is (n, e) and the private key (d, p, q). Keep all the values d, p, q and ϕ secret.
B . Encryption Phase
A sender sends a message to a receiver using n and e.
Cipher text can be calculated as C= e mod n.
C . Decryption Phase
Receiver keeps ϕ and d private. When the receiver receives the cipher text, private key is used to decrypt the message.
Plain text can be calculated as P = C d mod n.
D. A simple example of RSA Encryption
This is an extremely simple example using numbers you can work out on a pocket calculator.
1. Select prime numbers p=11, q=13.
2. n = pq = 11.3 = 33 ø = (p-1)(q-1) = 10*2 = 20
3. Choose e=3 Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1), and check gcd(e, q-1) = gcd(3, 2) = 1 therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
4. Compute d such that e*d ≡ 1 (mod phi) i.e. compute d = (1/e) mod ø = (1/3) mod 20 i.e. find a value for d such that ø divides (ed-1) i.e. find d such that 20 divides 3*d-1. Simple testing (d = 1, 2, ...) gives d = 7 Check: e*d-1 = 3*7 - 1 = 20, which is divisible by ø.
5. Public key = (n, e) = (33, 3) Private key = (n, d) = (33, 7).
This is actually the smallest possible value for the modulus n for which the RSA algorithm works. Now say we want to encrypt the message P = 7, C =343 mod 33=13. Hence the cipher text C = 13.
To check decryption we compute P′=13 7 mod33=7. We don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that a = b*c mod n =(b mod n) ⋅ (c mod n) mod n.
E. Significance of RSA Algorithm
RSA is a strong encryption algorithm that has stood a partial test of time. RSA implements a public-key cryptosystem that allows secure communications and “digital signatures”, and its security rests in part on the difficulty of factoring large numbers. It is one of the most commonly used cryptographic algorithm. RSA is, in fact, commonly used to securely transmit the keys for another less secure, but faster algorithm.
F . Restriction of RSA Algorithm
For RSA Algorithm to work, the value of ‘P’ must be less than the value of ’n’. If ‘P’ is larger than ’n’, the plain text must be divided into blocks to make ‘P’ less than ’n’.
G. Limitations of RSA Algorithm
Although, RSA Algorithm is one of the secure and commonly used algorithm, it can still be improved. There are many problems in RSA algorithm that needs to be taken care of. Several issues exist that could potentially damage RSA’s security, such as timing attacks and problems with key distribution. Also, RSA is slower than certain other symmetric crypto-systems.
A very major threat to RSA would be a solution to the Riemann hypothesis. Thus a solution has neither been proven to exist nor to not exist. Development on the Riemann hypothesis is currently relatively stagnant. However, if a solution were found, prime numbers would be too easy to find, and RSA would fall apart.
Some of the limitations of RSA Algorithm are:
Speed and comp utationa l cost: As the RSA modulus n is a large number, factoring it is a rather hard task. RSA algorithm employs lengthy calculations for both encryption and decryption. Speed of computation can be improved by modifying the RSA Algorithm.
Attacks: There are several types of attacks on RSA. The obvious one is to factor the modulus N, which will create a total break of the system: the cryptanalyst will be able to decrypt all messages. Another common attack is common modulus attack.The idea of the common modulus is that in a session of RSA with several users there is a trusted entity which defines a modulus N and provides for each user a pair of public and private valid RSA keys defined modulo φ(n), but not the factorization of N. Some other attacks are: low decryption exponent, short message, cyclic attack etc. These attacks can breach the security of RSA Algorithm.
Public Key Authentication: In RSA cryptography public key is used by the sender to encrypt the message. Thus only authenticated user can participate in encryption procedure.
Una uth or iz ed Access to Private Key: RSA Algorithm can completely fall apart if the private key is accessed by an unauthorized entity as the security of RSA Algorithm is completely based on the private key.
III. Problem Definition
RSA Algorithm is very slow due to the computational complexity of the numbers. The RSA algorithm is also prone to security attacks such as factorisation attack, common modulus attack and other attacks. The RSA can fall apart and its security can be compromised. However, the speed of computation as well as the security can be improved by the proposed method. This improvement is achieved by using a cloud based database to store the key parameters instead of calculating them at the time of transmission of data. Also, the security is improved by passing key indexes instead of actual key parameters and using four prime numbers instead of two. One of the prime number is a Proth Number and one is a Mersenne Prime Number, other two being balanced prime numbers.
IV. Proposed T echnique
Our approach is based on modified RSA cryptosystem. We have tried to provide some improvements on the modified RSA cryptosystem. For our approach, we have considered:
i. Four Prime Numbers p, q, r and s. p is a fixed Proth Number q is a fixed Mersenne Prime Number r and s are two Balanced Prime Numbers
ii. n is the common modulus
iii. e is the public key
iv. d is the private key
The proposed algorithm consists of only two stages: encryption and decryption. The key generation phase is not required all the time. Key is generated only once and saved in a cloud based database. The indices are fetched from database instead of actual values and encryption/decryption is performed.
- Quote paper
- Aditya Kumar (Author), 2019, Improved RSA Algorithm based on cloud database using Proth Number and Mersenne Prime Number, Munich, GRIN Verlag, https://www.grin.com/document/511690