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:
- Encrypting with the public key, and then decrypting with the private key.
- 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:
- We choose two distinct prime numbers, such asp=61 and q=53
- Compute n = pq giving n=61.53=3233
- Compute the totient of the product as ϕ(n) = lcm(p − 1, q − 1) giving ϕ(3233)= lcm(60,52)=780
- 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
- 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) = m17 mod 3233
The private key is (n = 3233, d = 413). For an encrypted ciphertext c, the decryption function is
m(c) = c413 mod 3233
For instance, in order to encrypt m = 65, we calculate
c = 6517 mod 3233 =2790
To decrypt c = 2790, we calculate
m = 2790413 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:
Sources: https://en.wikipedia.org/wiki/RSA_(cryptosystem)