RSA Algorithm in Cryptography

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

1. What is RSA Algorithm?
2. Key Generation
3. RSA Encryption
4. RSA Decryption
5. Advantages and Disadvantages
6. 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)

1. First, select two prime numbers p=7 and q=11.
2. Now calculate n= p X q = 7 X 11
   n = 77
3. 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
4. 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).

5. 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⁷ mod 77

M’= [ (15⁴ mod 77)*(15² mod 77)*
( 15¹ 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⁴³ 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

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

Disadvantage

1. RSA has too much computation.

Key Takeaways

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.