Thursday 24th January 2013

by Mr Me

Here is RSA algorithm explained in a simple way with example.

Algorithm:

  1. Find two random distinct prime numbers (usually very big) , call them P and Q
  2. Find number N = P x Q   (this N is called modulus, used in both private and public key pair)
  3. Find number Z = (P-1) x (Q-1)        (Z is called Euler’s totient function)
  4. 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 ]
  5. 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

  1. Find two distinctive prime number P and Q.P = 11 and Q = 13
  2. Find N = P x QN = 11 x 13 = 143
  3. Find Z = (P-1) x (Q-1)Z = 10 X 12  = 120
  4. Find E as co-prime of ZFind any co-prime of 120, E = 101   , because GCD(120, 101) = 1
  5. 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:

Ruby
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

 

· · · ◊ ◊ ◊ · · ·

One Response to “RSA Algorithm”

  1. Ranjithkumar says:

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

· · · ◊ ◊ ◊ · · ·

Leave a Reply

Need your support
More in php (1 of 108 articles)


QPDF is a command line tool for creating / editing and managing PDF. This is a powerful tool manages ...