Tuesday, February 21, 2012

Encrypt & decrypt with RSA algorithm

The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, the persons responsible for its creation. Lets see an example of how can we perform encryption and decryption with RSA.

Suppose we have,

p=2; q =11; e=7; and Message to be encrypted is M =5

To encrypt the given message with RSA algorithm,

Calculating Euler totient function φ = (p-1)(q-1) = 1 * 10 = 10

calculating n = (p. q) = (2. 11) = 22

Cipher Text c = m^e (mod n)
= 5^7 (mod 22)
= 3

Hence encryption of message 5 is done into cipher text =3
c is the cipher text

Decrypt(c) = c^d (mod n)

Here we have to find d such that ed-1 is divisible by φ
when d = 1 then ( ed-1 ) = 7*1 -1 = 6 not divisible by (φ = 10)
when d = 2 then ( ed-1 ) = 7*2 -1 = 13 not divisible by (φ = 10)
when d = 3 then ( ed-1 ) = 7*3 -1 = 20 divisible by (φ = 10)

Hence we take d =3
So, Decrypt(c) = c^d (mod n) = 3^3 (mod 22) = 27 (mod 22) gives original message 5

Hence decryption done.