RSA (cryptosystem) – Part 3 (Encryption and Decryption)

This is the process of transforming a plaintext message into ciphertext, or vice-versa. The RSA function, for message m and key k is evaluated as follows:

F(m,k)=mkmodn

There are two cases:

1. Encrypting with the public key, and then decrypting with the private key.
2. Encrypting with the private key, and then decrypting with the public key.

The two cases above are mirrors. I will explain the first case, the second follows from the first

Encryption: F(m,e)=memodn=c, where m is the message, e is the public key and c is the cipher.

Decryption: F(c,d)=cdmodn=m, where m is the message, d is the private key and c is the cipher.

Example:

Following the example from the previous post:

1. We choose two distinct prime numbers, such asp=61 and  q=53
   
2. Compute n = pq giving n=61.53=3233
   
3. Compute the totient of the product as ϕ(n) = lcm(p − 1, q − 1) giving ϕ(3233)= lcm(60,52)=780
   
4. Choose any number 1 < e < 780 that is coprime to 780. Choosing a prime number for e leaves us only to check that e is not a divisor of 780.Let e=17
   
5. Compute d, the modular multiplicative inverse of e (mod ϕ(n)) yielding,d=413
   

The public key is (n = 3233, e = 17). For a padded plaintext message m, the encryption function is

c(m) = m¹⁷ mod 3233

The private key is (n = 3233, d = 413). For an encrypted ciphertext c, the decryption function is

m(c) = c⁴¹³ mod 3233

For instance, in order to encrypt m = 65, we calculate

c = 65¹⁷ mod 3233 =2790

To decrypt c = 2790, we calculate

m = 2790⁴¹³ mod 3233 = 65

Please note the whole security of RSA system depends on the selection of p and q for the algorithm. A real world example for p and q could be:

p
12131072439211271897323671531612440428472427633701410925634549312301964373042085619324197365322416866541017057361365214171711713797974299334871062829803541

q
12027524255478748885956220793734512128733387803682075433653899983955179850988797899869146900809131611153346817050832096022160146366346391812470987105415233

and as per the algorithm, you can calculate other parameters.

RSA is very helpful in building secure products and I hope you understood the basic concept of RSA with these posts:

RSA – Part 1

RSA – Part 2

RSA – Part 3

Sources: https://en.wikipedia.org/wiki/RSA_(cryptosystem)

Advertisements

• RSA