CS1800 (HON) Discrete Structures Fall 2014 Prof. Fell September 19, 2014 Written Homework 02 (Honors) Assigned: Due: Wed 19 Sep 2014 Wed 1 Oct 2014 Instructions: • The assignment is due at the beginning of class on the due date specified. Late assignments will be penalized 10 points per day (or fraction thereof). Late assignments will not be accepted after the solutions have been distributed. • We expect that you will study with friends and often work out problem solutions together; however, you must write up you own solutions, in your own words. Cheating will not be tolerated. • We expect your homework to be neat, organized, and legible. If your handwriting is unreadable, please type your solutions. • We will not accept sheets with curly edges ripped from spiral-bound notebooks, or multi-sheet handins that are not stapled. • Please write your name and recitation number on the first sheet of your handin. Problem 1 [40 pts (6,7,7,7,7,6)]: Cryptography. A spy has been captured, but all attempts to interrogate him have failed: he speaks a very strange language, unintelligible to any translator. However, this spy was caught with a number of documents. Linguists who have studied these documents believe that they were written in the spy’s language, but that they have been encrypted. Decrypting these documents to obtain valid text in the spy’s language would be incredibly helpful; your job is to decrypt the spy’s documents and hopefully determine where he’s from and what language he speaks. Linguists analyzing the spy’s documents have determined that the spy’s language consists of 26 linguistic units (analogous to English letters), where each unit consists of one or more case-sensitive English letters or punctuation marks. The units of the spy’s language, numbered from 0 to 25, are given below. 0 a 13 o 1 b 14 p 2 ch 15 q 3 D 16 Q 4 e 17 r 5 gh 18 S 6 H 19 t 7 I 20 tlh 8 j 21 u 9 l 22 v 10 m 23 w 11 n 24 y 12 ng 25 ’ You suspect that the spy has used a linear encryption scheme with m = 15 and k = 3 since symbols representing these values were found tattooed on the spy’s scalp. Finally, the linguists and interrogators are particularly interested in following phrase, which was written on the top of each document the spy possessed: 1 rebDng wDq lDghjDp i. Parse the phrase above to obtain the individual linguistic units of the spy’s language, i.e., “r” followed by “e” followed by “b” and so on. Note the multi-letter combinations which correspond to individual linguistic units. ii. Encode each linguistic unit with its corresponding number from the table given above, e.g., r → 17 and so on. iii. Since you suspect that these values were encrypted using the function a → (15 · a + 3) mod 26 you must subtract 3 and then multiply by the multiplicative inverse of 15 (mod 26) in order to decrypt these values. Start by determining the multiplicative inverse of 15 (mod 26). iv. Decrypt each value by inverting the linear encryption. v. Decode these values using the table given above to obtain a phrase in the spy’s language. (It will not be intelligible to most people.) vi. Conduct some research on the web to see if you can determine what this phrase means. (Try typing the decrypted words or the entire phrase into Google.) What is the English translation of this phrase? Where does our spy come from and what language does he speak? Problem 2 [20 pts; (5,10,5)]: Mod Multiplication Patterns i. List all natural numbers less than 18 that are relatively prime to 18 (i.e., those natural numbers that do not share a common factor with 18). ii. Construct the multiplication table, mod 18, for only the numbers that you obtained in your solution to part i. That is, the row headers and the column headers of the table should include precisely the numbers you obtained in your solution to part i. iii. Discuss any patterns you see in the multiplication table and why they occur. Problem 3 [20 pts]: The RSA cryptosystem You have just successfully deciphered a collection of important documents in a strange language, thanks to a mastery of modular arithmetic, and are enjoying a well-deserved vacation in the Carribean. Alas, your reverie on the beach is short-lived and you are called to decipher what appears to be an even more important message. This is a message sent by one of the spies in your own unit, who is suspected of being a mole (foreign agent). This message has been encrypted using the RSA cryptosystem. You are told that in the RSA system being used, n = 391, and the public key exponent e = 7. You suspect that the message being exchanged is in English, using the standard encoding of letters to the numbers from 0 to 25, and with 26 used for space (no other punctuation marks are being used). 2 Thus, for instance, the message “HEY” will be encrypted as follows. The letter H corresponds to 7, and 77 mod 391 equals 97. The letter E corresponds to 4, and 47 mod 391 equals 353. The letter Y corresponds to 24, and 247 mod 391 equals 369. So the message “HEY”, when encrypted, reads as follows. 97 353 369 The message that you need to decrypt reads as follows. 371 295 2 195 0 383 52 Decrypt the above message. You may use a calculator, Microsoft Excel, or write a program to compute these values. Show your work. What is the private key of this RSA cryptosystem? Problem 4 [20 pts; (5 each)]: An Alternative GCD Algorithm Euclid’s algorithm computes the gcd of two positive numbers a and b (a ≥ b) by reducing the problem to that of computing the gcd of b and (a mod b), where a mod b is often much smaller than a. Thus the algorithm rapidly converges to the final result. While the calculation of a mod b is not hard, it requires division and may be more expensive to do on some very simple computing devices. In the world of binary arithmetic, division by 2 is much easier to compute. Consider the following alternative algorithm for gcd using subtraction and division by 2, developed below through a series of exercises. i. Show that if a and b are both even, then gcd(a, b) = 2 · gcd(a/2, b/2). ii. Show that if a is even and b is odd, then gcd(a, b) = gcd(a/2, b). (Similarly, if a is odd and b is even, then gcd(a, b) = gcd(a, b/2).) iii. Show that if a and b are both odd, then gcd(a, b) = gcd((a − b)/2, b). Hint: Show that gcd(a, b) = gcd(a − b, b); for inspiration, see the proof of correctness for the Euclidean Algorithm given in the text. If a and b are both odd, what is true about a − b? Now apply your result from part ii above. . . iv. Apply the above three claims repeatedly to compute gcd(246, 72). Show your work. 3