Introduction
In the first article, we saw the two kinds of cryptosystems, symmetric and asymmetric, and how to generate entropy and we upload to our development board. In this article, we are going to see how to generate our RSA keys and the program display these keys on the LCD.
Walking through the world of coprime
The RSA encryption algorithm is based on the prime number and the coprime, so, it’s important to understand these concepts, and we are going to walk through to see what are they. For people who do not like maths, believe me, it’s easy to understand.
Maths
Euclidean division
The Euclidean division is a primordial arithmetic and it’s used in RSA encryption. All concept we are going to see in this article is based on the Euclidean division.
The Euclidean division is the best way to find the greatest common divider (GCD), and for doing that, you divide the dividend by the divisor. The equation of the Euclidean division is this one: \(a = bq + r\). Where, \(a\) is the dividend, \(b\) the divisor, \(q\) the quotient and \(r\) the remainder. Take an example with a = 25 and b = 7.
$$\begin{aligned} 25 = & 7q + r \\\ 25 = & 7\times3 + 4 \end{aligned}$$
For finding the greatest common divider, we repeat until the remainder equal to 0. So, for doing that, the divisor become the dividend and the remainder become the divisor, like that:
$$ \begin{aligned} 7 = & 4 \times 1 + 3\\\ 4 = & 3 \times 1 + 1 \\\ 3 = & 1 \times 3 + 0 \end{aligned} $$
So, the GCD of 25 and 7 is 1, because it’s the last value of the divisor. Another example, we want to find what is the GCD of 4105 and 33:
$$ \begin{aligned} 4105 & = 33 \times 124 + 13 \\\ 33 & = 13 \times 2 + 7 \\\ 13 & = 7 \times 1 + 6 \\\ 7 & = 6 \times 1 + 1 \\\ 6 & = 1 \times 6 + 0 \end{aligned} $$
So, the GCD of 4105 and 33 is 1. Another example for 413 and 126:
$$ \begin{aligned} 413 & = 3 \times 126 + 35 \\\ 126 & = 35 \times 3 + 21 \\\ 35 & = 21 \times 1 + 14 \\\ 21 & = 14 \times 1 + 7 \\\ 14 & = 7 \times 2 + 0 \end{aligned} $$
This time, the GCD of 413 and 126 is 7. For calculating the Euclidean division in computing, we use the modulo:
$$ \begin{aligned} 413 \mod(126) & = 35 \\\ 126 \mod(35) & = 21\\\ 35 \mod(21) & = 14 \\\ 21 \mod(14) & = 7 \\\ 14 \mod(7) & = 0 \end{aligned} $$
The code below can find the GCD in python:
#!/usr/bin/env python3
def gcd(a, b):
if b == 0:
return a
return gcd(b, a%b)
print(gcd(4105, 33))
print(gcd(413, 126))
Now, we seen how to find the GCD with the Euclidean division, we are going to see the concept of the prime number.
Prime number
A prime number is a positive number which are dividers by 1 and the number itself. 0 and 1 are not prime numbers. In RSA encryption, we need to generate some randomness variables and they need to be prime number.
For identifying a prime number, we need to use the GCD algorithm and, if a number can be divided only by 1 and the number itself, it’s a prime number. We need to identify all GCD until the number itself. For instance, 19 is a prime number, because 19 can be divided only by 1 and 19 itself, and the number 20 is not a prime number, because it can be divided by 2, 4, 5 and 10. The python code below show if 19 and 20 are prime numbers:
$ cat prime_number.py
#!/usr/bin/env python3
def primeNumber(p):
values = []
for i in range(2, p):
values.append(p % i)
return values
print(f"19: {primeNumber(19)}")
print(f"20: {primeNumber(20)}")
$ python3 prime_number.py
19: [1, 1, 3, 4, 1, 5, 3, 1, 9, 8, 7, 6, 5, 4, 3, 2, 1]
20: [0, 2, 0, 0, 2, 6, 4, 2, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1]
For illustrating the concept of prime number, the C code below generate the 100 first prime numbers.
$ cat prime_numbers.c
#include <stdlib.h>
#include <stdio.h>
static int isPrimeNumber(int);
static int generatePrimeNumber(int);
int main(void) {
generatePrimeNumber(100);
}
static int isPrimeNumber(int x){
for (int i = 2; i < x; i++){
if (x % i == 0)
return 1;
}
return 0;
}
static int generatePrimeNumber(int max){
int i = 2;
// Generate a list of prime number
while (i <= max) {
if (isPrimeNumber(i) == 0)
printf("%d, ", i);
i++;
}
}
$ gcc prime_numbers.c -o prime_number && ./prime_number
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
Coprime
By definition, if two positive integers doesn’t have any dividers in common, they are coprime, except the number 1. The best way to find a coprime is to use the GCD. For instance, 27 and 56 are coprime, but 27 and 54 are not coprime, because both of them can be divided by 3:
$ cat coprime.py
#!/usr/bin/env python3
def coprime(a):
values = []
for i in range(1, a):
if a % i == 0:
values.append(i)
return values
print(f"27: {coprime(27)}")
print(f"54: {coprime(54)}")
print(f"56: {coprime(56)}")
$ python3 coprime.py
27: [1, 3, 9]
54: [1, 2, 3, 6, 9, 18, 27]
56: [1, 2, 4, 7, 8, 14, 28]
I hope you survived until now. These concept are easy to understand, and it’s really important to understand them before to continue to read the article, because in the next section we are going to practice.
Example
Now we seen the concept of prime number and coprime, we can start practising and how to generate keys with RSA. For generating keys, we need to do different steps:
- Choose \(p\) and \(q\) which need to be prime numbers
- compute \(n = pq\). That is used for the modulus for both public and private key.
- Compute \(\varphi(n)\), based on the Euler’s totient.
- Choose \(e\), which is the public key. \(e\) must be lower than \(\varphi(n)\) and coprime with it.
- Generate \(d\) as \(d \equiv e^{-1} mod(\varphi(n))\).
The first step for generating keys, it’s to choose randomly two numbers, called p and q and these numbers need to be prime numbers. For instance, we will choose:
$$ \begin{aligned} p = 41 \\\ q = 61 \end{aligned} $$
After we choose \(p\) and \(q\), we need to calculate \(n\) and phi (\(\varphi\)). \(n\) is very simple to calculate, it’s just the multiplication of \(p\) and \(q\). For \(\varphi\), we can use the Euler’s totient, but we can easily calculate with this formula: \(\varphi (n) = (p - 1)(q - 1)\).
$$ \begin{aligned} n & = pq \\\ n & = 41 \times 61 \\\ n & = 2501 \\\ \varphi (n) & = (p - 1)(q - 1) \\\ \varphi (n) & = (41 -1)(61 -1) \\\ \varphi (n) & = 2400 \end{aligned} $$
For the next step, we need to calculate the number \(e\), which need to be lower than \(\varphi (n)\) and must be coprime with it. Let \(e = 137\).
Now, we need to generate \(d\), which is the modular inverse of \(\varphi(n)\). For doing that, we need to find an integer multiply by \(e\) and the modular of \(\varphi(n)\) and it must be coprime with \(\varphi(n)\). The code below can find the \(d\) value:
for i in range(0, phi - 1):
if i * e % phi == 1:
d = i
break
Let \(d = 473\).
The python program can generate RSA keys:
$ cat example.y
#!/usr/bin/env python3
def gcd(a, b):
if b == 0:
return a
return gcd(b, a%b)
p = 41
q = 61
n = p * q
phi = (p - 1) * (q - 1)
e = 135
d = 0
print(f"n: {n}")
for i in range(1, phi - 1):
if gcd(phi, e) != 1:
e = e + 1
print(f"e: {e}")
for i in range(1, phi - 1):
if i * e % phi == 1:
d = i
break
print(f"d: {d}")
$ python3 example.py
n: 2501
e: 137
d: 473
Good, we have our keys, now, we can encrypt and decrypt our data. For encrypting, we need to get the product of the hexadecimal value and of \(e\), and we do a modular of the product and \(\varphi(n)\). For decrypting, it’s the same operation, but, we use \(d\). The python code below encrypt and decrypt a string:
$ cat test_encryption.py
#!/usr/bin/env python3
n = 2501
e = 137
d = 473
s = "Encryption"
encryptedData = list()
decryptedData = list()
for i in range(0, len(s)):
encryptedData.append(ord(s[i]) ** e % n)
print(encryptedData)
for i in range(0, len(s)):
decryptedData.append(chr(encryptedData[i] ** d % n))
print(decryptedData)
$ python3 test_encryption.py
[1980, 832, 1318, 155, 1768, 1161, 2348, 373, 294, 832]
['E', 'n', 'c', 'r', 'y', 'p', 't', 'i', 'o', 'n']
Program - C
The aim of this section is to implement in our RSA application and to upload to the Arduino Uno board. In the first article, we seen how the project is split in different files. So, the source files rsa.h and rsa.c interest us for generating RSA keys.
When the program has completed to generate the entropy pool, the program call the function generateKeys(), which take three arguments: both public and private keys and the modulus.
In this function, we generate \(p\) and \(q\), which need to be prime number. The program call the function prng() which get the value from the entropy pool. After this operation, the program check if the value is a prime number, if is not, we increase the value until it’s a prime number. For finding the prime number, I made this function:
static void prime_number_finder(unsigned long *p){
while(isPrimeNumber(*p) != 0)
*p += 1;
}
After that, the program compute \(n\) and \(\varphi(n)\). Now we generate our numbers, we can start to generate our keys. So, first, we call the function generatePublicKey(). In this function, we generate get a data from the entropy pool and we increase the value until \(e\) is coprime with \(\varphi(n)\). When we found it, the program will generate the private key.
As we seen above, for generating the private key, the program determine \(d\), which is the modulus inverse of \(e\) modulus \(\varphi(n)\).
The program has finished to generate RSA keys, now, the program display these keys in the LCD. So, for doing that, in the loop() function, we print these values:
lcd.setCursor(0, 0);
lcd.print("e:" + String(e) + "," + String(n));
lcd.setCursor(0, 1);
lcd.print("d:" + String(d) + "," + String(n));
You have the result like that:
Now, you can encrypt and decrypt your data with the keys you generated. If you want, you can push the button and the program will generate another keys.
In conclusion
RSA is a fundamental part in the cryptography world, a lot of cryptography libraries use RSA, like OpenSSL or even for the SSH keys with ssh-keygen. Despite it is an old cryptosystem, it’s very use in cryptography. I hope you enjoyed to read this article and like me you like the cryptography part.
References
These articles permit me to write these two articles: