Question

How does RSA cipher encryption algorithm's logic work? and what are the advantages and disadvantages?

Answer 1

RSA(Rivest Shamir Adleman) algorithm is a type of asymmetric cryptographic algorithm, which means that two different keys are used for encryption and decryption. The key which is made available to the public is called Public key and this key is used to encrypt the data, and the key which is only available to the receiver is called Private Key and is used to decrypt the data. Whole process goes as:

1. Receiver generates the public & private key pair.

2. Public key is sent freely to the sender.

3. Sender encrypts the message with the public key of receiver and sends the encrypted data.

4. Receiver receives the encrypted data and decrypts the data using the private key already generated (in step 1) to obtain the original message.

This algorithm is based on the fact that large integers are difficult to factorize.

The algorithm goes as follows (for message m=5):

For Public Key:

• Select two prime numbers. Let P = 3 and Q = 11.
• First part of the Public key: n = P*Q = 3*11 = 33.
• Let small integer exponent say e which is not a factor of n and 1 < e < Φ(n) {Φ(n) = (P-1)(Q-1) as discussed below} Let it to be 7.Since 1 < 7 < 20
• Our encrypted data is calculated as c = m^e mod n = 5⁷ mod 33 = 14
• Thus, c = 14

For Private Key:

• We need to calculate Φ(n) : Such that Φ(n) = (P-1)(Q-1) so, Φ(n) = (2)*(10) = 20
• Now calculate Private Key, d : d = (k*Φ(n) + 1) / e for some integer k For k = 1,
• We have d = (1*20 + 1)/7 => value of d is 3.
• Decrypted data goes as  m = c^d mod n = 14³ mod 33 = 5
• Thus m = 5 (which is our original message).

Advantages of RSA

1. Since encryption process is asymmetric hence only receiver can decrypt the data using only his private key.
2. This algorithm is based on prime factors and becomes hard to crack for large numbers, since large numbers can have large number of factors which increases uncertainty in guessing the correct key.
3. Since key is made public, hence the need for secure transmission of keys gets eliminated.

Disadvantages of RSA

1. Algorithm becomes cumbersome and demanding w.r.t. resources since a lot of mathematical calculations are involved.
2. It takes time for encryption and decryption processes to take place directly because of its complexity in real life situations where there are keys of 1024/2048 bits in length.
3. There is always a need to verify the source of origin of public key by some already verified authority.