What is RSA Algorithm in Cryptography?

Let’s look at the topics we’ll be discussing in this blog:

• What is RSA Algorithm?
• RSA Encryption Algorithm
• RSA Algorithm Example
• Application of RSA Algorithm
• Possible Attacks on RSA Algorithm
• Difference Between AES and RSA Algorithm
• Advantages of RSA Algorithm Over Other Algorithms
• Conclusion

Check out our youtube video on Cyber Security Full Course:

What is RSA Algorithm?

RSA Algorithm (Rivest Shamir Adleman) was introduced in 1978 by Rivest, Shamir, Adleman as an asymmetric encryption algorithm. There are both public and private keys involved in this algorithm. RSA Algorithm in cryptography is based on the fact that you can find and multiply large numbers easily but finding the factor of their product is difficult.

Mathematical research estimates that if the key value is 100 digits, it would take attackers more than 70 years to find its value. The most difficult part of the algorithm probably is choosing and generating the public and private keys.

RSA Encryption Algorithm

In the RSA Encryption Algorithm, a public key is used for encryption and a private key, different from the public key and only known to the recipient, is used for decryption. The public key would be the product of two large prime numbers. That product is made public. The decryption would require knowledge of the two prime factors of that number and there is no known method to find the prime factors of such numbers. This means that only the person who created the public key will be able to generate the private key as well.

Let’s look at the RSA Algorithm Steps:

1. You can choose any two large prime numbers, say A and B.
2. Next, you can find the product of A and B, say N.
   N = A*B
3. You have to select a public key, say E, for encryption. You have to make sure this key isn’t a factor of (A-1) and (B-1).
4. Now you can select the private key for decryption say, D. The private key should match this equation:
   (D*E) mod (A-1)*(B-1) = 1
5. You can calculate the ciphertext from the plaintext using this equation:
   Ciphertext = Plaintext^E mod N
6. Once the ciphertext is generated, it should be sent to the recipient.
7. You can decrypt the plaintext from the ciphertext using this equation:
   Plaintext = Ciphertext^D mod N

RSA Algorithm Example

For this example, let’s try and work the RSA Encryption Algorithm with random prime numbers, say 7 and 17. So,

A = 7, and B = 17
N = A*B
N = 7*17
N = 119
Now, we have to select a public key, say p, so that isn’t a factor of (A-1) and (B-1).
(7-1)*(17-1) = 6*16 = 96
Now, the factor of 96 is 2*2*2*2*2*3.
So, we can choose our public key, E as 5 since it isn’t a factor of 2 or 3.
Now, to select the private key, we have to make sure it matches this equation:
(D*E) mod (A-1)*(B-1) = 1
(D*5) mod (6)*(16) = 1
(D*5) mod 96 = 1
Now, we can choose D as 77 to satisfy the equation.
(77*5) mod 96 = 1
385 mod 96 = 1
1 = 1
It satisfies the equation so we can move on.
Now, we have to calculate the ciphertext.
Let’s take our plaintext to be 10.
Ciphertext = Plaintext^E mod N
Ciphertext = 10^5 mod 119
Ciphertext = 40
Once, we have the ciphertext we can send it to the recipient.
We can also check the value by decrypting it with the equation:
Plaintext = Ciphertext^D mod N
Plaintext = 40^77 mod 119
Plaintext = 10

That is the plaintext we chose.

Application of RSA Algorithm

Let’s look at some applications of the RSA Algorithm:

• RSA Algorithm is used in hybrid encryption.
• RSA Algorithm is also used in digital signatures.

Possible Attacks on RSA Algorithm

Here’s a list of the possible attacks on the RSA Algorithm:

Plaintext Attack

There can be three types of Plaintext Attacks:

Short message attack

In short message attacks, it is generally assumed that the attacker already knows some of the plaintext messages. Now, if an attacker knows some blocks of plaintext, they could try to encrypt the blocks using the information. Padding bits of encryption is used to prevent a short message attack.

Cycling attack

The reverse process takes place in a cycling attack. The attacker assumes some permutations for the ciphertext. If this assumption is true, they can try and reverse the process to generate the plaintext using the ciphertext.

Unconcealed message attack

There are some rare times when, for some reason, the encrypted ciphertext is the same as the plaintext. The plaintext isn’t concealed and this type of attack is called an unconcealed message attack.

Chosen cipher Attack

In a chosen cipher attack, the attacker finds out the plaintext from the ciphertext using the extended Euclidean algorithm.

Factorization Attack

In a factorization attack, the attacker can impersonate the owners of the key. They can use the information to decrypt sensitive data bypassing the system’s security. The attackers aim at an RSA cryptographic library. This library is used to generate the RSA key. This gives the attackers access to private keys of various security tokens, Motherboard Chipsets, and smartcards because they have the target’s public key.

Difference Between AES and RSA Algorithm

Let’s look at the differences between the AES and RES Algorithms:

Advantages of RSA Algorithm over other Algorithms

There are some advantages of the RSA Algorithm over other algorithms. Here are some of them:

• RSA Algorithm is very easy to implement.
• Confidential data can be transmitted safely and securely using RSA Algorithm.
• RSA Algorithm involves a lot of complex mathematics which makes it more difficult to crack.
• You can easily share the public key with users.

Conclusion

We have discussed the Rivest Shamir Adleman Algorithm in this blog. We have talked about how the algorithm works along with examples. We also know why the RSA Algorithm is more advantageous over other algorithms.