Do You Know: What Is a RSA Algorithm?

Do You Know: What Is a RSA Algorithm?

7 mins read1K Views Comment
Anshuman
Anshuman Singh
Senior Executive - Content
Updated on Feb 19, 2024 16:25 IST

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. As a result, 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.

2022_08_MicrosoftTeams-image-44-1.jpg

So what is the RSA algorithm? Before answering this question, let’s go through the topics that we will be covering in this blog:

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.

2022_08_RSA1.jpg

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:

2022_03_image-60.jpg

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

2022_03_image-62.jpg

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.

2022_08_ATUl-and-vik.jpg

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

2022_03_image-63.jpg
  • 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:

2022_03_image-64.jpg

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

The encryption of the letter H is 29.

Decryption of H: 

2022_03_image-65.jpg

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!

FAQs

Is the RSA algorithm symmetric or asymmetric?

RSA is an asymmetric algorithm that encrypts with a publicly known key but decrypts with a different key known only to the intended recipient.

What are the potential threats to the RSA algorithm?

A factorization attack is one of the most common threats to the RSA algorithm. In this attack, the attacker impersonates the key owners and decrypts sensitive data using stolen cryptographic data to circumvent system security.

How secure is RSA?

The mathematical difficulty of factoring large integers underpins RSA security.

What problem does the RSA algorithm solve?

The RSA algorithm is built around the factoring problem. The practical difficulty of factoring the product of two large prime numbers underpins RSA's security.

What are the stages for RSA algorithm?

There are four stages for RSA algorithm, such as: Key generation (1st stage):u00a0To generate a private key (to keep) and a public key (to share). Key distribution (2nd stage):u00a0Flood the network with the public key. Encryption (3rd stage):u00a0The sender encrypts the message using the receiver's public key. Decryption (4th stage):u00a0The message is decrypted by the receiver using its private key.

What is the RSA key size?

On the public key data set (PKDS), the minimum size for clear RSA keys and secure RSA keys is 512 bits. On the token key data set (TKDS), the minimum size for secure RSA keys is 1024 bits, and the size must be a multiple of 256.

About the Author
author-image
Anshuman Singh
Senior Executive - Content

Anshuman Singh is an accomplished content writer with over three years of experience specializing in cybersecurity, cloud computing, networking, and software testing. Known for his clear, concise, and informative wr... Read Full Bio