Understanding RSA

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)”

Encryption (Message ‘10’)

10 power(5) (mod 91) = 82, the cipher text.

Decryption (Cipher text ‘82’)

82 power(29) (mod 91) = 10, the cipher text.