**RSA** is a first successful **public key cryptographic algorithm. **It is also known as an** asymmetric cryptographic algorithm **because **two different keys** are used for encryption and decryption. RSA is named after **Rivest, Shamir and Adleman** the three inventors of RSA algorithm. The algorithm was introduced in the year 1978.

In this section, we will discuss, RSA algorithm along with an example. We will also study the reason for the evolution of the RSA algorithm along with its advantages and disadvantages.

## Content: RSA Algorithm in Cryptography

- What is RSA Algorithm?
- Key Generation
- RSA Encryption
- RSA Decryption
- Advantages and Disadvantages
- Key Takeaways

### What is RSA Algorithm?

RSA is a **public key** cryptographic algorithm in which two different keys are used to encrypt and decrypt the message. That’s why it is also called an **asymmetric** key algorithm.

But what was the need of this asymmetric key cryptography? Why it evolved? Let us discuss the reason behind the evolution of asymmetric key cryptography. The Asymmetric key cryptography evolves due to the **two problems** of **symmetric key cryptography**.

The **first problem** with symmetric key cryptography is the key distribution. The two communicating parties may already be sharing the key which has been distributed to them by any means or the key must be shared with the help of a **key distribution centre**. But, using of key distribution centre compromises the secrecy of the key which hampers **confidentiality** of the message.

The **second problem** with symmetric key cryptography is **digital signatures**. That is, there was a requirement of digital signatures which would assure all the parties that message has been sent from a particular individual. So, there was a lack of **authentication**.

Both of these problems of symmetric key cryptography lead to the evolution of asymmetric key cryptography. In the year 1978 the three inventors at MIT; Rivest, Shamir and Adleman introduced RSA public key algorithm which follows the essential steps below:

- In RSA public key cryptography each user has to generate two keys a
**private key**and a**public key.** - The public key is circulated or published to all and hence others are aware of it whereas, the private key is secretly kept with the user only.
- A sender has to encrypt the message using the intended receivers public key.
- Only the intended receiver can crack the message. In between the communication no one can harm to the confidentiality of the message as the message can only be decrypted by the intended receiver’s private key which is only known to that receiver.

**M’= E(PU _{r}, M) ………..Encryption**

**M = D(PR _{r}, M’) ………..Decryption**

**M** *is the original message*

**M’*** is encrypted message*

**E** *is an encryption algorithm*

**D*** is a decryption algorithm*

**PU _{r }**

*is the receivers public key*

**PR**

_{r}*is the receivers private key*

**PU**

_{s }*is the senders public key*

**PR**

_{s}*is the senders private key*

The two problems of symmetric key cryptography i.e. confidentiality and authentication can be overcome by the double use of public key cryptography.

1.** First**, encrypt the message by the **sender’s private key** which can be decrypted by the sender’s public key(known to all). This provides a digital signature to the sender’s message and thus **authentication** is achieved.

**E(PR _{s}, M)**

2. In the **next step**, encrypt again with the **receiver’s public key**. This will allow only the intended receiver to decrypt the message, this provides the **confidentiality** to the message.

**M’= E(PU _{r}, E(PR_{s}, M)**

The Decryption is shown by the following expression:

**M= D(PU _{s}, E(PR_{r}, M’)**

### Key Generation

Till now we have seen that every sender or a receiver must have **two keys** a **public key** and a **private key**. In this section, we will discuss the steps to derive a public and a private key.

In RSA, the encryption and decryption expressions are in the exponential form:

**M’= M ^{e} mod n …………. Encryption, Public key (e, n)**

**M= M’ ^{d} mod n …………. Decryption, Private key (d, n)**

Steps to generate **public key **(e, n) & **private key** (d, n)

- First, select two prime numbers p=7 and q=11.
- Now calculate n= p X q = 7 X 11

**n = 77** - Calculate Ø(n)= Ø(pXq)

= Ø(p) X Ø(q)

= (p-1) X (q-1) ……. Ø (a) = (a-1) if**a**is a prime number.

=(7-1) X (11-1)

= 6X10

**Ø(n) = 60** - Select e such that
**1 ≤ e < Ø(n)**and also ‘e’ should be**coprime**to Ø(n).

So, I select**e=7.**Our

**Public Key**for this particular example is**(7,77)**.

- Now we will determine the value of
**d**. The value of d can be calculated from the formula given below:

In the expression above we know that and e and Ø(n) are the coprime numbers so in this case d is the multiplicative inverse of e. To calculate the value of d use the formula below:

In this equation above we know the value of Ø(n), e, the value of i is unknown. First, we have to put the value of i=1.

If the result is in decimals then we have to compute the equation again but this time we have to increment the value of i by 1 so we will compute the equation with i=2. Keep on incrementing the value of i till the above equation results in a proper integer.

So, by trial and error method, for i=5 we get the result 43 i.e.

Now we have generated both the private and public key.

**Private Key (43, 77)**

**Public Key (7, 77)**

### RSA Encryption

Now, after generating the private and public key we will now encrypt the message. In RSA the plain text is always encrypted in **blocks.** The **binary value** of each plain text block should be** <n**. Encryption is done with the intended receiver’s **public key**. The expression to calculate cipher text is as follow:

**M’= M ^{e} mod n**

In our example, the value of e=7 and n=77 i.e. public key (e, n) and we have to take the value of M such that **M<n**. We will take the value of M=15. So, the expression becomes

**M’= 15 ^{7 }mod 77**

**M’= [ (15 ^{4 }mod 77)*(15^{2 }mod 77)***

**( 15**

^{1 }mod 77) ]mod77**M’= [(36)*(71)*(15)] mod77**

**M’=71 ……… Cipher Text**

### RSA Decryption

Done with the encryption now its time to decrypt the message. For decryption in RSA, we require a cipher text and the private key of the corresponding public key used in encryption.

In our example the cipher text we have M’=71 and the private key we have (43, 77). The expression to calculate plain text is as follow:

**M= M’ ^{d} mod n**

**M= 71 ^{43} mod 77**

**M= 15**

So, this is the method to encrypt and decrypt the message in RSA. It is very important to remember that in RSA we have to encrypt the message using the intended receiver’s public key. So, the message can only be decrypted by the intended receiver private key. This provides **confidentiality** to our message.

### Advantages and Disadvantages

**Advantage**

- RSA is stronger than any other symmetric key algorithm.
- RSA has overcome the weakness of symmetric algorithm i.e. authenticity and confidentiality.

**Disadvantage**

- RSA has too much computation.

### Key Takeaways

- RSA is a
**public key**or**asymmetric key algorithm**. - RSA stands for
**Rivest, Shamir and Adleman**the three inventors of RSA algorithm. - Each user has to generate
**two keys**public key known to all and private key only known to him. - Encryption is done using the
**public key**of the**intended receiver**. - A receiver cracks the message using its
**private key.** - Encrypting the message using receivers public key assures
**confidentially**of the message as no third party would be able to crack the message because the message can only be decrypted by using receivers private key which is only known to him. - Using the double public key scheme, we can also achieve
**authenticity**.

So, this is all about the RSA algorithm. So far, we have discussed the methods of generating a public key and a private key. We have also studied encryption and decryption in RSA using these keys.

Carolene Price says

This was explained extremely well – succinctly and simply. This is my first time at studying IT binary terms but I could understand it completely. Other sites I looked at and books were nowhere as good as this site.