## Thursday 24th January 2013

by Mr MeHere is RSA algorithm explained in a simple way with example.

Algorithm:

- Find two random distinct prime numbers (usually very big) , call them P and Q
- Find number N = P x Q (this N is called modulus, used in both private and public key pair)
- Find number Z = (P-1) x (Q-1) (Z is called Euler’s totient function)
- Chose an integer E, which is co-prime to Z. (Co-prime means GCD of E and Z should be 1, means, E and Z should only be divisible by 1) [This E will be our encryption key ]
- Find integer D, such a way that, ( D x E ) mod N should be 1 (D ≡ E ** -1 (mod Z) )

This D is called multiplicative inverse of E. This D is your decrypt key (** indicates power to or raise to, eg: 2 ** 3 = 2 x 2 x 2 = 8 )

So, here we get E and D can be used as encryption and decryption key

Encryption key pair (E, N)

Decryption key pair ( D, N)

Here N is the modulus common for both keys.

### Encryption

To encrypt Data

(Data ** E ) mod N => C, the encrypted Cypher (Here ** is power to, or raise to )

### Decryption

To decrypt the Cypher C

(C ** D) mod N => Data

Real life Example

- Find two distinctive prime number P and Q.P =
**11**and Q =**13** - Find N = P x QN = 11 x 13 =
**143** - Find Z = (P-1) x (Q-1)Z = 10 X 12 =
**120** - Find E as co-prime of ZFind any co-prime of 120, E =
**101**, because GCD(120, 101) = 1 - Find D, such that E x D mod N should be 1(D x 101 ) mod 120 => 1D =
**221**

We god E, D and N, so the encryption key pair is (101, 143) [E, N] and the decrypting key pair is ( 221,143) [D, N]

**Lets try Encryption**,

eg: We need to encryption Data = 2

Encrypted Data Cypher C = Data ** E mod N

C = 2 ** 101 mod 143

C = 2535301200456458802993406410752 mod 143 = 123

Encrypted Data C = **123**

**Lets try Decryption**

Data decrypted = C ** D mod N

Data decrypted = 123 ** 221 mod 143

Data decrypted = **2 **(try calculating yourself, as 123 ** 221 is too big to print here)

A sample ruby code finding these numbers is below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#to find gcd
def gcd(a,b)
if b == 0
return a
else
return gcd(b, a%b)
end
end
#to find co-prime
def find_coprime(a,z)
if gcd(a,z) == 1
return z
end
find_coprime(a, z + 1)
end
#to find decrypt key D
while ((d*e) % z != 1) or (d == e) do
d= d+1
print d.to_s + "\n"
end |

can u send a “Jmail++ , My Final Year Project” Source Code to ID:mrkodai.tn@gmail.com