CMPUT 101 Assignment 2

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 ﬁnal 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 ﬁgures 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 ﬁle with the ﬁlename encryptOriginal.txt. It is known that the ﬁle 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 ﬁle, 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 ﬁrst 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 diﬃcult. Instead of using one character for the key, we can use 3 characters for the key, e.g. ‘abc’. Then we encode the ﬁrst 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 ﬁles 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 ﬁle 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 ﬁle 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 ﬁle and a key and output the decrypted text into another ﬁle. Since there are only 6 possible orderings, it is relatively simple to use the program to ﬁnd the key that outputs the correct decrypted text. The ﬁle manipulation functions are provided for you in encrypt3.py. Submit the following: i. The key that you discovered to decrypt the ﬁle. ii. A commented Python program that will accept the key and read the text from the given ﬁle. To simplify the task for the TA to run your program, please hardcode the ﬁlename encryptOriginal.txt iii. The decrypted text ﬁle - use the ﬁlename 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.