Do You Know: What Is a RSA Algorithm?

Millions of people use advanced technologies in their lives, personally and professionally, daily. As a result, they store and exchange personal data regularly. Failure to safeguard gadgets exposes systems to fraud, resulting in significant failures and a boost in cybercrime. Encryption and cybersecurity are some of the most effective ways to combat cybercrime. So, in this article, we will look at one of the encryption algorithms, the RSA algorithm.

• What is the RSA algorithm?
• How does the RSA algorithm work?
• Example of RSA algorithm
• How to generate RSA keys?
• Numerical on RSA algorithm

What is the RSA algorithm? 

The RSA algorithm is an asymmetric cryptography algorithm widely regarded as the most secure encryption method. Rivest, Shamir, and Adleman invented it in 1978, hence the name RSA algorithm. You may wonder what I mean by saying the RSA algorithm is asymmetric. It means it works on two different keys: the Public Key and the Private Key. And, as the name implies, the Public Key is distributed to everyone while the Private Key is kept private. The RSA algorithm is based on how difficult it is to factorize a large integer.

You might be wondering why this algorithm was created in the first place. Let me illustrate by using an example:

Assume there are two friends, Atul and Vikram. Atul wishes to reveal some information to his friend Vikram. Because Atul and Vikram are on opposite sides of the country, they can’t just whisper it to each other. Yes, but Atul can document it and mail it to Vikram, or he can call him, but each communication channel is not secure, and anyone can easily intercept the message.

You can also explore: Different Types of cryptography

So Atul decided to encrypt the message in order to prevent eavesdropping. This essentially means adding a code to the message so that only those with access to the decryption code can access the original message. So you decided to encrypt the message in order to prevent eavesdropping. However, Atul did not have the opportunity to share the decision code with Vikram beforehand. So, what happens next? How will he send the message without jeopardizing the information? How will he deal with this issue? This is one of the many issues public-key encryption schemes like RSA address.

Once we have understood the importance of public-key encryption schemes like RSA, let’s go over the RSA algorithm’s private and public key math.

It is possible to find three extremely large positive integers, e, d, and n. As a result, modular exponentiation for integers m(0 = m n) is as follows:

Even if e and n are known, it’s extremely hard to find d.

Here, m stands for the original message, and C stands for cipher. 

Did the maths get a bit overwhelming? Don’t worry; you’ll understand it well in the later section of the article.

How does the RSA algorithm work?

RSA algorithm comprises four stages, and those four stages are:

• Key generation (1st stage): To generate a private key (to keep) and a public key (to share).
• Key distribution (2nd stage): Flood the network with the public key.
• Encryption (3rd stage): The sender encrypts the message using the receiver’s public key.
• Decryption (4th stage): The message is decrypted by the receiver using its private key.

The working of the RSA algorithm can be explained better with the help of an example stated in the next section of the blog.

Example of RSA algorithm

Here is an example of an RSA algorithm:

Suppose that Atul wants to send his bank details to Vikram. So, is there any way to send the bank details on the same public unencrypted network ensuring only Vikram can read it?

For Vikram to receive Atul’s bank details, Atul needs Vikram’s Public key. Using this, he can encrypt his message and send it. Vikram, who carries his private key, can decrypt the message sent by Atul. It’s a one-way process of sending messages to the intended recipient.

Here,

• M denotes an original message
• E denotes encryption function
• k denotes Vikram’s public key
• M’ denotes an encrypted message
• k’ denotes Vikram’s private key
• D denotes the decryption function

How to generate RSA key?

Here are the steps to generate RSA keys

• STEP 1: Choose two distinct prime integers, p, and q. Note: p and q should be chosen randomly. 
• STEP 2: Calculate n = p*q. Here, ‘n’ is the length of the key.
• STEP 3: Calculate f(n) = (p-1) (q-1) {Euler’s Totient function}
• STEP 4: Choose an integer ‘e’ such that 1 < e < (n) and GCD (e, f(n)) = 1 where ‘e’ and ‘f(n)’ are co-prime (means a pair of number that don’t have any common factor other than 1). Also, GCD is the greatest common factor.

Determine

• Here, ‘d’ is the modular multiplicative inverse of e (mod f(n)). [Note: (d*e) (mod f(n)) = 1]

Let’s follow the process using an example

This example shows how we can encrypt plaintext letter ‘H’ where H=2, using the RSA public-key encryption algorithm.

STEP 1: Create a Public Key

Following the steps:

1. Selecting two prime numbers, p, and q. Let’s say p = 3 and q = 11.
2. Calculate n = pq. So, n = 33. As, 3*11 = 33 = n.
3. Calculate f(n) = (p-1) (q-1). Here, f(n) = 20. As, f(n) = (p-1) (q-1) = (2)*(10) = 20
4. Choosing e=7. Such that 1 < e < f(n) and GCD(e, f(n)) = 1.

Hence, Public Key is (e, n) = (7, 33)

STEP 2: Create a Private Key

Using, (d*e) (mod f(n))=1. 

One Solution can be d=3. Such that, (3*7) % 20 = 1.

Hence, Private Key is (d, n) = (3, 33)

STEP 3: Encryption and Decryption of letter H

Let’s encrypt the ‘H’. where H = 2. 

Encryption of H:

 C=(2^7)% 33 = 29 => C = 29

The encryption of the letter H is 29.

Decryption of H: 

m=(29^3)% 33 = 2 => H = 2

The decryption of the letter H is 2.

We encrypted and decrypted the letter H. 

Note: The above example is a much simpler version of math than actual RSA cryptographic math with greater numbers. 

Above all, the robustness and encryption depend on the key size. In short, the longer the key size, the stronger the encryption. RSA public keys generally create outputs of 1024 and 2048 bits.

Numerical on RSA algorithm

Ques 1: In an RSA cryptosystem, Atul uses two prime numbers, p=7 and q=17, to generate his public and private keys. Suppose the public key is 11. Find the private key of Atul.

Ans: p=2, q=17, e=11

In RSA Cryptosystem, 

For Public Key: GCD (e, f(n)) = 1 

For Private Key: (d*e) (mod f(n)) = 1

f(n) = (p-1) (q-1) = 6*16 = 96

Such that, 1 < e; d < f(n). Therefore, the private key is (11*d) (mod f(n))=1

d=35. Hence, the private key of Atul = 35

Conclusion

The preceding article covered the RSA algorithm in great detail, focusing on topics such as What it is? How does it function? Examples include the generation of RSA keys, among other things. I hope you enjoyed the article!