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
So far we have:20
.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
andn
, also coprime ton
.This basically means that the greatest common divisor of both numbers is
1
. If you choose a prime number fore
all you need to do now is check thate
isn't a divisor ofn
. 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:
It would take quite long to work it out by hand so I wrote a small Javascript function that does the work for me:(e * x - 1) mod (totient(n)) = 0
function doLoop(e, totient) { var i = 1, x; while (true) { x = (e * i - 1) % totient; if (x === 0) { console.log(i); break; } } }
The function takes 2 arguments, one is
e
the other is thetotient(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 calld
. 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!