**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^{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^{37} mod 143 = 13.

**Solution of exercise (Given in video)**

**To learn more about RSA Algorithm, Click here**

**Watch more videos click here.**

Nice info sir

ReplyDeleteThank you please share with others...

DeleteThank you sir

ReplyDeleteWelcome Please share with others....

DeleteError in exercise 4 part 3:

ReplyDelete(p-1)(q-1) = (3-1)(11-1)= 2*10 = 20

ohhh...Thank you for suggestion...It was my mistake.... Now check this...It is changed..

Delete