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