Table of contents
1.
Introduction
2.
How it works
2.1.
Generation of keys
3.
Frequently Asked Questions
3.1.
Which algorithm is used in RSA?
3.2.
How strong is RSA?
3.3.
What is RSA used for?
4.
Conclusion
Last Updated: Mar 27, 2024

RSA Algorithm

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Computer Networks

Introduction

The RSA algorithm is an asymmetric algorithm widely used in many products and services. Asymmetric encryption uses a key pair to encrypt and decrypt data. A private and public key is created, with the public key being accessible to anyone and the private key is a secret known to the key pair creator. In RSA, either the private or public key can encrypt the data, while other keys decrypt it. It is one of the reasons RSA is the most used asymmetric encryption algorithm.

Recommended Topic, Basic Networking Commands

How it works

The RSA algorithm ensures that the keys in the above illustration are as secure as possible. The following steps highlight how it works:

RSA Algorithm

Generation of keys

  1. We will take two large prime numbers, x, and y. The prime numbers need to be large so that they will be difficult for someone to figure out.
  2. Calculate n = x*y
  3. Calculate the totient function; ϕ(n)=(x−1)(y−1).
  4. We also need a small exponent to say e. e must be an integer, but it should not be a factor of n. 1 < e < ϕ(n).
  5. The public key consists of n and e.
  6. Now calculate Private Key, d, d = (k*Φ(n) + 1) / e for some integer k.
  7. A plain message m is encrypted using public keys e and n. To convert the plaintext into ciphertext, we use the following formula to get ciphertext C.
    C = me mod n
  8. A ciphertext c is decrypted using private key d and n. We use the following formula to calculate plain text m from the ciphertext c.
    m = cd mod n

This example shows how we can encrypt plaintext 9 using the RSA public-key encryption algorithm. This example uses prime numbers 7 and 11 to generate the public and private keys.

In this example, we will encrypt plaintext 9 using the RSA algorithm. We will take prime numbers 7 and 11 for the public and private keys.

Explanation:

Step 1: Take two large prime numbers, x and y.

x = 7

y = 11

Step 2: Multiply both of them to find n = x * y , 

n = x * y

n = 7 * 11

n = 77

Step 3: Pick a number e less than n, such that n is relatively prime to (x - 1) * (y -1). It means that e and (x - 1) * (y- 1) have no common factor other than 1. Choose e, where 1<e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1.

Now, we calculate

φ (n) = (x - 1) * (y-1)

φ (n) = (7 - 1) * (11 - 1)

φ (n) = 6 * 10

φ (n) = 60

Let us now choose e=7, relative prime of 60.

The value of public key is (e, n) = (7, 77)

Step 4: Any plaintext message m is encrypted using public keys e and n. We use the following formula to convert ciphertext from plain text to get ciphertext C.

To get ciphertext from the plain text, we use the following formula.

C = me mod n

C = 97 mod 77

C = 37

Step 5:The private key is (d, n). To find the private key, we use the following formula to find d:

De mod {(x - 1) * (y - 1)} = 1

7d mod 60 = 1, which gives d = 43

So, the private key is (d, n) = (43, 77)

Step 6: The ciphertext message c is decrypted using the private key (d, n). We use the following formula to find plain text m from the ciphertext ca.

m = cd mod n

m = 3743 mod 77

m = 9

In the above example, Plain text is 9, and the ciphertext is 37

You can also read about the Layered Architecture in Computer Network Subnetting in Computer Networks

Frequently Asked Questions

Which algorithm is used in RSA?

RSA algorithm is an asymmetric cryptography algorithm. Asymmetric implies that it works on two different keys, i.e., Public Key and Private Key. The public key is shared with everybody, but the private key is secret and should not be shared with anyone.

How strong is RSA?

All in all, Only 12,934 keys have been broken till now. In other words, if used carelessly, RSA encryption provides less than 99.8% security. That doesn't sound very important, and it's about two in every 1,000.

What is RSA used for?

RSA encryption is a type of public-key cryptography widely used for data encryption of e-mail and other digital transactions over the Internet.

Conclusion

In this article, we learned about the RSA algorithmis an asymmetric algorithm that uses public and private keys for encryption and decryption. The receiver's public key is used to encrypt the data and the receiver's private key to decrypt the data. We learned about the need and working of ARP. At the end of this blog, we also find out the outcome of the RSA Algorithm.

Recommended Articles 

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. 

Happy Coding!

Live masterclass