Directions: Use your own paper for answers. When you are done you may keep this exam sheet. The answers will be posted.

1. What is wrong with using a 16-bit random number generator to generate 128-bit cryptographic keys, by calling the generator 8 times to get the needed 128 bits? (Why is this always bad?)

   ---

2. This problem is concerned with Merkle's "puzzle" method of key distribution. Suppose Alice and Bob want to end up with a a cryptographic key in common, after communicating in public, with Boris listening in. Bob sends Alice a large number of "puzzles", that is, ways of sending information in a package that can be broken open with a fixed amount of execution time.
   1. What information (or data) is stored in each puzzle?
   2. What does Alice do with all the puzzles?
   3. What does Bob do in response to what Alice does?
   4. Why is it hard for Boris to get the same information that Alice and Bob have in common?

   ---

3. Suppose one has a random number generator rnd that returns 128 random bits each time it is called (say as an array of 16 bytes). There is also a function setRnd that takes 128 bits as input to work as a seed.
   1. Show with equations or with a diagram (or both), how one can use exclusive-or to turn this into a cryptosystem. (Assuming a 128-bit message m, how does one form the ciphertext and how does one decrypt?)
   2. What does CBC stand for?
   3. Give a significant disadvantage that the system in a. would have that is not present when the CBC mode is used.

   ---

4. This is a question about Fermat's Theorem and its use.
   1. State Fermat's Theorem.
   2. Use the theorem to simplify the expression 9¹¹¹ mod 13.
   3. How can Fermat's theorem be used to prove (with certainty) that a number is not prime? Will this method work for any non-prime?

   ---

5. Consider the random codes that are used to prove Shannon's noisy coding theorem.
   1. What are the information words (or source words)?
   2. What are the code words?
   3. Given a transmitted code word with errors introduced in the channel, say briefly how it is decoded.

    

    

    

    

6. This problem is concerned with the following exp algorithm from the notes and discussed in class:

   
   int exp(int X, int Y) {
      int x = X, y = Y, z = 1;
      while (y > 0) {
         while (y%2 == 0) {
            x = x*x;
            y = y/2;
         }
         z = z*x;
         y = y - 1;
      }
      return z;
   }
   

   Suppose one knows that the following equation is true, for integer variables x, y, z, X, and Y, and = is the mathematical equals:

   
   z * xy = XY
   

   and suppose the following 2 assignment statements are executed, where = is assignment:

   
   z = z * x;
   y = y - 1;
   

   a. Prove that the equation remains true (remains invariant) after the two assignments are executed.

   b. At the point in the above algorithm just before the two assignments statements, it is also true that y%2 is not zero, that is, y is odd. Is this needed for the proof of invariance?

   In light of the above two parts, consider the following C, C++, or Java function?

   
   int exp(int X, int Y) {
      int x = X, y = Y, z = 1;
      while (y > 0) {
         z = z*x;
         y = y - 1;
      }
      return z;
   }
   

   c. Do you think this second function will correctly calculate X^Y ?

   d. Do you think this version of exp is of any use?