# System Imports import math import random # Project Imports import SHA256Custom class Receiver: """Class for dealing with the receiving end of the custom simple RSA encryption""" def __init__(self): # A list of small prime numbers we can use to calculate a larger one self.__small_primes_list = [211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349] self.__p = None self.__q = None self.__n = None self.__t = None # This is apparently the most commonly used shared co-prime used for RSA self.__e = 65537 self.__d = None # The generated public and private keys self.__public_key = None self.__private_key = None self.generated = False # The bit size of the key self.__bit_size = 1024 def generate_keys(self) -> bool: """Method to generate the RSA Public and Private keys for encryption""" try: # Only generate keys if we haven't already if not self.generated: self.__p = self.__generate_prime_number() self.__q = self.__generate_prime_number() # Make sure we have 2 different prime numbers while self.__q == self.__p: self.__q = self.__generate_prime_number() # Most of the following is just the pseudo code for RSA prime generation self.__n = self.__p * self.__q self.__t = (self.__p - 1) * (self.__q - 1) while math.gcd(self.__t, self.__e) > 1: self.__e += 2 if self.__e < 1 or self.__e > self.__t: raise Exception("E must be > 1 and < T") if self.__t % self.__e == 0: raise Exception("E is not a co-prime with T") self.__d = Receiver.find_inverse(self.__e, self.__t) # We have our keys, set up the tuples and flag the generated as true self.__public_key = (self.__e, self.__n) self.__private_key = (self.__d, self.__n) self.generated = True return True else: raise Exception("Keys have already been generated.") except Exception: return False def get_expected_block_size(self) -> int: """Method to return the expected block size for the encrypted data""" # the encrypted request blocksize seems to be half of the bit size return int(self.__bit_size / 2) def get_public_key_pair(self, hex_result=True): """Method for returning the public key as a hex string or tuple depending on the hex_results""" if hex_result: # Return both public key elements as a hex string return "{0:x} {1:x}".format(self.__public_key[0], self.__public_key[1]) else: return self.__public_key def get_private_key_pair(self, hex_result=True): """Method for returning the private key as a hex string or tuple, not really used""" if hex_result: # Return both private key elements as a hex string return "{0:x} {1:x}".format(self.__private_key[0], self.__private_key[1]) else: return self.__private_key def decrypt_string(self, string_in: str) -> str: """Method for decrypting our custom RSA encrypted blocks, takes the hex string in""" if self.generated: # Convert the hex string back into an int encrypted_string_as_int = int(string_in, 16) # Do the math on our encrypted int decrypted_string_as_int = pow(encrypted_string_as_int, self.__d, self.__n) # Convert the result back into a hex string decrypted_string_as_hex = "{0:x}".format(decrypted_string_as_int) start_padding_included = False plain_text_read = False plain_text_string = '' hashed_checksum = '' # Loop for every 2 characters (hex) for i in range(0, len(decrypted_string_as_hex), 2): current_byte = decrypted_string_as_hex[i:i+2] # the encrypted string should start with a padding FF value if not start_padding_included and current_byte.upper() == "FF": start_padding_included = True # the Checksum hash should start after the 00 value elif not plain_text_read and start_padding_included and current_byte == "00": plain_text_read = True # Everything else should be the message or the checksum hash elif start_padding_included: if not plain_text_read: # The message is padded after the fact to fill up the bit size, these are ignored if current_byte.upper() != "FF": # Convert the hex value back into a utf character plain_text_string += chr(int(current_byte, 16)) else: # Reconstruct the hash checksum hashed_checksum += current_byte # If the text of hash is missing then something went wrong with encrypting or sending if len(plain_text_string) == 0 or len(hashed_checksum) == 0: raise Exception("No text was decrypted, something must be wrong...") # Hash the plain text string and make sure it matches our checksum hash hash_test = SHA256Custom.SHA256Custom() hash_test.update(plain_text_string.encode()) hashed_plain_text = hash_test.hexdigest() if hashed_plain_text == hashed_checksum: # The message has not been altered, decrypted successfully return plain_text_string else: raise Exception("Plain text did not match the Hashed Checksum, something is wrong.") else: raise Exception("No key has been generated") def __generate_prime_number(self) -> int: """Private method for generating prime numbers with the bit size set""" while True: current_prime_candidate = self.__generate_low_level_prime(self.__bit_size) if not self.miller_rabin_prime_check(current_prime_candidate): continue else: return current_prime_candidate def __generate_low_level_prime(self, prime_candidate: int) -> int: """Private method for generating the prime number using the candidate number and the small prime array""" while True: current_prime_candidate = self.generate_random_large_int(prime_candidate) # We try to generate a large prime number using the candidate and looping through the small primes # array until we get one for divisor in self.__small_primes_list: if current_prime_candidate % divisor == 0 and divisor ** 2 <= current_prime_candidate: break else: return current_prime_candidate @staticmethod def generate_random_large_int(n_bit_size: int) -> int: """Static method to generate a large int value""" # Get a random number in a range of the bit size given return random.randrange(2 ** (n_bit_size - 1) + 1, 2 ** n_bit_size - 1) # Method to test that the prime number we generate passes the miller rabin prime candidate test @staticmethod def miller_rabin_prime_check(prime_candidate: int) -> bool: """Static method for the miller rabin prime number checking algorithm, to ensure that we have a valid prime""" max_divisions_by_two = 0 prime_minus_one = prime_candidate - 1 while prime_minus_one % 2 == 0: prime_minus_one >>= 1 max_divisions_by_two += 1 assert 2 ** max_divisions_by_two * prime_minus_one == prime_candidate - 1 def trial_composite(round_tester_in): """Sub method for doing the actual prime number factorisation check""" if pow(round_tester_in, prime_minus_one, prime_candidate) == 1: return False for x in range(max_divisions_by_two): if pow(round_tester_in, 2 ** x * prime_minus_one, prime_candidate) == prime_candidate - 1: return False return True for i in range(0, 20): round_tester = random.randrange(2, prime_candidate) if trial_composite(round_tester): return False return True @staticmethod def extended_euclidean_algorithm(a: int, b: int) -> tuple: """Static method for the EEA from the pseudo code""" if b == 0: return 1, 0 q = a // b r = a % b s, t = Receiver.extended_euclidean_algorithm(b, r) return t, s-(q*t) @staticmethod def find_inverse(a: int, b: int) -> int: """Static method for finding the inverse of the primes given""" inverse = Receiver.extended_euclidean_algorithm(a, b)[0] if inverse < 1: inverse += b return inverse class Transmitter: """Class for dealing with the transmitting end of the custom simple RSA encryption""" def __init__(self, public_key: str): # We should be getting the string hex values from the receiver and splitting them into the actual parts public_key_parts = public_key.split(" ", 1) # Must match the Receiver bit size self.__bit_size = 1024 # Check if the public key has 2 parts to be valid if len(public_key_parts) == 2: self.__e = int(public_key_parts[0], 16) self.__n = int(public_key_parts[1], 16) self.__has_key = True else: self.__has_key = False raise Exception("Public key was incorrect") def get_current_key_pair(self): """Method for getting the key pair values e and n""" return self.__e, self.__n def get_usable_byte_length(self) -> int: """Method for getting the usable byte length incase we need to split a request into multiple parts""" # Im not entirely sure on this as it was calculated mostly by "brute force" but it seems to be the # key size divided by 4 # minus 2 bytes for the start and hash break bytes added # minus 32 for the SHA256 hash size # minus 32 for the RSA byte overhead, i've tried different values but getting too close to 256 bytes will # sometimes case issues which i think is down to return int(self.__bit_size / 4) - 2 - 32 - 32 def encrypt_string(self, string_in: bytes) -> bytes: """Method for encrypting a string using the public RSA key provided by the receiver""" if self.__has_key: # Create a hash of the message given for our checksum string_hashing = SHA256Custom.SHA256Custom() string_hashing.update(string_in) string_hashed = string_hashing.hexdigest() # Pad to make the string the full size of the custom RSA block padding = "" if len(string_in) < self.get_usable_byte_length(): padding_required = self.get_usable_byte_length() - len(string_in) - 1 padding = "ff" * padding_required # Add an FF pad at the start of the string, since if the input hex starts with a 0X value the 0 is dropped # when it is converted to an int, im not entirely sure how they get around this hex_string = "ff" + string_in.hex() + padding + "00" + string_hashed string_as_int = int(hex_string, 16) # Do the math to the int value encrypted_string_as_int = pow(string_as_int, self.__e, self.__n) # Convert the int value into a hex string encrypted_string_hex = "{0:x}".format(encrypted_string_as_int) return encrypted_string_hex.encode() else: raise Exception("No key has been generated")