Note: The final changes to this homework were made on Friday, 2003-04-18 at 09:47:00.

1. Cryptograms (see Chapter 9):
   1. How many possible keys are there for a cryptogram?
      

   2. As a power of 10, your answer to part a should be: 4.0329 x 10²⁶

      How many bits are needed to represent this number? (You must show how you get your answer, not just "from a calculator".)
      

   3. What simple change could one make to a cryptgram and have a resulting system that is arbitrarily hard to break? (Not just leaving out blanks, and not somehow trying to turn it into a one-time pad. The answer is in Chapter 9.4.)
      

   4. Why is a cryptosystem no good if it has just a small number of possible keys?
      

   5. Assume the same key is used repeatedly for cryptograms. How effective is a ciphertext only attack in this case? (See section 11.2.) How about a known plaintext attack? How about a chosen plaintext attack?

2. Beale Cipher and One-time pad (see Chapter 10):
   1. What is the main difference between the Beale cipher and the one-time pad (that is, the version of the one-time pad given in Section 10.3).
      

   2. Use the random pad characters UJXPBRTM to encrypt up to 8 characters of your own last name. Show your work, including the resulting ciphertext and the decryption. What is the key for decryption?

3. Cipher Block Chaining (see Chapter 11):
   1. Referring to Figure 11.1 in Chapter 11, give equations showing encryption and decryption in this mode, using plaintext blocks P₁, P₂, P₃, ..., ciphertext blocks C₁, C₂, C₃, ..., and IV = C₀.

4. The RSA Cryptosystem (see Chapter 14):
   Consider an ultimate "toy" system using p = 5 and q = 11 and exponent e = 3.
   1. Why wouldn't p = 7 or p = 12 work as one of the primes?

   2. Corresponding to encryption exponent e = 3, find the decryption exponent d.
      

   3. Using the same system, show what calculations would be needed to use the Chinese Remainder Theorem for decryption. (Just show the powers needed using which mods.)

5. Rabin's Cryptosystem (see Chapter 15):
   Use Rabin with a modulus of 77.
   
   1. What would be wrong with a modulus of 55?

   2. How would you encrypt the message 6 (assuming you use modulus 77)? What is the ciphertext?

   3. How would you decrypt this message? What special problem do you face, one not present with RSA?

6. Pseudo-random Numbers (see Chapter 16):
   1. What is the most important property of the multiplier in a linear congruence generator? [Hint: Why is a multiplier of 2 modulo 13 better than a multiplier of 5 modulo 13?]
      

7. Advanced Encryption Standard (see Part VI):
   1. Suppose you use AES to encryption one block with a 128-bit key. Say exactly how many times each of the following subparts is executed: AddRoundKey, SubBytes, ShiftRows, MixColumns, and KeyExpansion.

   2. In outline form, explain how the key is handled (without details of key expansion).
      

   3. Write down the LAST TWO DIGITS (rightmost) of your SSN. (If the leftmost of these two digits is a 0, then you should use a 6 for this digit. Thus replace 0y by 6y, where y is the rightmost digit.) Interpret these as hex digits, and the pair as an element of GF(256). Let 0x5a be another element. Use polynomial multiplication and long division by the special irreducible polynomial m(x) = 0x11b to find the product of these two elements in GF(256). (You must show your work for credit.)

   4. Do the same product in GF(256) as in the previous part using the "logs" and "exponentials" as in Section 19.7. (Again you must show your work. Of course you should get the same answer as before.)

8. Threshold Schemes (see Chapter 28):
   1. Using a (3, 5) threshold scheme and a prime p = 13, suppose three of the shares are (4,5), (2,10), and (3,2). Use the formulas from the "Handbook" to recover the "secret". (The calculation is not trivial, but it's fairly easy.)

9. Zero knowledge proofs:
   1. Find a way to prove to someone that you know how to factor a number n that is the product of two primes p and q, without revealing what the two primes are. This should be done without using any third party. [Hint: this is actually easy if you think about the RSA cryptosystem.]