Understanding RSA Algorithm
RSA Algorithm
RSA algorithm is an asymmetric key system.
Means system will generate a key pair :
(Public key , Private Key )
We will later in this post would get to know how this pair come out .
For now suppose we have a message
SecretMessage which we want to encrypt . Then following happens in the RSA system.
1.The system randomly picks two prime numbers P & Q respectevely suppose they are 2 & 7 .
So We have P = 2
Q = 7
2. Multiply both to obtain the Modulus i.e
N = 14.
Now in order to generate public key.
System will generate numbers from 1 to 14 ( modulus )
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Remove the common factors with 14 from the above list of numbers.
1 3 5 9 11 13
Find the length of the above.
L = 6
There is a very simple formula to obtain the length given the modulas.
L = ( P-1 ) × ( Q-1 )
L = 6 .
Now from the list 1 3 5 9 11 13
Find out the co prime number with 6( Length ) and 14 ( the modulas )
That number will be unique. And this time it is only 5 .
So 5 is the public key .
Now encrypting it using the public key as follow.
Message is in strings so we need something to encode it in number so that we can perform arithmetic operations on it .
So suppose its get converted to 2 by some encoding system. In production we use lot of different techniques to encode the message and padding is also used.
So we have ,
2 ^5 mod (14) = 4
4 is the encrypted message.
For the private key we will use the RSA equation.
(D*E) mod ( L ) = 1
Where D is the private key
E is the public key
L is the Length of the common factors.
So from basic mathematics we can observe that D must be the common factor of E. In this case it is common factor to 5.
lets generate 1 to 50 and test one by one using the above formula.
We get D = 11 satisfying the above equation.
So this will be our private key.
Lets decrypt the message now by using private key so obtained.
4^11 mod(6) = 2 ( the original encoded message ) .
We have 5, 11 as public and private key respectevely.