What is RSA Algorithm in Cryptography?

By
Alimam Miya
-

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 in Cryptography?

The RSA algorithm in Cryptography 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 in Cryptography 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 in Cryptography work?

RSA algorithm in Cryptography 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 in Cryptography 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 a better understanding, let’s see one example:

  1. Let the two prime numbers be 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. The public key is (n, e) = (77, 7).
    The private key is (n, d) = (77, 43).

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

Advantages of RSA algorithm in Cryptography

  • 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.

Disadvantages of RSA algorithm in Cryptography

  • With the RSA algorithm in Cryptography, 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 in Cryptography 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 in Cryptography 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 in Cryptography. For more exciting & informative modules like this, you read our other tutorials and blogs on our website.