RSA Algorithm
RSA Algorithm for Key-pair generation:
1) Choose 2 distinct prime numbers ‘p’ & ‘q’. Preferably large , random & of same bit size.2) Compute modulus “n = p.q”.
3) Compute F(n) = (p – 1) (q – 1) where is F(n) is Totient function.
4) Choose an integer ‘e’ such that 1 < e < F(n) and e and F(n) are co-prime. ‘e’ is the Public key exponent.
5) Determine d multiply e = 1 mod F(n) ,the Private key exponent.
Public Key is modulus ‘n’ & exponent ‘e’ = (n, e).
Private Key is modulus ‘n’ & exponent ‘d’ = (n, d), the secret.
Encryption (Message ‘m’)
m power(e) (mod n) = c, the cipher text.Decryption (Cipher text ‘c’)
c power(d) (mod n) = m, the original message.Example:
RSA Algorithm for Key-pair generation:
1) Choose 2 distinct prime numbers ‘7’ & ‘13’. Preferably large , random & of same bit size.
2) Compute modulus “n = p . q = 91”.
3) Compute F(n) = (p – 1) (q – 1) = 72 where is F(n) is Totient function.
4) Choose an integer ‘e’ such that 1 < e < F(n) and e and F(n) are co-prime. ‘e’ is the Public key exponent.
e = {5,7, 11, 13, 17,...}. Let it be 5.
5) Determine d multiply e = 1 mod(F(n))
5 multiple d = 1 mod (72)
5d = 1 (mod 72) equals a set of candidates { …,29, 101, 173, …}. Chose d = 29.
Public Key is modulus ‘n=91’ & exponent ‘e=5’ = (91, 5). [ Note: e.d = 1 mod (p-1 x q -1) ]
Private Key is modulus ‘n=91’ & exponent ‘d=29’ = (91, 29), the secret.
“Note: Factoring ‘n’ to find ‘p, ‘q’, & then ‘d’ is the hardest part(as of today)
and strength of RSA (so far)”
