CMPUT 101 Assignment 2

• Your code must be easy-to-read with descriptive variable names and good use of spacing. • Above each program or function, comments must be provided on how your program/function works. Comments must also be provided inside the program/subroutine to explain the code where needed. There are marks for commenting your programs. • You must test your programs using the lab machines to make sure they work before submitting them. Leave the final copy of your program on your CS account in case there are problems with your submission. • You must submit each program as a separate .py file. • Should you need to consult with other students, you must follow the Consultation Policy on the course website. 1. (10 marks) Give the Python program to reduce a fraction (proper or improper) to its lowest terms, i.e. remove all common factors between the numerator and the denominator. A proper fraction is a fraction in which the numerator is less than the denominator while an improper fraction is a fraction in which the numerator is larger than or equal to the denominator. Some examples are given below: Input Output Remarks 4 16 1 4 Proper fraction. The fraction is reduced so that the numerator and the denominator do not have any common factors. 3 2 1 1 2 Improper fraction 65 15 4 1 3 Improper fraction. The final result also has the fraction reduced to remove all common factors between the numerator and the denominator. The input is the numerator and denominator of the fraction. Some sample outputs of running the program are given below: Input the numerator and denominator :3 2 3/2 is equal to 1 1/2 Input the numerator and denominator :3 4 3/4 is equal to 3/4 Input the numerator and denominator :120 35 120/35 is equal to 3 3/7 2. Excursion into Encryption. You may have heard of the Enigma machine, which was used by the Germans to transmit secret messages during the Second World War. Finding a method of deciphering these secret messages contributed to winning the war by Allied Forces. One of the leading figures in deciphering the secret messages was Alan Turing, the father of Computing Science. In this exercise, you are asked to give the Python program to decipher a secret text file with the filename encryptOriginal.txt. It is known that the file was encrypted using the XOR method, which is explained below. Given c and k as variables, XOR(c,k) is c & ˜k|˜c&k, where ˜denotes negation, & bitwise AND and | bitwise OR in Python for logical operations on integers (see an example below). One interesting property of XOR is that applying XOR with the key once will encrypt the input value and applying XOR again with the same key will decrypt it. In other words, c is equal to XOR(XOR(c,k),k) irrespective of the value of c. It is because of this property, we can use it to do encryption. For example, 0C0 = 67 = 01000011 0a0 = 97 = 01100001 XOR(67,97) = 00100010 XOR(XOR(67,97),97) = 01000011 =0 C0 In a typical English text file, the characters are encoded using ASCII, which stands for American Standard Code for Information Interchange. Every character has a unique code. In the above example, the letter ‘a’ has the code value of 97; while the letter ‘C’ is 67. Hence, a piece of text can be encrypted using the above mentioned XOR method. To simplify discussion, k is referred to as the key. In this example, we pick one character as the key, e.g. k= ‘a’. Suppose the message we want to encrypt is the string ‘CMPUT 101’. If we apply the above XOR method using ‘a’ as the key, then the encrypted output is shown below: Input C M P U T 1 0 1 ASCII code 67 77 80 85 84 32 49 48 49 key 97 97 97 97 97 97 97 97 97 XOR 34 44 49 52 53 65 80 81 80 Output ” , 1 4 5 A P Q P The ASCII code of a character can be obtained using the Python function ord, e.g. ord(‘C’) gives 67. It can be converted back by using the Python function chr, e.g. chr(67) gives ‘C’. Each entry in the first row shows the input character. The second row shows the corresponding ASCII code value. The third row shows the ASCII code value of the key. The fourth row shows the corresponding value after the XOR operation. For example, XOR(67,97) is 34. The last row shows the corresponding ASCII character of the output. Note: Not all code values can be printed. The example given just happens to have all output codes printable. The above method can be extended to make decrypting more difficult. Instead of using one character for the key, we can use 3 characters for the key, e.g. ‘abc’. Then we encode the first character (‘C’) in the input message using ‘a’, the second (‘M’) using ‘b’, and the third (‘P’) using ‘c’. Then this process is repeated with the fourth character (‘U’) using ‘a’ again. As an example, using ‘abc’ as the key, then the encrypted output of ‘CMPUT 101’ in code value is shown below: Input C M P U T 1 0 1 ASCII code 67 77 80 85 84 32 49 48 49 key 97 98 99 97 98 99 97 98 99 XOR 34 47 51 52 54 67 80 82 82 Output ” / 3 4 6 C P R R You will solve this problem in a series of steps. Note, .py files are provided for each of these. (a) (1 mark) Give the Python function XOR(a,b) that returns the XOR(a,b) where a and b are integers. Submit a complete Python program that uses XOR in file xor.py. (b) (3 marks) Give the Python function encrypt1(key,ar) that uses XOR to encrypt a string ar using key, where key is a single character, say, ‘a’. Submit a complete Python program that uses encrypt1 in encrypt1.py. Your program should ask for the key and output in the shell the encrypted result. Since the same method is used in decrypting the encrypted string, your program should also output the decrypted string. A sample run of the program with the input string = ‘CMPUT 101’ is shown below: Input string = CMPUT 101 key = a Encrypted string = ",145APQP Decrypted string = CMPUT 101 (c) (3 marks) Extend the above encrypt1 function to encrypt2(key,ar), where the key is three characters. Submit a complete Python program encrypt2.py that uses encrypt2. Your program should ask for the key and output in the shell the encrypted result. Since the same method is used in decrypting the encrypted string, your program should also output the decrypted string. A sample run of the program with the input string = ‘CMPUT 101’ is shown below: Input string = CMPUT 101 key = abc Encrypted string = "/346CPRR Decrypted string = CMPUT 101 (d) (3 marks) In this problem, the encrypted file encryptOriginal.txt is known to be encrypted using the XOR method. It is also known that the key has 3 characters, which are ‘a’,‘e’, and ‘i’. However, the order by which these characters are arranged is unknown. Your are to provide the Python program to read the text from an encrypted text file and a key and output the decrypted text into another file. Since there are only 6 possible orderings, it is relatively simple to use the program to find the key that outputs the correct decrypted text. The file manipulation functions are provided for you in encrypt3.py. Submit the following: i. The key that you discovered to decrypt the file. ii. A commented Python program that will accept the key and read the text from the given file. To simplify the task for the TA to run your program, please hardcode the filename encryptOriginal.txt iii. The decrypted text file - use the filename decrypted.txt. Marking Scheme: 1. Question 1 (a) 2 marks for comments and readability (b) 3 marks for code (c) 5 marks for producing correct results 2. Question 2 (a) 1 mark for correct results - XOR (b) 1 mark for comments and code, 2 marks for correct results (c) 1 mark for comments and code, 2 marks for correct results (d) 1 mark for the correct key, 2 marks for the correct decrypted text.