RSA Encryption
I wanted to learn more about cryptography and it is easier to learn if I read about it, I do it by hand or write some code and I explain it to someone. That someone is you.
So I started with RSA which is a very common encryption. RSA stands for Rivest–Shamir–Adleman which are the 3 people who designed this public-key cryptosystem and also it is the first public-key encryption.
Let’s start with an example and this is actually easier to understand if you take a piece of paper and do the calculation as you read.
Example
We just want to encrypt a single character, a single letter, the letter B
. We first have to transform this letter into a number, the number 2
.
We chose the number 2 for the letter B because we consider
- A = 1
- B = 2
- C = 3
- …
The message that we are encoding is $m$
$m=2$
The public_key
and private_key
we already know and we will understand how to use them and then we are going to understand how to create the keys.
Our public_key
, also known as encryption key consists of 2 numbers:
- $e = 5$ public (or encryption) exponent
- $n = 14$ modulus
The private_key
, also known as decryption key is made of:
- $d = 11$ private (or decryption) exponent
- $n = 14$ modulus
Encryption
These are the important parts for encryption.
What we know
- $m = 4$ message to be encrypted
- $e = 5$ exponent of public key
- $n = 14$ modulus of public key
What we need to compute
- $c$ encrypted cypher text
To encrypt some data you need to compute
$m^e \mod n = c$
In our case
$2^5 mod 14 = 4$
Decryption
These are the important parts for decryption
What we know
- $c = 4$ - cyphertext aka encrypted message (computed above)
- $d = 11$ - exponent of private key
- $n = 14$ - modulus of private key
What we need to compute
- $m$ - decrypted message
To decrypt some data you need to compute
$c^d \mod n = m$
In our case
$4^{11} mod 14 = 2$
Now we understand the basic process to encrypt and decrypt data, we have to find out how to generate the public_key
and the private_key
.
Compute the encryption and decryption keys
We start by picking $2$ prime numbers $p$ and $q$
$p = 2$
$q = 7$
We compute the $n$ modulus which will be part of both private and public keys
$p * q = n$
That means
$n = 14$
And we also need to compute $\phi(n)$ which we will need later
$(p - 1) * (q - 1) = \phi(n)$
$(2 - 1) * (7 - 1) = 6$
$\phi(n) = 6$
Public key
We need to pick an $e$ that fulfills these conditions:
$e \left\{
\begin{array}{ll}
1 < e < \phi(n) \\ e \perp n\\ e \perp \phi(n)\
\end{array}
\right.$
In this case $\perp$ means coprime, meaning it does not have any divisors in common with $n$ or with $\phi(n)$.
In other words - $e$ is greater than $1$ and lower than $\phi(n)$ - $\gcd(e, n) = 1$ - $\gcd(e, \phi(n)) = 1$
Where $\gcd$ denotes the greatest common divisor.
The numbers that are greater than $1$ and lower than $\phi(n)$ are:
$2$ $3$ $4$ $5$
Out of these numbers, the only number that is coprime with 14 and 6 is
$\bcancel2$ $\bcancel3$ $\bcancel4$ $5$
That means
$e = 5$
This makes our public_key $(e = 5, n = 14)$
Private key
We need to pick a $d$ such as
$(d*e)\mod \phi(n) = 1$
In this case we need to do a little bit of work. So a simple python script should be able to solve this
e = 5
phi_n = 6
for i in range(1,50):
if (i * e) % phi_n == 1:
print("Found {}".format(i))
Which outputs
Found 5
Found 11
Found 17
Found 23
Found 29
Found 35
Found 41
Found 47
We can pick any result, I decided to pick $d = 11$.
Which makes our private key $(d = 11, n = 14)$
Conclusion
We got our keys:
- public key $(e = 5, n = 14)$
- private key $(d = 11, n = 14)$
And we learned how to derive the encryption and decryption keys.
In practice things are a bit harder, you need to pick huge prime numbers and the bigger they are, the stronger your cyper is. But it’s super important to understand how to do this and it’s fairly easy to do with small numbers.