If you followed along with part 1 of this series, you should have code that very closely resembles something like this:
from random import randrange
class RSA:
def __init__(self, desired_entropy):
self.entropy = desired_entropy
def create_key_pair(self):
n = 10000
sieve = set(range(2, n+1))
primes = []
while sieve:
prime = min(sieve)
primes.append(prime)
sieve -= set(range(prime, n+1, prime))
p = primes[randrange(len(primes))]
q = primes[randrange(len(primes))]
phi = (p - 1) * (q - 1)
n = p * q
e = self.get_e(phi)
extended_euclidean = self.get_inverse(e, phi)
d = extended_euclidean[1]
if d < 0:
d += phi
self.public_key = (n, e)
self.private_key = (n, d)
def get_e(self, phi):
k = 16
e = 2 ** k + 1
while e < phi:
gcd = self.get_inverse(e, phi)[0]
if gcd == 1:
return e
else:
k += 1
e = 2 ** k + 1
def get_inverse(self, a, b):
if a == 0 :
return b, 0, 1
gcd, n, m = self.get_inverse(b % a, a)
x = m - (b // a) * n
y = n
return gcd, x, y
def encrypt(self, plaintext):
n = self.public_key[0]
e = self.public_key[1]
return "".join([hex(pow(ord(c), e, n)) for c in plaintext])
def decrypt(self, ciphertext):
from re import split
n = self.private_key[0]
d = self.private_key[1]
ciphertext = [int(i, 16) for i in split(r"0x", ciphertext) if i]
return "".join([chr(pow(c, d, n)) for c in ciphertext])
if __name__ == "__main__":
rsa = RSA(0)
rsa.create_key_pair()
user_input = input("input to encrypt:\n>> ")
encrypted = rsa.encrypt(user_input)
print(encrypted)
decrypted = rsa.decrypt(encrypted)
print(decrypted)
assert decrypted == user_input
As mentioned in the last post, this may be good for showing the concept of RSA but it is not going to cut the mustard if we try to use the size of numbers needed to actually create a secure algorithm.
Let’s beef this up to make it more real world ready
RSA, to be considered secure into the year 2030, requires an entropy of 2048 bits. This means that primes p and q will each need to be 1024 bits long. Trying to find primes that large will require a new approach as a simple sieve will not be able to produce the results needed within any type of reasonable time frame.
class RSA:
--snipped--
def create_key_pair(self):
p = self.get_prime(self.entropy)
q = self.get_prime(self.entropy)
--snipped--
def get_prime(self, desired_entropy):
while True:
n = desired_entropy // 2
prime_candidate = self.create_prime_candidate(n)
if not self.is_prime(prime_candidate):
continue
else:
return prime_candidate
def create_prime_candidate(self, n):
pass
def is_prime(self, n):
pass
--snipped--
Here, I have offloaded the the responsibility of creating a prime to a few different methods outside of create_key_pair. This keeps the methods cleaner and is better for self-documentation. Next, it’s time to begin populating the empty methods just created. We’ll start with the create_prime_candidate method.
class RSA():
first_70_primes = [
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, 101, 103,
107, 109, 113, 127, 131, 137, 139,
149, 151, 157, 163, 167, 173, 179,
181, 191, 193, 197, 199, 211, 223,
227, 229, 233, 239, 241, 251, 257,
263, 269, 271, 277, 281, 283, 293,
307, 311, 313, 317, 331, 337, 347,
349
]
--snipped--
def random_range_of_n_bits(self, n):
return randrange(2**(n-1)+1, 2**n - 1)
def create_prime_candidate(self, n):
while True:
prime_candidate = self.random_range_of_n_bits(n)
# disqualify candidate if divisible by any of first 70 primes
for divisor in RSA.first_70_primes:
if prime_candidate % divisor == 0 and divisor**2 <= prime_candidate:
break
else:
return prime_candidate
--snipped--
Notice, that the create_prime_candidate relies on a new method, random_range_of_n_bits and a list of the first 70 primes (retrieved by running the sieve from the previous post). random_range_of_n_bits offers number in the range of (binary format) 1 followed by n-2 number of zeroes followed by 1 through n number of ones. As an example, if desired entropy were 20, each number would need 10 bits. With 10 bits the lower bound of random_range_of_n_bits would be 513 which in binary is 1000000001 or 1 followed by 8 (n-2) zeroes followed by one. The upper bound would be 1023 which in binary is 1111111111 or 10 (n) ones.
This ensures that the algorithm gives the correct number of bits as requested.
Next, I’ll use a Miller Rabin primality test for the is_prime method.
def is_prime(self, n, k=20):
"""
Miller Rabin primality test to determine probability of large primes
Input: n = number being checked for primality, k = number of rounds
output: boolean indicating whether or not the number is likely a prime
"""
powers_of_two = 0
d = n - 1
while d % 2 == 0:
d >>= 1
powers_of_two += 1
def is_composite(a):
if pow(a, d, n) == 1:
return False
for i in range(powers_of_two):
if pow(a, 2 ** i * d, n) == n - 1:
return False
return True
for _ in range(k):
a = randrange(2, n - 1)
if is_composite(a):
return False
return True
Now, the RSA class has the ability to generate large primes without being bogged down. However, there is a new problem.
The decrypt function, as it is currently written, will hang and/or crash when attempting to complete the maths with such large numbers. In order to fix this, the program will need a revamp on the decrypt function.
Before we can get to the decrypt function, however, we’ll need to add some information to the private key. if you take a look at RFC 3447, and check out section A.1.2, you will notice that the RSA private key contains much more than just n and d. Instead, it stores values for n, e, d, p, q, d mod (p -1), d mod (q -1), and (inverse of q) mod p. The first five should already be familiar. The last three are what we will need to calculate and use to increase the efficiency of the decrypt method.
def create_key_pair(self):
p = self.get_prime(self.entropy)
q = self.get_prime(self.entropy)
phi = (p - 1) * (q - 1)
n = p * q
e = self.get_e(phi)
extended_euclidean = self.get_inverse(e, phi)
d = extended_euclidean[1]
if d < 0:
d += phi
extended_euclidean = self.get_inverse(q, p)
co = extended_euclidean[1]
if co < 0:
co += p
self.public_key = (n, e)
self.private_key = (0, n, e, d, p, q, d % (p-1), d % (q-1), co)
The astute observer will notice that the new private key includes 0 as the version number. This simply indicates that there are only two primes in the key. If there were three or more primes, the version would be set to 1.
Now that the RSA private key is more robust, it is time to beef up the decrypt method to match.
def decrypt(self, ciphertext):
from re import split
p = self.private_key[4]
q = self.private_key[5]
ex1 = self.private_key[6]
ex2 = self.private_key[7]
co = self.private_key[8]
ciphertext = [int(i, 16) for i in split(r"0x", ciphertext) if i]
decrypted = ""
for i in ciphertext:
m1 = pow(i, ex1, p)
m2 = pow(i, ex2, q)
h = (co * (m1 - m2)) % p
decrypted += chr(m2 + h * q)
return decrypted
It is interesting to note here that the variable d is no longer used in the decrypt algorithm. I haven’t looked it up but I am expecting that the decrypt variable d is used for nothing more than signing messages now that it is not needed to decrypt data. I’ll let the curious reader explore that on their own.
Now, the only thing left to do is to fix how we initialize an instance of the class by including a desired_entropy in the call for construction.
if __name__ == "__main__":
rsa = RSA(2048)
--snipped--
And there you have it. RSA encryption and decryption that can use the recommended size of numbers to keep its communications safe.
The next post in this series will tackle creating and using keys that are stored on disk. Hope to see you there.
References:
https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/
https://en.wikipedia.org/wiki/RSA_(cryptosystem)