$30
CECS 229 Programming Assignment #3
CECS 229 Programming Assignment #3
Submission Instructions:
To receive credit for this assignment you must submit to CodePost this file converted to a Python script named pa3.py
Objectives:
Find the inverse of a given integer under a given modulo m.
Encrypt and decrypt text using an affine transformation.
Encrypt and decrypt text using the RSA cryptosystem.
Programming Tasks
You may use the utility functions at the end of this notebook to aid you in the implementation of the following tasks:
Utility functions
"""Utility Functions from previous coding assignments"""
# Writing a function to find the bezout coefficients of two numbers
def bezout_coeffs(a, b):
# Variables to store the current and updated values of a and b
value_a, value_b = a, b # Using absolute values to avoid negative a & b values
# Variables to store the current and updated values of the 1st & previous round coefficients of a and b
first_coeff_a, first_coeff_b = 1, 0
# Variables to store the current and updated values of the 2nd & next round coefficients of a and b
second_coeff_a, second_coeff_b = 0, 1
# Creating a loop to go through the rounds of coefficients until b is 0
while value_b != 0:
# Integer division of a and b
quotient = value_a // value_b
# Modulo of a and b
remainder = value_a % value_b
# Calculating the new coefficients of a and b
new_coeff_a = first_coeff_a - quotient * second_coeff_a
new_coeff_b = first_coeff_b - quotient * second_coeff_b
# Updating the values of a and b
value_a = value_b
value_b = remainder
# Updating the previous and next round coefficients of a
first_coeff_a = second_coeff_a
second_coeff_a = new_coeff_a
# Updating the previous and next round coefficients of b
first_coeff_b = second_coeff_b
second_coeff_b = new_coeff_b
return {a: first_coeff_a, b: first_coeff_b} # Returning the coefficients of a and b as a dictionary
# Writing a function to find the greatest common divisor of two numbers
def gcd(a,b):
# Calling the bezout_coeffs function to find the coefficients of a and b
a_b_coeffs = bezout_coeffs(a, b)
s_coeff_a = a_b_coeffs[a] # Coefficient of a -> s
t_coeff_b = a_b_coeffs[b] # Coefficient of b -> t
# Calculating the greatest common divisor of a and b
GCD = abs((a * s_coeff_a) + (b * t_coeff_b)) # Following the Bezout Identity: |a*s + b*t| = gcd(a,b)
return GCD # Returning the greatest common divisor of a and b
# Writing a function that computes the modular exponentiation of a number
def mod_exp(b, n, m): # b -> base; n -> exponent; m -> modulus (all positive integers)
result = 1 # result -> the final result of the modular exponentiation
if b < 0 or n < 0 or m < 0: # Checks if the base, exponent, and modulus are positive integers
result = 0 # Returns as the result 0 to satisfy the condition
pass
k = bin(n)[2:] # k -> converting the exponent 'n' into binary form using 'bin' without the '0b'
power = b % m # power -> base to the power of 2
for i in range(len(k) -1, -1, -1): # Iterates through the binary form of the exponent in reverse order
if k[i] == '1': # Checks if the current digit is 1
result = (result * power) % m # Computes the result
power = (power * power) % m # Computes the power
return result # result = b^n mod m
"""Using given utility functions in Programming Assignment #3 file"""
# Utility function to convert letters to digits
def letters2digits(letters):
digits = ""
for c in letters:
if c.isalpha():
letter = c.upper() #converting to uppercase
d = ord(letter) - 65
if d < 10:
digits += "0" + str(d) # concatenating to the string of digits
else:
digits += str(d)
return digits
# Utility function to convert digits to letters
def digits2letters(digits):
letters = ""
start = 0 #initializing starting index of first digit
while start <= len(digits) - 2:
digit = digits[start : start + 2] # accessing the double digit
letters += chr( int(digit) + 65) # concatenating to the string of letters
start += 2 # updating the starting index for next digit
return letters
# Returns the size of a block in an RSA encrypted string
def blocksize(n):
twofive = "25"
while int(twofive) < n:
twofive += "25"
return len(twofive) - 2
Problem 1:
Create a function modinv(a,m) that returns the smallest, positive inverse of a modulo m. If the gcd of a and m is not 1, then you must raise a ValueError with message "The given values are not relatively prime". You may NOT use any built-in functions as part of your implementation, but you may use any functions you implemented in previous coding assignments. Please make sure to copy and paste them into this file, so that they are uploaded to CodePost when you submit your ca3.py file.
# Writing a function that returns the smallest, positive inverse of a modulo m
def modinv(a,m):
"""returns the smallest, positive inverse of a modulo m
INPUT: a - integer
m - positive integer
OUTPUT: an integer in the range [0, m-1]
"""
# Storing the result after calling the result of the gcd() function
GCD_Calculation = gcd(a,m)
if GCD_Calculation != 1: # Checking if a and m are relatively prime
raise ValueError("The given values are not relatively prime") # Raising an error if a and m are not relatively prime
elif m < 1:
raise ValueError("\'m\' has to be a positive integer") # Raising an error if m is not greater than 1
else: # When the basic requirements above are met
# Calling the bezout_coeffs() function to find the coefficients of a and m
a_m_coeffs = bezout_coeffs(a, m)
"""Only the coefficient of 'a' is needed to find the inverse of 'a' modulo 'm'
Because sa = 1 (mod m), and s is the coefficient of 'a', where s(s_coeff_a in this case) is the inverse
According to the THM 4.4.1"""
# Setting up variables to store the coefficients of a and m
s_coeff_a = a_m_coeffs[a] # Coefficient of a -> s
correct_value = 0 # Variable to store the value of the inverse of 'a' modulo 'm'
# Setting up conditonal statments to check coefficient of 'a' are in the range [0, m-1]
if s_coeff_a >= 0 and s_coeff_a < m:
correct_value = s_coeff_a # If the coefficient of 'a' is in the range [0, m-1], then it is the correct value
else:
correct_value = s_coeff_a + m # Otherwise, add 'm' to the coefficient of 'a' to get the correct value
mod_inv_value = correct_value # Transferring the value to a better-named variable
return mod_inv_value # Returning the value of x as the inverse of 'a' modulo 'm'
Problem 2:
Create a function affineEncrypt(text, a, b) that returns the cipher text encrypted using key (a, b). You must verify that the gcd(a, 26) = 1 before making the encryption. If this is not the case, the function must raise a ValueError with message "The given key is invalid. The gcd(a,26) must be 1.". You may NOT use any built-in functions as part of your implementation, but you may use any functions you implemented in previous coding assignments. Please make sure to copy and paste them into this file, so that they are uploaded to CodePost when you submit your ca3.py file.
# Writing a function that outputs a cipher text encrypted using key(a, b)
def affineEncrypt(text, a, b):
"""encrypts the plaintext 'text', using an affine transformation key (a, b)
INPUT: text - plaintext as a string of letters
a - integer satisfying gcd(a, 26) = 1. Raises error if such is not the case
b - integer
OUTPUT: The encrypted message as a string of characters
"""
# Calling on the gcd() instruction
GCD_calculation = gcd(a, 26)
# Checking if the gcd(a, 26) is not equal to 1
if GCD_calculation != 1:
raise ValueError("The given key is invalid. The gcd(a, 26) must be 1")
else: # When the basic requirements above are met
digit_letters = letters2digits(text) # Converting the text to "digits"(numbers in string format)
# Creating a variable to store the encrypted text
encrypted_cipher_num = ""
# Writing a loop to shift the digit letters
for char_digit in range(0, len(digit_letters), 2): # --> Each letter is associated with 2 digits
# Converting the "digits" into numbers
numbers = int(digit_letters[char_digit:char_digit + 2]) # --> Each letter is associated with 2 digits
# Implementing the affine encryption formula
encrypted_num = (a * numbers + b) % 26
# Converting the encrypted numbers into "digits"
if encrypted_num < 10: # --> Each letter is associated with 2 digits, e.g. A = 10, B = 11, C = 12, etc.
# Adding a "0" to the front of the encrypted number to make it 2 digits
encrypted_digits = "0" + str(encrypted_num)
else: # If the encrypted number is greater than 10
encrypted_digits = str(encrypted_num)
# Adding the encrypted digits to the encrypted cipher "numbers"
encrypted_cipher_num += encrypted_digits
# Converting the encrypted cipher "numbers" into letters
cipher_message_encrypted = digits2letters(encrypted_cipher_num)
return cipher_message_encrypted # Returning the encrypted cipher text
Problem 3:
Create a function affineDecrypt(ciphertext, a,b) that returns the cipher text encrypted using key (a, b). You must verify that the gcd(a, 26) = 1. If this is not the case, the function must raise ValueError with message "The given key is invalid. The gcd(a,26) must be 1.". You may NOT use any built-in functions as part of your implementation, but you may use any functions you implemented in previous coding assignments. Please make sure to copy and paste them into this file, so that they are uploaded to CodePost when you submit your ca3.py file.
# Writing a function that outputs a cipher text decrypted using key(a, b)
def affineDecrypt(ciphertext, a, b):
"""decrypts the string 'ciphertext', which was encrypted using an affine transformation key (a, b)
INPUT: ciphertext - a string of encrypted letters
a - integer satisfying gcd(a, 26) = 1.
b - integer
OUTPUT: The decrypted message as a string of characters
"""
# Calling on the gcd() instruction
GCD_calculation = gcd(a, 26)
# Checking if the gcd(a, 26) is not equal to 1
if GCD_calculation != 1:
raise ValueError("The given key is invalid. The gcd(a, 26) must be 1")
else: # When the basic requirements above are met
digit_letters = letters2digits(ciphertext) # Converting the text to "digits"(numbers in string format)
decrypted_message_num = "" # Creating a variable to store the decrypted text
# Writing a loop to shift the digit letters
for char_digit in range(0, len(digit_letters), 2): # --> Each letter is associated with 2 digits
# Converting the "digits" into numbers
numbers = int(digit_letters[char_digit:char_digit + 2]) # --> Each letter is associated with 2 digits
# Implementing the affine decryption formula
decrypted_num = (modinv(a, 26) * (numbers - b)) % 26
# Converting the decrypted numbers into "digits"
if decrypted_num < 10: # --> Each letter is associated with 2 digits, e.g. A = 10, B = 11, C = 12, etc.
# Adding a "0" to the front of the decrypted number to make it 2 digits
decrypted_digits = "0" + str(decrypted_num)
else: # If the decrypted number is greater than 10
decrypted_digits = str(decrypted_num)
# Adding the decrypted digits to the decrypted cipher "numbers"
decrypted_message_num += decrypted_digits
# Converting the decrypted cipher "numbers" into letters
cipher_message_decrypted = digits2letters(decrypted_message_num)
return cipher_message_decrypted # Returning the decrypted cipher text
Problem 4:
Implement the function encryptRSA(m, n, e) which encrypts a string m using RSA key (n = p * q, e). You may NOT use any built-in functions as part of your implementation, but you may use any functions you implemented for previous coding assignments. Please make sure to copy and paste them into this file, so that they are uploaded to CodePost when you submit your pa3.py file.
# Writing a function that encrypts a string using RSA key(n = p * q, e)
def encryptRSA(m, n, e):
"""encrypts the plaintext m, using RSA and the key (n = p * q, e)
INPUT: m - plaintext as a string of letters
n - a positive integer
e - integer satisfying gcd((p-1)*(q-1), e) = 1
OUTPUT: The encrypted message as a string of digits
"""
# Converting the plaintext into digit "numbers"(numbers in string format)
digit_letters = letters2digits(m)
# Create a variable to store the block size
block_size = blocksize(n)
# Writing a while loop if the length of the digit_letters is not a multiple of the block size
while len(digit_letters) % block_size != 0:
# Padding the "digits" with "23"(X) to make it a multiple of the block size
digit_letters += "23"
# Creating a variable to store the "digits" into blocks
unencrypted_blocks = []
# Writing a loop to split the "digits" into blocks
for i in range(0, len(digit_letters), block_size): # --> Each letter is associated with 2 digits
# Converting the "digits" into numbers
numbers = digit_letters[i:i + block_size] # --> Each letter is associated with 2 digits
# Appending the "numbers" to the unencrypted_blocks list
unencrypted_blocks.append(numbers)
encrypted_blocks = [] # Creating a variable to store the encrypted blocks
# Writing a loop to encrypt the blocks
for block in unencrypted_blocks:
message_num = int(block) # Converting the "digits" into numbers
# Implementing the RSA encryption formula
encrypt_RSA_num = str(mod_exp(message_num, e, n)) # --> C = M^e mod n
# Padding the "digits" with "0" to make the length of the "digits" a multiple of the block size
encrypt_RSA_num = encrypt_RSA_num.zfill(block_size)
# Adding the encrypted blocks to the cipher_blocks list
encrypted_blocks.append(encrypt_RSA_num)
# Creating a variable to store the encrypted cipher "numbers"
RSA_encrypted_num = " ".join(encrypted_blocks)
return RSA_encrypted_num # Returning the encrypted cipher text
'''--------------------- ENCRYPTION TESTER CELL ---------------------------'''
"""----------------------- TEST 1 ---------------------------"""
'''
encrypted1 = encryptRSA("STOP", 2537, 13)
encrypted2 = encryptRSA("HELP", 2537, 13)
encrypted3 = encryptRSA("STOPS", 2537, 13)
print("Encrypted Message:", encrypted1)
print("Expected: 2081 2182")
print("Encrypted Message:", encrypted2)
print("Expected: 0981 0461")
print("Encrypted Message:", encrypted3)
print("Expected: 2081 2182 1346")
'''
"""--------------------- TEST 2 ---------------------------"""
'''
encrypted = encryptRSA("UPLOAD", 3233, 17)
print("Encrypted Message:", encrypted)
print("Expected: 2545 2757 1211")
'''
'\nencrypted = encryptRSA("UPLOAD", 3233, 17)\nprint("Encrypted Message:", encrypted)\nprint("Expected: 2545 2757 1211")\n'
Problem 5:
Complete the implementation of the function decryptRSA(c, p, q, m) which depends on modinv(a,m) and the given functions digits2letters(digits) and blockSize(n). When you are done, you can test your function against the given examples.
# Writing a function to output the decrypted message using RSA key(n = p * q, e)
def decryptRSA(c, p, q, e):
"""decrypts the cipher c, which was encrypted using the key (p * q, e)
INPUT: c - ciphertext as a string of digits
p, q - prime numbers used as part of the key n = p * q to encrypt the ciphertext
e - integer satisfying gcd((p-1)*(q-1), e) = 1
OUTPUT: The decrypted message as a string of letters
"""
actual_message = '' # Creating a variable to store the actual message
encrypted_cipher = c.replace(" ", "") # Removing the spaces in the cipher text
n = p * q # Storing the product of the prime numbers as part of the key n = p * q
m = (p - 1) * (q - 1) # Storing the product of (p - 1) and (q - 1)
cipher_length = len(encrypted_cipher) # Storing the length of the encrypted cipher
# Writing a loop for the decrypting the encrypted cipher
for i in range(0, cipher_length, 4):
# Splitting the encrypted cipher into blocks of 4
cipher_blocks = encrypted_cipher[i:i + 4]
# Finding the inverse of e
inverse = modinv(e, m)
# Decrypting the blocks using the RSA decryption formula
cipher_blocks = int(cipher_blocks) ** inverse % n
# Converting the decrypted numbers into string of "digits"
cipher_blocks = str(cipher_blocks)
# Conditional statement to check if the length of the cipher_blocks is less than 4
if len(cipher_blocks) < 4:
# Padding the "digits" with "0" to make the length of the "digits" a multiple of the block size
actual_message += digits2letters('0' + cipher_blocks)
else: # Otherwise printing the decrypted cipher blocks
actual_message += digits2letters(cipher_blocks)
return actual_message # Returning the decrypted cipher text
'''
"""--------------------- TESTER CELL ---------------------------"""
decrypted1 = decryptRSA("2081 2182", 43, 59, 13)
decrypted2 = decryptRSA("0981 0461", 43, 59, 13)
decrypted3 = decryptRSA("2081 2182 1346", 43, 59, 13)
print("Decrypted Message:", decrypted1)
print("Expected: STOP")
print("Decrypted Message:", decrypted2)
print("Expected: HELP")
print("Decrypted Message:", decrypted3)
print("Expected: STOPSX")
"""--------------------- TEST 2---------------------------"""
decrypted = decryptRSA("0667 1947 0671", 43, 59, 13)
print("Decrypted Message:", decrypted)
print("Expected: SILVER")
'''
Decrypted Message: STOP
Expected: STOP
Decrypted Message: HELP
Expected: HELP
Decrypted Message: STOPSX
Expected: STOPSX
Decrypted Message: SILVER
Expected: SILVER
