RSA public/private key encryption explained

In this blog post I'll show you how to calculate a simple RSA private-/public-key pair.

First of all you need to know that each key (the public-key and the private-key) consists of 2 parts. The first part is different in each key, the second is equal in both. So let's start calculating!

Warning: The encryption in this tutorial has a very low security level, because of the low values of p and q! To improve the security level choose higher primes.

Think of 2 prime numbers.

In real openssl, these prime numbers are very large and have a similar bit-size. So that we have no problem doing the calculations I'll choose 2 numbers that are quite small:
```
p = 3, q = 11
      
```
Calculate the modulus for the public/private key.

This is the number that is the same in both keys, let's call it n. It is used as the modulus in en- and decryption. You calculate it by doing:
```
n = 3*11
```
Calculate the totient of n.

Calculating the totient is easy. You could use a table and look up the value, but the calculation is just as easy and faster. Just do:
```
totient(n) = (p - 1) * (q - 1)
```
In our case we do:
```
totient(33) = (3 - 1) * (11 - 1)
```
This equals 20.
So far we have:
```
p = 3
q = 11
n = 33
totient(n) = 20
```
Choose a number for e

This number is is a bit harder than the others. It has to be between 1 and n, also coprime to n.

This basically means that the greatest common divisor of both numbers is 1. If you choose a prime number for e all you need to do now is check that e isn't a divisor of n. I'll choose the number:
```
e = 17
```
Calculating the modular multiplicative inverse of e * (mod totient(n))

Now at first this sounds a bit overwhelming, I struggled a bit to find out what it means. Expressed in an easy way you could say: What is the solution to the equation:
```
(e * x - 1) mod (totient(n)) = 0
```
It would take quite long to work it out by hand so I wrote a small Javascript function that does the work for me:
```
function doLoop(a, b) {
  for(i=1; i < window.Infinity; i++){
    x = (a * i -1) % b;
    if( x === 0 ){
      console.log(i)
      break;
    }
  }
}
```
The function takes 2 arguments, one is e the other is the totient(n). Depending on your processor and the size of the numbers you choose it can take longer or shorter to run.

In our case the function will log the value 13, which I'll call d. Now you have all the values needed for public-/private-key encryption and decryption.
Putting it all together

All the values up to now:
```
p = 3
q = 11
n = 33
totient(n) = 20
e = 17
d = 13
```
Your public-key is now: e = 17, n = 33

Your private-key is now: d = 13, n = 33

With this private and public-key you can now encrypt data by doing this:

We'll encrypt the value:
```
m = 9
```
To encrypt with the public key, you take m to the power of e (in the public-key) mod n
```
m ^ e mod n
```
```
9 ^ 17 mod 33 = 15
```
Our encrypted value is:
```
c = 15
```
This can only be decrypted with the private-key.

To decrypt it, you take c to the power of d (in the private-key) mod n
```
c ^ d mod n
```
```
15 ^ 13 mod 33 = 9
```
Now we have our original value!

December 10, 2011
Joseph Adams