RSA Algorithm
Here 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 |
