RSA Algorithm | Why It Is The Most Used Encryption Algorithm?

The RSA algorithm is an asymmetric cryptography algorithm, uses two different but mathematically linked keys –one public and one private. Public key is used for encryption and the Private Key is used for decryption.

The public key is well known and shared publicly, but the private key is secret and it is known only to the user who owns the key and must not be shared with anyone. This algorithm was invented by Rivest, Shamir and Adleman in year 1978 that’s why name RSA algorithm.

How does the RSA algorithm work?

The public and private key generation algorithm is the most complex part of RSA cryptography. In this algorithm, public key consists of two numbers where one number is multiplication of two large prime numbers. And private key is also derived from the same two prime numbers.

Encryption strength totally depends upon the key size and if we increase the key size, the strength of encryption increase and the size of key is 1024 or 2048 bits.

Generating Public Key

• Select two large prime numbers, p and q. The prime numbers need to be large so that they will be difficult for someone to figure out.
• Multiply these two numbers to find n = p x q, where n is called the modulus for encryption and decryption.
• Choose a number e and e must be
• An integer.
• Not be a factor of n.
• 1 < e < Φ(n)

• Public Key is made of <e,n>
• A plaintext message m is encrypted using public key (e, n). To find cipher text from the plain text following formula is used to get cipher text C.
• C = m^e mod n

Generating Private Key

• We need to calculate Φ(n)
• Φ(n) = (p-1)(q-1)
• calculate Private Key, d
• d = (k*Φ(n) + 1) / e for some integer k
• The private key is <d, n>
• A ciphertext message c is decrypted using private key <d, n>. To calculate plain text m from the ciphertext c following formula is used to get plain text m.
• m = c^d mod n

Let’s understand with an example

Assume P = 41 and Q = 59.
n= p*q
n=41*59
n=2419

Suppose e = 3

Φ(n) = (p-1)(q-1)
Φ(n) = (41-1)(59-1)
Result Φ(n)=2320

d = (k*Φ(n) + 1) / e for k = 2
d = (2*2320+1)/3
Result d = 1547

For Encryption
Suppose plaintext Message is “m”. Then cipher text is: 
C = m^e mod n
C = m³ mod 2419.

For Decryption
Suppose Cipher Text Message is “C”. Then plaintext is: 
m = C^d mod n
m = C¹⁵⁴⁷ mod 2419.

RSA Key Exchange

Suppose that Aman wants to send a message m to Tarun. If both decide to use RSA algorithm, Aman must know Tarun’s public key to encrypt the message, and Tarun must use his private key to decrypt the message.

To enable Aman to send his encrypted messages, Tarun transmits his public key (n, e) to Aman via a reliable, but not necessarily secret, route. Tarun’s private key (d) is never distributed.

Advantages of RSA Algorithm

1. RSA algorithm depends on using the receiver’s public key, so no need to share any secret key to receive messages from others.
2. Since both public & private key are related to each other, a receiver can’t intercept the message since they won’t have the correct private key to decrypt the message.
3. RSA encryption process is faster than that of the DSA algorithm.

Application of RSA Algorithm

RSA encryption is widely used in Virtual Private Networks (VPNs), email services, web browser (TLS), digital signing for code and certificates. Certificates can be used to verify the public key’s owner, by signing it with the private key of the key pair owner. Apart from that RSA also used in password exchange, banking, & online shopping.

RSA Vulnerabilities

When we use weak random number generators, then the prime numbers created by us are much easier to factor, thus giving attackers an easier time of cracking the RSA algorithm.

Another vulnerability of this algorithm focuses on hardware, attackers can analyze the power being used, use branch prediction analysis, or use timing attacks to find ways to ascertain the key used in the algorithm, thus compromising the data.

Related Questions & Answers