Midterm Exam -
Problem 1: (a) What is message integrity, and how does a MAC (message authentication code) ensure it?
(b) Draw a diagram that illustrates the way a MAC interacts with a message between Alice and Bob in CBC (cipher block chaining) mode.
Problem 2: What is the GCD of 9774 and 234? Show all work using Euclid's Algorithm. Specifically, show the status after each iteration - you do not need to show computation of remainders.
Problem 3: Consider the private-key ciphers we studied in class (substitution cipher, shift cipher, Vigenere's cipher). Define a chosen-plaintext attack, and explain why the aforementioned ciphers are vulnerable in this attack model. Is the one-time pad vulnerable in this model? The two-time pad (ie, the one-time pad with a re-used pad)? Why or why not?
Problem 4: Prove that 38209001 is not a prime using Fermat's Little Theorem. (Hint: Proceed by contradiction. Assume to the contrary that 38209001 is a prime, and show that this contradicts Fermat's Little Theorem. You may use Wolfram Alpha to compute modular powers.)
Problem 5: (a) Does the set {1, 3} form a group under multiplication modulo 5? Why or why not?
(b) Does the set {1, 6} form a group under multiplication modulo 7? Why or why not?
Problem 6: Answer the following. Fill in the blanks where provided.
(a) What is the identity element in the additive group Zn?
(b) What is the identity element in the multiplicative group Z∗p?
(c) What is the additive inverse of 18 modulo 29? Hint: your answer must be an integer between 0 and 28.
(d) What is the multiplicative inverse of 19 in Z∗23?
Problem 7: (a) Encrypt the following phrase using the Vigenere cipher with the keyword COFFEE:
COLDBREWPLEASE
(b) The Vigenere keyword is CWM and the ciphertext is PWFWNMNHK. What is the message?
Problem 8: We wish to find the multiplicative inverse of 18 in Z∗1491823. Let's follow the following steps:
(a) Use Euclid's Extended Algorithm to find r and s such that
r · 18 + s · 1491823 = 1
Show your work. In other words show the status of the algorithm after each step.
(b) How can you use part (a) to deduce the multiplicative inverse of 18 modulo 1491823?
Problem 9: What is a length extention attack against a MAC and what are ways we could defend against it?
Problem 10: Suppose you have a 50-bit string that contains exactly 37 ones at random positions. How many bits of entropy does this string contain? Show all work.
Problem 11: Write code which implements Euclid's Extended Algorithm. You are to send your code to me via email or Piazza for this problem. If you code does not run, you receive no credit.
I expect you to work independently for problems 1-10, but you may work in a group of up to four students for this problem. Include all group member's names in a readme.txt file in the .zip folder you submit your solution in. Also write your group members' names below (if you are submitting alone, leave blank.)
(1) Self
(2) ____________
(3) ____________
(4) ____________
A sample run of the program would look as follows:
Enter the first number: 192
Enter the second number: 270
The GCD is 6
(u, v) = (-7, 5)