What is RSA Algorithm?

Hello there, everyone. We’re glad you’re back. For this module, I’ll explain what is RSA algorithm in cryptography is all about. You’ll learn about the RSA algorithm and how it works after reading this module. So, without further delay, let’s know about the RSA algorithm.

What is RSA algorithm?

What is RSA algorithm?

The RSA algorithm was developed by 3 founders: Ron Rivest, Adi Shamir, and Leonard Adleman in 1978, and hence, this algorithm was named RSA (Rivest, Shamir, and Adleman) algorithm.

The RSA algorithm is a public key cryptography algorithm used for converting plain text into ciphertext. It is also known as asymmetric-key cryptography because two different keys i.e., a public key and a private key are used for encrypting and decrypting the message or data. As the name implies, the Public Key is made available to anyone, while the Private Key remains secret or private i.e., not shared with anyone.

The public key is used by the sender to encrypt the message or plain text and a private key is used by the receiver to decrypt the encrypted message or ciphertext.

How does the RSA algorithm work?

RSA algorithm works in 3 steps:

  1. Generation of public and private keys.
  2. Encryption of message by the sender using the public key.
  3. The decryption of the message by the receiver using the private key.

Now, let’s go through the process of the RSA algorithm step by step.

Generation of public and private keys

  1. Choose a and b as two large prime numbers, where a cannot be equal to b.
  2. Compute, n= a * b, where n is referred to as the modulus for encryption and decryption.
  3. Compute the totient function, ϕ(n) = (a – 1) * (b – 1).
  4. Select e such that 1 < e < ϕ(n) is relatively prime to ϕ(n), i.e., gcd(e, ϕ(n)) = 1. In other words, e and (n) don’t have any factors except for one.
  5. Compute, d in such a way that e.d = 1 mod ϕ(n) or d=e-1 mod ϕ(n). You can find out d by using the Extended Euclidean Algorithm.
    Or
    d can be calculated using the given formula below:
    d = (ϕ(n) * k + 1) / e, for some integer k.
  6. Finding the public key
    The public key consists of two numbers n & e, i.e., (n, e).
  7. Finding a Private key
    The private key consists of two numbers n & d, i.e., (n, d).

Encryption of message by the sender using public key

Using the public key, the ciphertext C is calculated from the plaintext P, which is a number:
C = Pe mod n

The decryption of message by the receiver using the private key

Using the private key, the plaintext P is calculated from the ciphertext C, which is a number:
P = Cd mod n

For better understanding, let’s see one example:

  1. Let the two prime numbers are a=11 and b=7.
  2. Compute, n = a * b = 11 * 7 = 77.
  3. Compute: ϕ(n) = (a – 1) * (b – 1) = (11 – 1) * (7 – 1) = 10 * 6 = 60.
  4. Selecting a number e such that gcd(e, ϕ(n))=1 and 1 < e < ϕ(n).
    Let e = 7.
    Gcd(7,60)=1
  5. Calculating d.
    ed = 1 mod ϕ(n)
    Or
    d = (ϕ(n) * k + 1) / e
    d = (60 * k + 1) / 7
    When k=1, d = (60 * 1 + 1) / 7 = 61/7 = 8.17.
    When k=2, d = (60 * 2 + 1) / 7 = 121/7 = 17.28.
    When k=3, d = (60 * 3 + 1) / 7 = 181/7 = 25.86.
    When k=4, d = (60 * 4 + 1) / 7 = 241/7 = 34.43.
    When k=5, d = (60 * 5 + 1) / 7 = 301/7 = 43.
    Therefore, d = 43.
  6. Public key is (n, e) = (77, 7).
    Private key is (n, d) = (77, 43).

Now, let’s see some of the advantages and disadvantages of the RSA algorithm.

What are the advantages of the RSA (Rivest, Shamir, and Adleman) algorithm?

  • In comparison to the DSA algorithm, the RSA one encrypts data more quickly.
  • If you encrypt a message with the receiver’s public key, you ensure the message’s confidentiality and authenticity since no one else will be able to decrypt it without knowing the receiver’s private key, which is only known to the receiver of the message or data.

What are the disadvantages of the RSA (Rivest, Shamir, and Adleman) algorithm?

  • With the RSA algorithm, there’s just too much computation going on.
  • The encryption and decryption processes take a long time, and generating keys is cumbersome.

Let’s see which layer model RSA algorithm works.

In which layer does the RSA algorithm work?

In the OSI (Open Systems Interconnection) model, the RSA algorithm works on the presentation layer.

In the TCP/IP (Transmission Control Protocol / Internet Protocol) model, RSA algorithms work on the application layer because, in the TCP/IP model, the application layer is a combination of an application layer, presentation layer, and session layer.

I hope this module will be beneficial for you and you have now got some basic idea about the RSA algorithm. For more exciting & informative modules like this, you read our other tutorials and blogs on our website.