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.
 Choose two prime numbers, p and q. We must try to take large prime numbers to ensure the high security of our data.
 Compute the modulus for encryption and decryption denoted by n, equal to the product of p and q. Hence, n = p * q.

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 coprime to ‘n’. Coprime 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) = n1
In the above statements, p and q are the prime numbers and hence p1 and q1 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 floatingpoint 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.
 p = 61 and q = 53
 n = p * q = 61 * 53 = 3233

Φ(n) = Φ(p * q) = Φ(p) * Φ(q) = (p  1) * (q  1)
= ( 61  1) * (53  1) = 60 * 52 = 3120

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 coprime to 3120 = 7.
Hence, the public key (e,n) = (7, 3120).

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 floatingpoint 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^{e}mod 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^{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^{37} 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);
}
}
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.