Problem 1:

Imagine you are a hacker trying to read encrypted messages exchanged between the professor and the grader for this class. They are exchanging messages not very securely by generating a key using the Diffie-Hellman algorithm and offsetting each character by this amount. You see the professor send a prime and a primitive root unencrypted: he is using [tex]p = 127[/tex] and [tex]g = 3[/tex] as a primitive root mod [tex]p[/tex]. The professor transmits the number [tex]A = 77[/tex]. The grader transmits the number [tex]B = 29[/tex].

a) First, you must figure out the professor's secret number [tex]z[/tex]. What is it? Explain how you found out. (Because the prime [tex]p[/tex] is not very big, you can solve the discrete logarithm problem fairly fast by brute force, so the key exchange is not very secure. You may find it convenient to write a short program to do this.)

b) Based on [tex]x[/tex], you can figure out the shared secret key [tex]K[/tex]. What is it? (Use your exponentiation code from last week.)

c) The message was encrypted as follows. The professor took the message and converted each letter into a two-digit number, using the table on the last page. He then added [tex]K[/tex] to each of the numbers and took the result mod 26. Finally, he stuck all the numbers together into a string. For example, with [tex]K = 16[/tex] and the message "TESTMESSAGE", this would go:

"TESTMESSAGE" → [20, 05, 19, 20, 13, 05, 19, 19, 01, 07, 05] → [10, 21, 09, 10, 03, 21, 09, 09, 17, 23, 21] → 1021091003210909172321