Updated August 10, 2023
Introduction to RSA Algorithm
RSA algorithm is the most popular asymmetric key cryptographic algorithm based on the mathematical fact that it is easy to find and multiply large prime numbers but difficult to factor their product. It uses both private and public key (Keys should be very large prime numbers). Mathematical research suggests that if the value of keys is 100 digit number, then it would take more than 70 years for attackers to find the value of keys. The real challenge in RSA algorithm is to choose and generate the public and private keys.
Working of RSA Algorithm
Working of RSA algorithm is given as follows:
Step 1: Choose any two large prime numbers to say A and B.
Step 2: Calculate N = A * B.
Step 3: Select public key says E for encryption. Choose the public key in such a way that it is not a factor of (A – 1) and (B – 1).
Step 4: Select private key says D for decryption. Choose the private key in such a way that it matches the below-mentioned equation
(D * E) mod (A – 1) * (B – 1) = 1.
Step 5: For encryption calculate the cipher text from the plain text using the below-mentioned equation
CT = PT^E mod N
Step 6: Send the cipher text to the receiver.
Step 7: For decryption calculate the plain text from the Cipher text using the below-mentioned equation
PT = CT^D mod N.
Example of RSA algorithm
Here I have taken an example from an Information technology book to explain the concept of the RSA algorithm.
Step 1: In this step, we have to select prime numbers.
suppose A is 7 and B is 17
Step 2: Calculate N
N = A * B
N = 7 * 17
N = 119
Step 3: Select public key such that it is not a factor of f (A – 1) and (B – 1).
= (7 – 1) * (17 – 1)
= 6 * 16
= 96
factor of 96 is 2 * 2 * 2 * 2 * 2 *3
So here we select encryption key E as 5 because it is not a factor of both 2 and 3.
Step 4: Select private key in such way that it match following equation
(D * E) mod (A – 1) * (B – 1) = 1.
(D * 5) mod (7 – 1) * (17 – 1) = 1
(D * 5) mod (6) * (16) = 1.
(D * 5) mod 96 = 1
After some mathematical computation, i have select D as 77
( 77 * 5) mod 96 = 1.
385 mod 96 = 1
1 = 1
Hence the equation is equal.
Step 5: Calculate cipher text
let’s take plain text as 10
CT = PT^E mod N
CT = 10^5 mod 119
CT = 100000 mod 119
CT = 40
Step 6: send cipher text to the receiver.
Step 7: calculate plain text
PT = CT^D mod N.
PT = 40^77 mod 119.
PT = 10 which is the original plain text.
Attacks on RSA
Below is the list of some possible attacks on RSA algorithm:
1. Plain text Attack
Plain text attacks are classified into three categories
- Short message attack: In this type of attack, the assumption is that the attacker knows some blocks of the plain text message. If an attacker knows some block of plain text, then he could try to encrypt the blocks of plain text using the information and try to convert it into cipher text. To prevent a short message attack, we can use the padding bits for encryption.
- Cycling attack: In cycling attack, the reverse process is done. An attacker assumes that the ciphertext is formed using some permutations operations. If the attacker assumption becomes true, then he can try the reverse process to obtain the plain text from the cipher text.
- Unconcealed message attack: In some rare cases, it is found that some encrypted cipher text is the same as the plain text i.e original text. This means that the plain text is not hidden. Such type of attack is called an unconcealed message attack
2. Chosen cipher Attack
In this type of attack, the attacker can find out the plain text from cipher text using the extended euclidean algorithm.
3. Factorization Attack
In factorization Attack, the attacker impersonates the key owners, and with the help of the stolen cryptographic data, they decrypt sensitive data, bypass the security of the system. This attack occurs on An RSA cryptographic library which is used to generate RSA Key. By doing this, Attackers can have the private keys of n number of security tokens, smartcards, Motherboard Chipsets by having a target’s public key.
Recommended Articles
This has been a guide to RSA Algorithm. Here we discuss the basic concept, working, examples and different attacks of RSA algorithms. You may also have a look at the following articles to learn more –
