What is the RSA algorithm with example

Hello everyone 🙂 Lucifer is here to explain to you guys what is RSA algorithm and how it works. Today in this article we are going to understand the working of the RSA algorithm with some examples that what is going over there.

After reading this article you’ll be able to know the working of RSA and be able to do mathematical calculations of the RSA algorithm. RSA is a Block cipher.

RSA (Rivest, Shamir, Adleman) algorithm was first described in 1977. It is an asymmetric cryptography algorithm with private and public keys in it. The public key is used for encryption and the private key is used for decryption.

// 01 Steps to calculate RSA

1. Key Generation

1. Select two prime numbers p and q respectively
2. Calculate n=p*q
3. calculate Φ(n)=(p-1)*(q-1)
   • Euler’s Totient Function
4. Exponential GCD [Φ(n), e] = 1
   • Condition = 1<e<Φ(n)
   • GCD = Greatest Common Division
5. Calculate [de mod Φ(n) = 1]
6. Public key = [e, n]
7. Private key = [d, n]

2. Encryption

• c = m^e mod n
  • [m = plaintext]
  • [m < n]
  • [c = ciphertext]
  • [m will be no. of words in your message]

3. Decryption

• m = c^d mod n

// 02 Example -1 RSA algorithm

Let's understand with an example

Assume p = 3, q = 11
n = 3x11 = 33                                        [i.e. n = pxq]
Φ(n) =  2x10 = 20                                 [i.e Φ(n) = (p-1)(q-1)]

So, let's take
e = 7 [1<7<20 and gcd ((7,20) = 1) ]

Now,

de mod Φ(n) = 1
7xd mod Φ(n) = 1
7xd mod 20 = 1        [ *** d = 3]

Since e = 7, d = 3

Public key = [e, n] = [7, 33]
Private key = [d, n] = [3, 33]

Let's take message = 31

Encryption

c = me mod n
c = 317 mod 33
c = 27512614111 mod 33
c = 4

Decryption

m = cd mod n 
m = 43 mod 33
m = 64 mod 33
m = 31

Note:-

[e, n] is a public key used in encryption, and [d, n] is a private key used for decryption.

// 03 Example – 2 RSA algorithm

Let's see another example

Assume p = 61, q = 53
n = 61x53 = 3233                                        [i.e. n = pxq]
Φ(n) = 60x52 = 3120                                 [i.e Φ(n) = (p-1)(q-1)]

So, let's take
e = 17 [1<17<3120 and gcd ((17, 3120) = 1) ]

Now,

de mod Φ(n) = 1
17xd mod Φ(n) = 1
17xd mod 3120 = 1        [ *** d = 2753]

Since e = 17, d = 2753

Public key = [e, n] = [17, 3233]
Private key = [d, n] = [2753, 3233]

Let's take message = 123

Encryption

c = me mod n
c = 12317 mod 3233
c = 855

Decryption

m = cd mod n 
m = 8552753 mod 3233
m = 123

// 04 Usage of the RSA algorithm

1. This uses in banks for securing customer data and transaction details
2. It uses in telecommunication for encrypting call data
3. Uses in e-commerce for securing users’ identity for transactions