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 –