Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024

RSA Algorithm

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

In a cryptographic system, there are two primary forms of cryptography algorithms. These are-

  1. Symmetric key algorithm- In this algorithm, there is only one key(or secret key) for encryption and decryption of data which is shared by both the sender and receiver. The main issue with the symmetric key algorithm is that it uses the same key for encryption and decryption which increases the chance for easily getting attacked by the third party user which will eventually leads the confidentiality to suffer. 
  2. Asymmetric key algorithm- In this algorithm, there are two different keys for encryption and decryption of data, each with the sender and receiver. This algorithm is also known as the public key encryption algorithm.

(See Difference Between Symmetric and Asymmetric Encryptions)

This article will discuss an asymmetric key algorithm, i.e. RSA algorithm. Before starting with the concept, let’s more understand the asymmetric key algorithm.

Asymmetric Key Algorithm

As said above; there are two different keys with the sender and receiver for encryption and decryption of data. These keys are-

  1. Public key- The key which can be shared with everyone. It is used for the encryption of data. 
  2. Private key- The key which is kept private and is only known to the owner. It is used for the decryption of data.
    Each sender and receiver has its own public and private key. 

(See Difference between Public Key and Private Key)

Note: 

  • The initial data with the sender is known as plain text
  • The data after encryption is known as the ciphertext
  • The data after decryption is known as the plain text.

The below diagram shows the working of the asymmetric key algorithm.

illustration image

Therefore,

  • The sender encrypts the plain text data to the ciphertext data using the receiver’s public key. 
  • The receiver decrypts the ciphertext data to the plain text using its private key.

Now, let’s get started with the RSA algorithm.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

RSA Algorithm

The RSA Algorithm is the most common asymmetric key algorithm. The word RSA is an abbreviation that means Rivest, Shamir and Adelman, who were the inventors of this algorithm, hence the name.

First, we will study the mechanism of the RSA algorithm.

Mechanism

The main task of the RSA algorithm is to generate the public and private keys of the receiver for performing the encryption and decryption of data.

The RSA algorithm uses the following steps to generate the public and private keys.

  1. Choose two prime numbers, and q. We must try to take large prime numbers to ensure the high security of our data.
  2. Compute the modulus for encryption and decryption denoted by n, equal to the product of p and q. Hence, n = p * q.
  3. Calculate the quotient function Φ(n) as Φ(n) = Φ(p*q)
          = Φ(p) * Φ(q)

         = (p - 1) * (q - 1)

where Φ(n) for [ n>=1] is defined as the number of positive integers less than ‘n’ that are co-prime to ‘n’. Co-prime means the GCD(Greatest Common factor) must be 1. Wherever the GCD is 1, we need to put those integers into a set and calculate its cardinality. 

For example, 
Φ(5) = { 1, 2, 3, 4 } = 4 

Φ(6) = { 1, 5 } = 2 

When ‘n’ is a prime number:
Φ(n) = n-1
In the above statements, p and q are the prime numbers and hence p-1 and q-1 are the cardinality for the same.

Generating public key: The public key is denoted as (e,n). Since we have already found n. Now, we will find e.

4. The variable is a small exponent which must be

  • An integer
  • 1 < e < Φ(n)
  • GCD of (e, Φ(n)) = 1 or e and Φ(n) must be coprime

Using these conditions, we can find the value of e which will form our public key.

Generating private key:  The private key is denoted as (d,n). Since we have already found n. Now, we will find d.

5. The formula for finding is-
d = { [ Φ(n) * i ] + 1 } / e for some integer i
The ranges from 1 till the value of d comes as an integer not a floating-point number.

Now, we will take an example to understand this mechanism.

Example

For example, we will take two prime numbers, 61 and 53, as p and q, respectively. We will generate the public and private keys for these numbers.

  1. p = 61 and q = 53
  2. n = p * q = 61 * 53 = 3233
  3. Φ(n) = Φ(p * q) = Φ(p) * Φ(q) = (p - 1) * (q - 1)
           = ( 61 - 1) * (53 - 1) = 60 * 52 = 3120
  4. Public key:
    Since 1 < e < Φ(n) and GCD of e and Φ(n) = 1.
    Therefore, 1 < e < 3120 and GCD of e and 3120 = 1, we will get e as a co-prime to 3120 = 7.
    Hence, the public key (e,n) = (7, 3120).
  5. Private key:
    d = { [ Φ(n) * i ] + 1 } / e for some integer i
    Substituting the values of Φ(n) and e, we get
    d = { [ 3120 * i ] + 1 } / 7
    Starting with i = 1, d = { [ 3120 * 1 ] + 1 } / 7 = 445.86 which is a floating-point number so we will increment i to 2.
    i = 2,  d = { [ 3120 * 2 ] + 1 } / 7 = 891.57
    i = 3,  d = { [ 3120 * 3 ] + 1 } / 7 = 1337.29
    i = 4,  d = { [ 3120 * 4 ] + 1 } / 7 = 1783

Since we got an integer value, we will stop here.
Hence, the private key (d,n) = (1783, 3120).

We will now understand how to encrypt and decrypt the data using the public and private keys generated.

Encryption and Decryption

We will use the generated public key and private key to encrypt and decrypt the data. First, we will understand how to encrypt the data.

Encryption

We will be given plain text as data. We will encrypt this plain text using the following steps.

  • If the plain text is in binary format, convert it into decimal format.
  • Use the formula C = Pemod n to get the encrypted ciphertext. Here, (e, n) is the receiver's public key.

Decryption

To decrypt the ciphertext to plain text, we will use the formula P = Cd mod n where P is the desired plain text and (d, n) is the receiver's private key.

Now, we will take an example to understand the encryption and decryption process.

Example

Suppose we are given a plain text 13, which we want to encrypt to ciphertext and decrypt to plain text. And the given public key and private key of the receiver is (13,143) and (37,143), respectively.
Solution: Given: Public key (e, n) = (13, 143)

Private key (d, n) = (37, 143)

Plain Text = 13

The given plain text is already in the decimal format so we don’t need to change it.

We will use the formula C = Pe mod n to encrypt our plain text.

Substituting the values of P, e and n in the formula, we get-

C = 1313 mod 143

C = 52. 

Therefore, our ciphertext is 52.

We will decrypt this ciphertext using the formula P = Cd mod n.

Substituting the values of C, d and n in the formula, we get-

P = 5237 mod 143

P = 13.

Hence, we get the correct data sent by the sender, i.e. 13.

Thus, we can modify the diagram of the asymmetric key algorithm (described above) according to the RSA algorithm.

illustration image

Now, we will see how to implement the RSA algorithm.

Also read - active and passive attacks

Implementation

Below is the Java code to implement the RSA algorithm.

// Java Program to Implement the RSA Algorithm
import java.math.*;
import java.util.*;

class RSA {
 
public static void main(String args[])
{
	int p, q, n, phi, e, d = 0, i;

	// Taking two prime numbers
	p = 61;
	q = 53; 

	// Calculating n                      
	n = p * q;

	// Calculating phi
	phi = (p - 1) * (q - 1);

	// Generating public key                      
	for (e = 2; e < phi; e++) {
		// e must be less than phi and GCD of (e, phi) must be 1
		if (gcd(e, phi) == 1) {
			break;
		}
	}
	System.out.println("The value of e = " + e); 

	// Generating private key                    
	for (i = 0; ; i++) {
		int x = 1 + (i * phi);
			if (x % e == 0) {
			d = x / e;
			break;
		}
	}
	System.out.println("The value of d = " + d);

	// The data to be encrypted and decrypted                      
	int plain_text = 45;
	System.out.println("The message sent is : " + plain_text);               
	double cipher_text;
	BigInteger msg;

	// Encrypting the data                     
	cipher_text = (Math.pow(plain_text, e)) % n;
	System.out.println("Encrypted message is : " + cipher_text);
 
	// converting int value of n to BigInteger
	BigInteger N = BigInteger.valueOf(n);
 
	// converting float value of cipher_text to BigInteger
	BigInteger C = BigDecimal.valueOf(cipher_text).toBigInteger();
 
	msg = (C.pow(d)).mod(N);
	System.out.println("Decrypted message is : " + msg);
}
 
static int gcd(int e, int phi) {
	if (e == 0)
		return phi;
	else
		return gcd(phi % e, e);
	}
}

The output of the above code will be-

The value of e = 7
The value of d = 1783
The message sent is: 45
Encrypted message is : 1754.0
Decrypted message is : 45


Also Read - Kadanes Algorithm

Frequently Asked Questions

Define cryptography.

Cryptography is a technique for securing information and communications by using codes so that only those who are intended to understand and process the information can do so. As a result, unauthorized access to information is prevented. The prefix "crypt" refers to "hidden," and the suffix "graphy" refers to "writing." 

Define cryptographic algorithms.

Cryptographic algorithms are used for essential tasks such as data encryption, authentication, and digital signatures. There are two types of cryptographic algorithms - symmetric key and asymmetric key algorithms.

What is the difference between a symmetric key algorithm and an asymmetric key algorithm?

In the symmetric key algorithm, there is only one key for the encryption and decryption of data shared by both the sender and receiver. In the asymmetric key algorithm, there are two different keys for encryption and decryption of data, each with the sender and receiver.

What is a public key and a private key?

A public key is a key that can be shared with everyone. It is used for the encryption of data. At the same time, a private key is a key that is kept private and is only known to the owner. It is used for the decryption of data.

Define encryption and decryption.

Converting a normal message (plain text) into a meaningless message (ciphertext) is known as encryption. On the other hand, decryption is the process of converting a meaningless message (ciphertext) back to its original form (plain text). 

Conclusion

In this article, we have studied the RSA algorithm in cryptography. We went through the concept thoroughly and discussed the mechanism and implementation of the RSA algorithm, along with an example.

Recommended Reading:

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, Computer Networks, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio

Also, do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Topics covered
1.
Introduction
2.
Asymmetric Key Algorithm
3.
RSA Algorithm
3.1.
Mechanism
3.1.1.
Example
3.2.
Encryption and Decryption
3.2.1.
Encryption
3.2.2.
Decryption
3.2.3.
Example
3.3.
Implementation
4.
Frequently Asked Questions
4.1.
Define cryptography.
4.2.
Define cryptographic algorithms.
4.3.
What is the difference between a symmetric key algorithm and an asymmetric key algorithm?
4.4.
What is a public key and a private key?
4.5.
Define encryption and decryption.
5.
Conclusion