In part 2 of this series, we beefed up the implementation of RSA to include the ability to use real world sized prime numbers in order to keep communications safe and secure. If you followed along, you should now have code that looks like this:
from random import randrange
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
]
def __init__(self, desired_entropy):
self.entropy = desired_entropy
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)
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 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
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
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
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
if __name__ == "__main__":
rsa = RSA(2048)
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 far as the basics go, that’s it. It’s not necessarily secure. Namely because the randomness we are using is not secure. But it certainly shows how everything works.
So where do we go from here?
There is a lot more to public key encryption than what we have covered so far. I want to get to where I can add in features to save keys to disk and work with keys saved to disk.
However, there is a bit of prerequisite knowledge needed before we can begin to tackle that task. Namely, you need to understand base64 encoding and ANS.1 objects.
Once you’ve checked out those articles and have a decent understanding of each, we can get begin adding functionality to the RSA class.
from b64 import B64
from ans1 import DER
class RSA:
--snipped--
def __init__(self, desired_entropy, private_key=None, public_key=None):
self.entropy = desired_entropy
self.private_key = private_key
self.public_key = public_key
--snipped--
First, i import the files I made to handle base64 encoding and ANS.1 object parsing. Then, I made it so that the RSA object can be initialized with both a private and public key. This will enable me to use keys found on the file system.
The keys could come from some external program, saved to disk. Or, they could be created by the RSA object itself and then saved to disk for future use.
def encode_key(self, key, encoding=None):
ans_encoding = "PKCS#8" if len(key) == 9 else "X.509"
der = DER()
der.encode(key, ans_encoding)
der_data = der.get_data()
if encoding == "PEM":
b64 = B64(der_data)
return b64.encode("hexstring")
return der_data
def package_key_for_printing(self, key, encoding=None):
select_key = {"private": self.private_key, "public": self.public_key}
key_info = self.encode_key(select_key[key], encoding)
packaged_key = "-" * 5 + f"BEGIN {key.upper()} KEY" + "-" * 5 +'\n'
for i in range(0, len(key_info), 64):
try:
packaged_key += key_info[i: i + 64] + '\n'
except IndexError:
packaged_key += key_info[i : len(key_info)] + '\n'
packaged_key += "-" * 5 + f"END {key.upper()} KEY" + "-" * 5
return packaged_key
This will print it out, but to get it saved to disk, we’ll need to do a little more.
from pathlib import Path
class RSA:
--snipped--
if __name__ == "__main__":
current_path = Path.cwd()
public_key_path = Path(current_path, "id_rsa.pub")
private_key_path = Path(current_path, "id_rsa")
def create_keys():
rsa = RSA(2048)
rsa.create_key_pair()
pem_packaged_public_key = rsa.package_key_for_printing("public", encoding="PEM")
with open(public_key_path, "w") as out:
print(pem_packaged_public_key)
out.write(pem_packaged_public_key)
pem_packaged_private_key = rsa.package_key_for_printing("private", encoding="PEM")
with open(private_key_path, "w") as out:
print(pem_packaged_private_key)
out.write(pem_packaged_private_key)
Now that the keys are on the drive, the program needs a way to pull them from the drive and into the RSA object.
def key_from_file(file_path):
key_data = ""
for line in open(file_path).readlines():
if "-" * 5 in line:
continue
else:
key_data += line.strip('\n')
b64 = B64(key_data)
return b64.decode("hexstring")
def crypt():
der = DER()
der.decode(key_from_file(public_key_path))
public_key = der.get_key_data()
der.decode(key_from_file(private_key_path))
private_key = der.get_key_data()
return RSA(2048, private_key, public_key)
Here, you can see that I am pulling in the keys and unpacking them using the DER decoding algorithm I imported earlier.
The next step is to change out the RSA encode and decode methods to be more in line with the imported base64 encoding methods I plan to use from my library. Previously, I allowed for the 0x for each byte sequence. However, now that I can base64 encode, I will need to rid the output of the 0x start sequences for the hexstring mode of my B64.encode method to work properly.
def encrypt(self, plaintext):
if not self.public_key:
return "You need to specify a public key to encrypt info"
encrypted = ""
for c in plaintext:
hexed = hex(pow(ord(c), self.public_key[1], self.public_key[0]))[2:]
if len(hexed) % 2:
hexed = "0" + hexed
encrypted += hexed
b64 = B64(encrypted)
return b64.encode("hexstring")
Note how the encrypt method now requires a public key. This can be either loaded or generated, but it needs to exist for the method to continue.
def decrypt(self, ciphertext):
if not self.private_key:
return "You need to specify a private key to decrypt info"
chunk = self.entropy // 4
b64 = B64(ciphertext)
hexed = b64.decode("hexstring")
decrypted = ""
for i in range(0, len(hexed), chunk):
m1 = pow(int(hexed[i : i + chunk], 16), self.private_key[6], self.private_key[4])
m2 = pow(int(hexed[i : i + chunk], 16), self.private_key[7], self.private_key[5])
h = (self.private_key[8] * (m1 - m2)) % self.private_key[4]
decrypted += chr(m2 + h * self.private_key[5])
return decrypted
Previously, I was able to use the re.split function to split the ciphertext by the 0x characters. Now that I got rid of those in the encode method, I needed to split the ciphertext up a different way. As it turns out, chunks that are 1/4 the size of n seem to work well. Seeing as how the size of n is determined by the user input desired_entropy, I have chosen to use that entropy variable divided by four as the proper chunk size.
Is there anything else?
That’s pretty much it. The RSA object now has the ability to create keys, PEM encode those keys, store them on disk, load them into other instances and encrypt/decrypt based upon them. It also outputs the encrypted data in base64 encoding so that it can be moved across the wire with ease.
One thing we can do is fix the randomness to make it more secure. To do so, it would be best to move away from the random library and use the secrets library instead. This will, according to the docs, “provide access to the most secure source of randomness that your operating system provides.”
The secrets library even has a method called randbits(k) that will return an int with k random bits.
I expect you can see how this would be used. Basically, I would remove the random_range_of_n_bits method and replace the only call to it with a call to secrets.randbits instead. This would beef up the entropy and, in theory, make it more secure.
But is it enough?
Stay tuned to find out. My next article in this series will look at how we can leverage our new-found understanding of the RSA algorithm to begin attacking RSA encryption.
Resources:
https://www.rfc-editor.org/rfc/rfc1421#section-4.3.2.4
https://docs.python.org/3/library/secrets.html