285 lines
12 KiB
Python
285 lines
12 KiB
Python
# 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")
|