To keep this guide sweet and simple we restrain ourself to using small primes.
(We also won’t use padding schemes or other security measures)
Should you use RSA in production always make sure to use numbers which are at least 512 Bit / 64 Byte long.
RSA is an asymmetric cryptographic method consisting of a public key for encryption and a private key for decyption.
This means that the ascii value of a letter, for example, is converted into a cipher using the public key and converted back into plaintext using the private key.
RSA provides security if the public key and the private key are sufficiently long (min. 64bytes). This is the case because it is theoretically possible to calculate the private key from the public key with immense effort for small prime numbers.
The first step of key generation consists of choosing p and q such that:
$$ \begin{align} p \not= q \end{align} $$
and that both numbers are prime.
Here, for example, we can choose p and q as follows:
$$ \begin{align} p = 61 \\\ q = 97 \end{align} $$
PYTHON
1p = 61
2q = 97
Now n has to be determined from the multiplication of the two previously selected numbers:
$$ \begin{align} n &= p \cdot q \\\ &= 61 \cdot 97 \\\ n &= \underline{5917} \end{align} $$
PYTHON
1p = 61
2q = 97
3print(f"n={p*q}")
4# n=5917
After we have chosen p and q and calculated n, now follows the calculation of a number by calculating phi of n:
$$ \begin{align} \phi(n) &= (p-1) \cdot (q-1) \\\ &= (61-1) \cdot (97-1) \\\ &= (60) \cdot (96) \\\ \phi(n) &= \underline{5760} \\\ \end{align} $$
PYTHON
1p = 61
2q = 97
3
4print(f"n={p*q}")
5# n=5917
6
7phi = (p-1)*(q-1)
8
9print(f"phi={phi}")
10# phi=5760
is relatively prime, i.e. the following applies:
$$ \begin{align} \gcd(e, \phi(n)) &= 1 \\\ \gcd(e, 5760) &= 1 \\\ \gcd(\underline{47}, 5760) &= 1 \end{align} $$
Our goal is to choose a small but not too small odd number for e, therefore i use the 47 for e.
PYTHON
1from math import gcd
2
3p = 61
4q = 97
5
6print(f"n={p*q}")
7# n=5917
8
9phi = (p-1)*(q-1)
10
11print(f"phi={phi}")
12# phi=5760
13
14pe = []
15for i in range(2, phi):
16 if gcd(i, phi) == 1:
17 pe.append(i)
18 # stop looping after 12 elements in array pe
19 if len(pe) == 12:
20 break
21
22print(f"e={pe[-1]}")
23# e=47
Formula for calculating the private key:
$$ \begin{align} e \cdot d \mod \phi(n) &= 1 \\\ 47 \cdot d \mod 5760 &= 1 \\\ 47 \cdot \underline{1103} \mod 5760 &= 1 \end{align} $$
PYTHON
1from math import gcd
2
3p = 61
4q = 97
5
6print(f"n={p*q}")
7# n=5917
8
9phi = (p-1)*(q-1)
10
11print(f"phi={phi}")
12# phi=5760
13
14pe = []
15for i in range(2, phi):
16 if gcd(i, phi) == 1:
17 pe.append(i)
18 # stop looping after 12 elements in array pe
19 if len(pe) == 12:
20 break
21
22print(f"e={pe[-1]}")
23# e=47
24
25d = 0
26for i in range(0, phi):
27 if (i*pe[-1]) % phi == 1:
28 d = i
29 break
30
31print(f"d={d}")
32# d=1103
Resulting keys:
$$ \begin{align} \textrm{Public key: } (e,n) \rightarrow (47, 5917) \\\ \textrm{Private key: } (d,n) \rightarrow (1103, 5917) \\\ \end{align} $$
To encrypt a string, we first need to convert the characters in the string to their numeric representation:
Example string: hello:)
| Characters | h | e | l | l | o | : | ) |
|---|---|---|---|---|---|---|---|
| Numeric | 104 | 101 | 108 | 108 | 111 | 58 | 41 |
PYTHON
1from math import gcd
2
3p = 61
4q = 97
5
6print(f"n={p*q}")
7# n=5917
8
9phi = (p-1)*(q-1)
10
11print(f"phi={phi}")
12# phi=5760
13
14pe = []
15for i in range(2, phi):
16 if gcd(i, phi) == 1:
17 pe.append(i)
18 # stop looping after 12 elements in array pe
19 if len(pe) == 12:
20 break
21
22print(f"e={pe[-1]}")
23# e=47
24
25d = 0
26for i in range(0, phi):
27 if (i*pe[-1]) % phi == 1:
28 d = i
29 break
30
31print(f"d={d}")
32# d=1103
33
34example_string = "hello:)"
35print(f"example_string={example_string}")
36# example_string=hello:)
37example_string_numeric = [ord(c) for c in example_string]
38print(f"example_string_numeric={example_string_numeric}")
39# example_string_numeric=[104, 101, 108, 108, 111, 58, 41]
We can now encrypt each characters numeric value by applying the following formula:
$$ \begin{align} e(m) = m^e \mod n \end{align} $$
where m is the character to encrypt and e and n are pieces of the public key:
$$ \textrm{Public key: } (e,n) \rightarrow (47, 5917) \\\ $$$$ \begin{align} e(104)&=104^{47} \mod 5917=3381 \\\ e(101)&=101^{47} \mod 5917=5214 \\\ e(108)&=108^{47} \mod 5917=2575 \\\ e(108)&=108^{47} \mod 5917=2575 \\\ e(111)&=111^{47} \mod 5917=3000 \\\ e(58)&=58^{47} \mod 5917=3303 \\\ e(41)&=41^{47} \mod 5917=3809 \\\ \end{align} $$
PYTHON
1from math import gcd
2
3p = 61
4q = 97
5
6print(f"n={p*q}")
7# n=5917
8
9phi = (p-1)*(q-1)
10
11print(f"phi={phi}")
12# phi=5760
13
14pe = []
15for i in range(2, phi):
16 if gcd(i, phi) == 1:
17 pe.append(i)
18 # stop looping after 12 elements in array pe
19 if len(pe) == 12:
20 break
21
22print(f"e={pe[-1]}")
23# e=47
24
25d = 0
26for i in range(0, phi):
27 if (i*pe[-1]) % phi == 1:
28 d = i
29 break
30
31print(f"d={d}")
32# d=1103
33
34example_string = "hello:)"
35print(f"example_string={example_string}")
36# example_string=hello:)
37example_string_numeric = [ord(c) for c in example_string]
38print(f"example_string_numeric={example_string_numeric}")
39# example_string_numeric=[104, 101, 108, 108, 111, 58, 41]
40
41encrypted = []
42for c in example_string_numeric:
43 encrypted.append(c ** pe[-1] % (p*q))
44
45print(f"encrypted={encrypted}")
46# encrypted=[3381, 5214, 2575, 2575, 3000, 3303, 3809]
47print(f"chiffre={' '.join([str(i) for i in encrypted])}")
48# chiffre=3381 5214 2575 2575 3000 3303 3809
| Characters | h | e | l | l | o | : | ) |
|---|---|---|---|---|---|---|---|
| Numeric | 104 | 101 | 108 | 108 | 111 | 58 | 41 |
| Chiffre | 3381 | 5214 | 2575 | 2575 | 3000 | 3303 | 3809 |
Decrypting a chiffre encrypted with RSA is simply applying the private key to the given integer and afterwards converting the result to its character representation.
Formula for decrypting:
$$ \begin{align} d(c) = c^d \mod n \end{align} $$
where c is the character to decrypt and d and n are pieces of the private key:
$$ \textrm{Private key: } (d,n) \rightarrow (1103, 5917) \\\ $$$$ \begin{align} d(3381)&=3381^{1103} \mod 5917=104 \\\ d(5214)&=5214^{1103} \mod 5917=101 \\\ d(2575)&=2575^{1103} \mod 5917=108 \\\ d(2575)&=2575^{1103} \mod 5917=108 \\\ d(3000)&=3000^{1103} \mod 5917=111 \\\ d(3303)&=3303^{1103} \mod 5917=58 \\\ d(3809)&=3809^{1103} \mod 5917=41 \\\ \end{align} $$
PYTHON
1from math import gcd
2
3p = 61
4q = 97
5
6print(f"n={p*q}")
7# n=5917
8
9phi = (p-1)*(q-1)
10
11print(f"phi={phi}")
12# phi=5760
13
14pe = []
15for i in range(2, phi):
16 if gcd(i, phi) == 1:
17 pe.append(i)
18 # stop looping after 12 elements in array pe
19 if len(pe) == 12:
20 break
21
22print(f"e={pe[-1]}")
23# e=47
24
25d = 0
26for i in range(0, phi):
27 if (i*pe[-1]) % phi == 1:
28 d = i
29 break
30
31print(f"d={d}")
32# d=1103
33
34example_string = "hello:)"
35print(f"example_string={example_string}")
36# example_string=hello:)
37example_string_numeric = [ord(c) for c in example_string]
38print(f"example_string_numeric={example_string_numeric}")
39# example_string_numeric=[104, 101, 108, 108, 111, 58, 41]
40
41encrypted = []
42for c in example_string_numeric:
43 encrypted.append(c ** pe[-1] % (p*q))
44
45print(f"encrypted={encrypted}")
46# encrypted=[3381, 5214, 2575, 2575, 3000, 3303, 3809]
47print(f"chiffre={' '.join([str(i) for i in encrypted])}")
48# chiffre=3381 5214 2575 2575 3000 3303 3809
49
50decrypted = []
51for c in encrypted:
52 decrypted.append(c ** d % (p*q))
53
54print(f"decrypted={decrypted}")
55# decrypted=[104, 101, 108, 108, 111, 58, 41]
56print(f"result={''.join([chr(i) for i in decrypted])}")
57# result=hello:)
| Numeric | 104 | 101 | 108 | 108 | 111 | 58 | 41 |
|---|---|---|---|---|---|---|---|
| Characters | h | e | l | l | o | : | ) |
As mentioned at the beginning, RSA can be cracked in several ways:
In the following chapter we will crack our private key we generated before using prime factorization to split our n into p and q.
The factorizing integers defines the process of calculating the factors which multiplied together result in the integer we factorize.
This is extremely useful to work our way back from the public key to the private key.
$$ \textrm{Public key: } (e,n) \rightarrow (47, 5917) \\\ $$$$e = 47 \\\ n = 5917$$$$ \begin{align} n = p \cdot q \end{align} $$
Using the following script, we can perform the integer factorization and calculate p and q:
PYTHON
1from math import gcd
2
3p = 61
4q = 97
5
6print(f"n={p*q}")
7# n=5917
8
9phi = (p-1)*(q-1)
10
11print(f"phi={phi}")
12# phi=5760
13
14pe = []
15for i in range(2, phi):
16 if gcd(i, phi) == 1:
17 pe.append(i)
18 # stop looping after 12 elements in array pe
19 if len(pe) == 12:
20 break
21
22print(f"e={pe[-1]}")
23# e=47
24
25d = 0
26for i in range(0, phi):
27 if (i*pe[-1]) % phi == 1:
28 d = i
29 break
30
31print(f"d={d}")
32# d=1103
33
34example_string = "hello:)"
35print(f"example_string={example_string}")
36# example_string=hello:)
37example_string_numeric = [ord(c) for c in example_string]
38print(f"example_string_numeric={example_string_numeric}")
39# example_string_numeric=[104, 101, 108, 108, 111, 58, 41]
40
41encrypted = []
42for c in example_string_numeric:
43 encrypted.append(c ** pe[-1] % (p*q))
44
45print(f"encrypted={encrypted}")
46# encrypted=[3381, 5214, 2575, 2575, 3000, 3303, 3809]
47print(f"chiffre={' '.join([str(i) for i in encrypted])}")
48# chiffre=3381 5214 2575 2575 3000 3303 3809
49
50decrypted = []
51for c in encrypted:
52 decrypted.append(c ** d % (p*q))
53
54print(f"decrypted={decrypted}")
55# decrypted=[104, 101, 108, 108, 111, 58, 41]
56print(f"result={''.join([chr(i) for i in decrypted])}")
57# result=hello:)
58
59def prime_factors(n):
60 factors = []
61 d = 2
62 while n > 1:
63 while n % d == 0:
64 factors.append(d)
65 n /= d
66 d = d + 1
67 return factors
68
69factors = prime_factors(p*q)
70print(f"factors={factors}")
71# factors=[61, 97]
$$ \begin{align} 5917 &= p \cdot q \\\ &= \underline{61 \cdot 97} \end{align} $$
Now we calculate phi of n:
$$ \begin{align} \phi(n) &= (p-1) \cdot (q-1) \\\ &= (61-1) \cdot (97-1) \\\ &= 60 \cdot 96 \\\ \phi(n) &= \underline{5760} \end{align} $$
This can be used to calculate d:
$$ \begin{align} e \cdot d \mod \phi(n) &= 1 \\\ 47 \cdot d \mod 5760 &= 1 \end{align} $$
To calculate this d, we simply use a for loop:
PYTHON
1from math import gcd
2
3p = 61
4q = 97
5
6print(f"n={p*q}")
7# n=5917
8
9phi = (p-1)*(q-1)
10
11print(f"phi={phi}")
12# phi=5760
13
14pe = []
15for i in range(2, phi):
16 if gcd(i, phi) == 1:
17 pe.append(i)
18 # stop looping after 12 elements in array pe
19 if len(pe) == 12:
20 break
21
22print(f"e={pe[-1]}")
23# e=47
24
25d = 0
26for i in range(0, phi):
27 if (i*pe[-1]) % phi == 1:
28 d = i
29 break
30
31print(f"d={d}")
32# d=1103
33
34example_string = "hello:)"
35print(f"example_string={example_string}")
36# example_string=hello:)
37example_string_numeric = [ord(c) for c in example_string]
38print(f"example_string_numeric={example_string_numeric}")
39# example_string_numeric=[104, 101, 108, 108, 111, 58, 41]
40
41encrypted = []
42for c in example_string_numeric:
43 encrypted.append(c ** pe[-1] % (p*q))
44
45print(f"encrypted={encrypted}")
46# encrypted=[3381, 5214, 2575, 2575, 3000, 3303, 3809]
47print(f"chiffre={' '.join([str(i) for i in encrypted])}")
48# chiffre=3381 5214 2575 2575 3000 3303 3809
49
50decrypted = []
51for c in encrypted:
52 decrypted.append(c ** d % (p*q))
53
54print(f"decrypted={decrypted}")
55# decrypted=[104, 101, 108, 108, 111, 58, 41]
56print(f"result={''.join([chr(i) for i in decrypted])}")
57# result=hello:)
58
59def prime_factors(n):
60 factors = []
61 d = 2
62 while n > 1:
63 while n % d == 0:
64 factors.append(d)
65 n /= d
66 d = d + 1
67 return factors
68
69factors = prime_factors(p*q);
70print(f"factors={factors}")
71# factors=[61, 97]
72new_phi = (factors[0]-1)*(factors[1]-1)
73for i in range(0, p*q):
74 if (47 * i) % 5760 == 1:
75 print(f"d={i}")
76 break
77# d=1103
$$ \begin{align} 47 \cdot \underline{1103} \mod 5760 = 1 \\\ \end{align} $$$$ \begin{align} \textrm{Private key} = (d,n) \rightarrow (1103, 5760) \end{align} $$
d and n are now given, therefore we cracked the private key and are now able to decrypt the chiffre.