The RSA Algorithm:
It is an asymmetric key
cryptographic algorithm. It uses prime numbers to manipulate the cipher text.
It is based on a mathematical fact that it is easy to find multiply large prime
numbers together but it is extremely difficult to factor their product.
The
private and public keys in RSA are based on very large prime numbers.
Procedure for algorithm:
i.
Select two large prime numbers P and Q
ii.
Calculate
N = P x Q
iii.
Select the public key (i.e. Encryption key) E such
that it is not the factor of P-1 x Q-1.
iv.
Select the private key (i.e. Decryption key) D such
that the following equation is true –
(D x E) mod (P-1) x (Q-1) = 1
v.
For encryption calculate the cipher text CT from the
plain text PT as follows
CT = PTE mod
N
vi.
Send CT as the cipher text to the receiver.
vii.
For decryption calculate the plain text PT from the
cipher text CT as follows –
PT = CTD mod N
Example of
RSA:
i.
Select two large prime numbers as P=7 and Q=17
ii.
Calculate N = P x Q
N = 7 x 17
N = 119
iii.
Select the public key E such that it is not a factor
of P-1 x Q-1
P-1
= 6
Q-1
= 16
Factor
of 6 x 16 will be
2,
2, 2, 2, 2, 3
So
now we have to select encryption key in a manner that it can’t be a factor of 2
and 3 so we can select E=5.
iv.
Select private key D such that following equation is
true –
(D
x E) mod (P-1) x (Q-1) = 1
(77
x 5) mod 96=1 .............................eq. 1
D=77
For
only D = 77 eq. 1 will be true
v.
CT = PTE mod N
Let’s
assume we have plain text PT equals to 10 so CT will be –
CT
= 105 mod 119
CT
= 40
vi.
Send CT as the cipher text to the receiver.
vii.
Calculate the plain text PT as –
PT
= CTD mod 119
PT
= 4077 mod 119
PT = 10
I find this algorithm very confusing as I tried to understand it many times but failed. But to some extent this post helped me. The example explained helped me a lot. Thanks.
ReplyDeleteelectronic signature