Final Exam, MA 3203 Spring 2022 This exam is due at noon Thursday April 28th. 

At the top of your submission, write your name and your M-number. Your reduced name is not used in this exam. If I speak of the first or second entry of your M-number, I am reading from the left, so the second and third digits of M-number M48305739 is 83. The last digits are the rightmost. You must show all work for any credit. The final answer is not sufficient: justify any claims you make. Numerical calculations may be performed by computer, whether Mathematica or some other tool; if so, include your work either in your submission or as an appendix document. You should verbally justify why you used any such calculations. If I ask for a specific method, you must use that method. Verbal arguments will be compared to standard databases and to other students papers, so use your own words. Do not quote sources directly; any you use should be paraphrased and cited. 1.) Find a primitive root mod p = Prime[r], where r is four digits from the mid- dle of your M-number not starting with zero. You may use the FactorInteger[] command to factor p 1. (Do not use online lists, primitive root calculators, etc. Do the verifying calculations yourself.) 2.) What do we mean when we say a problem is computationally hard? Be rigorous about its complexity compared to the number of bits in the input. Why are such problems important to modern cryptography? 3.) Suppose you want to randomly assign secret keys to a population, and even you do not store them, so you cannot guarantee nonduplication. (A reason for this might be that logging assigned keys could be compared to the time at which people requested keys.) How large should your space of potential keys be to have about a 1% chance of collision if x billion keys are to be assigned, where x is the first two nonzero digits of your M-number? 4.) Alice and Bob will decide an important matter by coin flip, so they agree to use the protocol of Section 13.1. Set it up as follows: let Alice choose primes p and q which are given by Mathematicas Prime[] command, using the first three nonzero digits of your M-number, and the last three. Both of these should be 3 mod 4; if they are not, increment each choice until you find primes that are 3 mod 4. The random integer x that Bob chooses is the last 4 digits of your M-number. Alice then calculates the square roots of y and takes the lowest of the four mod n to send to Bob. Who won? Show your work. 5.) Alice and Bob are using the coin-flipping protocol above, but Eve is execut- ing an intruder-in-the-middle attack and is impersonating each to the other. It would be useful for Eve if they both think they won, at least for a while. (It would create some disorganization and strife between the two.) a.) Can Eve achieve this if she chooses her role (i.e. she chooses primes, or she offers the y) in each flip? How? b.) Alice and Bob both have access to a trusted X.509 authority where they have high assurance certificates on file. Describe a signature procedure that would allow them to use this protocol while preventing Eves attack. Explain in enough detail to show how Eve is prevented from modifying or falsifying the relevant identifying information. You do not need to explain the workings of the cryptosystem used to sign things. 6.) What part of the SET protocol prevents an intruder from intercepting the transaction data and sending a false request to the bank for a nonexistent order from the Cardholder? Be detailed about why the necessary information is inaccessible. 7.) Suppose that in a long transmission, large blocks of data are occasionally interspersed with hashes of the preceding portion. Use the properties of a good hash function to explain why this is useful for detecting errors in transmission. 8.) Here is how bad randomness can cause a weakness in a zero-knowledge identification scheme. Suppose there are 8 pieces of secret information for a licit user, {s1, . . . , s8}, and Eve knows the method of random number generation that V uses. a.) If this is all she knows, what is her chance of passing a single test? What is her chance of passing 10 tests in a row? b.) Suppose that Eve can manipulate the seed, perhaps by timing her re- quests or choosing her x carefully, so that she can reliably guess B in 1/4 of trials and thereby pass. What is her chance of passing 10 tests in a row? (Equiv- alently, about how many tests should she expect to have to run to get a hit?) 9.) One use of classical cryptography principles in the 20th century was the use of codetalkers, Native Americans who transmitted verbal messages in their own language rather than English. A Navajo speaker would spell out some terms letter by letter using Navajo words, with several possibilities for a letter: s for instance might be dibeh, sheep, or klesh, snake. Many military terms were given special equivalents, such as artillery, be-al-doh-tso-lani, meaning many big guns. Common words were replaced by the Navajo language, such as before, bih-tse-dih, or after, bi-kha-di, and the grammatical structure of the English sentence would be replaced with Navajo grammar. How did this system protect communications from decryption? Discuss the protection it offers against ciphertext only analysis, and against known plaintext analysis. (Both contexts are required for full credit on the question.) Assume the following: 1. Foreign codebreakers did not speak Navajo. 2. Messages are being transcribed syllable by syllable. 3. Foreign codebreakers did not have a frequency table for Navajo syllables. 4. Foreign codebreakers do have a frequency table for English letters. 5. Foreign codebreakers are not familiar with Navajo grammar. 6. Codebreakers sometimes do have access to the intended plaintext. 7. Some message plaintexts are repeated regularly but may be encoded dif- ferently.