### Written Homework 2

```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 will not accept sheets with curly edges ripped from spiral-bound notebooks, or multi-sheet handins
that are not stapled.
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,
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
```