What is RSA algorithm | RSA Algorithm explain with example | RSA algorithm example | RSA algorithm steps | how to find private key in rsa example

RSA Algorithm

Introduction

Ron Rivest, Adi Shamir and Len Adleman have developed this algorithm (Rivest-Shamir-Adleman). It is a block cipher which converts plain text into cipher text and vice versa at receiver side.

RSA Algorithm Steps

Step-1: Select two prime numbers p and q where p ≠ q.

Step-2: Calculate n = p * q.

Step-3: Calculate Ф(n) = (p-1) * (q-1).

Step-4: Select e such that, e is relatively prime to Ф(n), i.e. (e, Ф(n)) = 1 and 1 < e < Ф(n)

Step-5: Calculate d = e ^-1 mod Ф(n) or ed = 1 mod Ф(n).

Step-6: Public key = {e, n}, private key = {d, n}.

Step-7: Find out cipher text using the formula,

C = P^e mod n where, P < n where C = Cipher text, P = Plain text, e = Encryption key and n=block size.

Step-8: P = C^d mod n. Plain text P can be obtain using the given formula. where, d = decryption key

RSA algorithm explanation with example step by step

Step – 1: Select two prime numbers p and q where p ≠ q.

Example, Two prime numbers p = 13, q = 11.

Step – 2: Calculate n = p * q.

Example, n = p * q = 13 * 11 = 143.

Step – 3: Calculate Ф(n) = (p-1) * (q-1).

Example, Ф(n) = (13 – 1) * (11 – 1) = 12 * 10 = 120.

Step – 4: Select e such that, e is relatively prime to Ф(n), i.e. (e, Ф(n)) = 1 and 1 < e < Ф(n).

Example, Select e = 13, gcd (13, 120) = 1.

 

Step – 5: Calculate d = e ^-1 mod Ф(n) or e * d = 1 mod Ф(n)

Example, Finding d: e * d mod Ф(n) = 1 

13 * d mod 120 = 1

(How to find:   d *e = 1 mod Ф(n)

d = ((Ф(n) * i) + 1) / e

d = (120 + 1) / 13 = 9.30 (∵ i = 1)

d = (240 + 1) / 13 = 18.53 (∵ i = 2)

d = (360 + 1) / 13 = 27.76 (∵ i = 3)

d = (480 + 1) / 13 = 37 (∵ i = 4))

 

Step – 6: Public key = {e, n}, private key = {d, n}.

Example, Public key = {13, 143} and private key = {37, 143}.

Step – 7: Find out cipher text using the formula, C = P^e mod n where, P < n.

Example, Plain text P = 13. (Where, P < n)

C = P^e mod n = 13¹³ mod 143 = 52.

 

Step – 8: P = C^d mod n. Plain text P can be obtain using the given formula.

Example, Cipher text C = 52

P = C^d mod n = 52³⁷ mod 143 = 13.

Solution of exercise (Given in video)

To learn more about RSA Algorithm, Click here

Watch more videos click here.