RSA algorithm

• RSA alogorithm is the most popular asymmetric key cryptographic algorithm

• It is based on the mathematical fact that it is easy to find and 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 (made up of 100 or more digits)

• The real challenge in the case of RSA is the selection and generation of the public and private keys

• Now let us know how public and private keys are generated and using them how we can perform encryption and decryption in RSA

Algorithm

$\hspace{1.5cm}$1. Choose two large prime numbers p and q

$\hspace{1.5cm}$2. Calculate n = p * q

$\hspace{1.5cm}$3. Select the public key (ie the encryption key) e such that it is not a factor of (p-1) (q-1).

$\hspace{1.5cm}$ Say $\phi$(n) = (p-1)(q-1)

$\hspace{1.5cm}$4. Select the private key (ie the decryption key) d such that the following equation is true:

$\hspace{1.5cm}$(d * e) mod(p-1)(q-1) = 1

$\hspace{1.5cm}$5. For encryption, calculate the ciphertext C.T from the plaintext P.T as follows

$\hspace{1.5cm}$ CT =$ PT^{(e)}$ mod n

$\hspace{1.5cm}$6. Send CT as the ciphertext to the receiver

$\hspace{1.5cm}$7. For decryption, calculate the plaintext PT from the ciphertext CT as follows

$\hspace{1.5cm}$ PT = $CT^{(d)}$ mod n

$\hspace{1.5cm}$Example:

$\hspace{1.5cm}$1. Choose two large prime number p and q, p =7 and q = 17

$\hspace{1.5cm}$2. n = p*q ie 7X17 = 119

$\hspace{1.5cm}$3. Select public key ‘e’ such that it is not a factor of (p-1)*(q-1)

$\hspace{2cm}$. $\phi$(n) = (p-1)(q-1)

$\hspace{2cm}$ $\phi$(n) = 6*16 =96

Thus encryption should not be a factor of 96, factors of 96 are 2 and 3. Thus we have to choose e such that none of the factors of e are 2 and 3. So let us choose e as 5 (it could be any other number than its factor of 2 and 3)

$\hspace{1.5cm}$4. Select private key ‘d’ such that (de) mod (p-1)(q-1) = 1

$\hspace{1.5cm}$Substitute e, p and in the following eq

$\hspace{1.5cm}$(d*5) mod (7-1) (17-1) =1

$\hspace{1.5cm}$(d*5) mod (6) (16) =1

$\hspace{1.5cm}$(d*5) mod (96) =1

$\hspace{1.5cm}$Let us take d= 77

$\hspace{1.5cm}$(77*5) mod (96) =1 for d = 77

$\hspace{1.5cm}$5. For encryption, calculate the ciphertext CT from the P.T as

$\hspace{1.5cm}$CT = $PT^{(e)}$ mod n

$\hspace{1.5cm}$Let plaint text P.T be 10

$\hspace{1.5cm}$CT = $10^{5}$ mod 119 = 40

$\hspace{1.5cm}$6. Send CT as ciphertext to the receiver. Send 40 as ciphertext to the receiver.

$\hspace{1.5cm}$7. For decryption, calculate the plain text PT from the CT as

$\hspace{1.5cm}PT = CT^{(d)} mod n $

$\hspace{1.5cm}$PT = $40^{77}$ mod 119 = 10, which was the original plaintext in step 5

Eg:

Consider, A is the sender and B is the receiver.

Use encoding scheme of encoding alphabets as A = 1, B=2, …..Z= 26.

Let us assume we want to encrypt a single alphabet F using this scheme and with B’s public key as 77 (known to A and B) and B’s private key(known only to B)

Now A wants send a single character ‘F’ to the receiver B.

$\hspace{1.5cm}$1. Using alphabetic encoding scheme F= 6

$\hspace{1.5cm}2. CT = PT^{(d)} mod n$

$\hspace{2.3cm}= F^{(E)} mod n$

$\hspace{2.3cm}= 6^5 mod 119 = 41$

This is the encrypted information to the sent across the network.

At the receiver end, the number 41 is decrypted.

1. $PT = CT^{(D)}$ mod n
2. $PT = 41^{77}$ mod 119 = 6
3. Decode 6 back to F from our alphabet numbering scheme thus original plaintext obtained.