• RSA is the most common public key algorithm named after its inventors Rivest, Shamir and Adleman.

• The RSA algorithm is based on the mathematical fact that it is easy to find and multiply large prime number together but it is extremely difficult to factor their product. The private and public keys in RSA are based on very large prime numbers.

  • Algorithm:

i. Choose two large prime numbers P and Q.

ii. Calculate $N = P x Q$

iii. Select the public key (encryption key) E such that it is relatively prime to the product $(P- l)(Q- 1)$.

iv. Select private key (decryption key) D such that the following equation is true:

$(D x E)mod(P-1) x (Q-1) = 1$

v. For encryption, calculate ciphertext C from plaintext M as follows:

$C= ME mod N$

vi. Send C as ciphertext to the receiver.

vii. For decryption calculate the plaintext M from ciphertext C as follows:

$M = CD mod N$

• Example:

i. To generate, Alice's key pair, select the two large primes $P = 7 and Q = 17$.

ii. Calculate modulus $N = P x Q = 119 and (p — l)(q — 1) = 20$

iii. Selecting the encryption key E:

$(7-1) x (17-1) = 6 x 16 = 96$. Factors of $96 are 2, 2, 2, 2, 2, 3$.

Choose E such that none of the factors of E is 2 and 3 hence E selected is $5 i.e E = 5$.

iv. Select Decryption Key $D: (D x E) mod (P-1) x (Q-1) =1$

$(D x 5) mod (7-1) x (17-1) = 1$

$(D x 5) mod (6) x (16) = 1$

Assume $D=77, (77 x 5) mod (96) = 385 mod 96$ which gives 1.

v. For encryption: $C = ME mod N$

Assume plaintext $M = 10, then C = 105 mod 119 = 40$

vi. Send ciphertext $C = 40$ to the receiver.

vii. For decryption: $M = CD mod N$

$M = 4077 mod 119 = 10$ which is original text.