1. What information (or data) is stored in each puzzle?
   A random key, a sequence number, and in our example enough redundant bits (such as a long string of 0's) to easily identify the broken puzzle.
2. What does Alice do with all the puzzles?
   Alice picks a puzzle at random. (They have been sent in random order.) She breaks this one puzzle, retrieves the key and sequence number, and sends the sequence number back to Bob.
3. What does Bob do in response to what Alice does?
   Bob uses the sequence number that Alice openly sent to retrieve the corresponding key, which Alice also has.
4. Why is it hard for Boris to get the same information that Alice and Bob have in common?
   Boris doesn't know which puzzle Alice chose, so he has to break half of them on the average until he knows the secret key Alice and Bob are using.

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?)

   As equations, encryption takes the form:
   setRnd(seed); c = rnd() xor m;
   transmit c openly, and seed securely;

   Decryption takes the form:
   receive seed securely and c openly;
   setRnd(seed); m = rnd() xor c;
   

2. What does CBC stand for?
   Cipher Block Chaining
3. Give a significant disadvantage that the system in a. would have that is not present when the CBC mode is used.
   See notes or the Handbook.

1. State Fermat's Theorem.
   For a not 0 and p a prime, a^p-1 mod p = 1.
2. Use the theorem to simplify the expression 9¹¹¹ mod 13.
   = 9^{(111 mod 12)} mod 13
   = 9³ mod 13 = 729 mod 13 = 1
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?
   If a^n-1 mod n is NOT 1 for some non-zero a, then n is definitely not a prime. However, this method doesn't always work, because there are numbers (Carmichael numbers) such that the equations works out to 1 for every a, yet still they are not prime.

1. What are the information words (or source words)?
   Pick a block size n, and the source words are all 2ⁿ strings of n 0's and 1's.
2. What are the code words?
   Pick a length m greater than n, and for each source word choose a random bit string of length m as the corresponding code word. For the binary symmetric channel, the code words must be at least n/C long, where C is Shannon's channel capacity. If one wants to transmit a source word, one transmits the longer code word instead.
3. Given a transmitted code word with errors introduced in the channel, say briefly how it is decoded.
   On receipt of a code word, with assumed errors, one searches all code words for the code word differing from the transmitted code word in the smallest number of bit positions (Hamming distance). The corresponding source word is then taken as what was originally transmitted. Of course this method doesn't always work. A give random code could be anything at all, but Shannon showed that the average over all codes has to satisfy his theorem, so therefore there is a code that satisfies it also.

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;
}

z * xy = XY

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

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?
The proof of the invariance after the two statements inside the inner while loop requires that one know the value of y is even. However, in this case, even though y is odd, the proof of invariance does not rely on y being odd.

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;
}

d. Do you think this version of exp is of any use?
This latter version takes Y many steps, whereas the earlier version takes at most log₂Y many steps (which are more complicated), a very much faster algorithm for large Y. This simpler algorithm is useless for cryptography and other similar applications because it is far too slow, but the algorithm is useful for small Y and for educational purposes (as here). Thus this question doesn't have a simple yes or no answer.