RSA Algorithm

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, p 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 e 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 d is-
d = { [ Φ(n) * i ] + 1 } / e for some integer i
The i 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 P 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 = P^emod n to get the encrypted ciphertext. Here, (e, n) is the receiver's public key.

Decryption

To decrypt the ciphertext C to plain text, we will use the formula P = C^d 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 = P^e mod n to encrypt our plain text.

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

C = 13¹³ mod 143

C = 52. 

Therefore, our ciphertext is 52.

We will decrypt this ciphertext using the formula P = C^d mod n.

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

P = 52³⁷ 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.

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);
	}
}

You can also try this code with Online Java Compiler

Run Code

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:

• Difference between Public Key and Private Key
• Design and Analysis of Algorithms
• Cryptographic System
• Difference between Cryptography and Cyber Security
• Difference between Hashing and Encryption
• PGP Protocol
• Introduction to Hashing
• Privacy in Computer Networks
• Cryptography Hash Function 
• Cryptosystem 
• Cyber Attacks and their Types 
• Active and Passive Attacks.
• Difference Between Active Attack and Passive Attack
• Fibonacci Series in Java
   

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.