1. [1 point.] Use the Euclidean Algorithm or the Extended Euclidean Algorithm to decrypt the following message written in the affine cipher "11x+16" (multiply by 11 and then add 16):

CABZKQDMN

Show all of the steps.
 
2. [1 point.] The 17 Mar lecture notes give a theorem that gives sufficient conditions for a cryptosystem to achieve perfect secrecy.  Apply that theorem to show that the Shift Cipher achieves perfect secrecy, if each key is used with probability 1/26.  (Hint:  this is a very easy problem.)


For the next two problems, note that a block general substitution cryptosystem is a cipher which works on blocks of n bits.  There is a table which gives a ciphertext block for each of the 2ⁿ possible plaintext blocks.



3. [2 points.] The 17 Mar lecture notes give a formula that approximates the unicity distance of a cryptosystem.
   1. Using that formula and Stirling's formula, derive an estimate the unicity distance of a block general substitution cryptosystem that works on m bits.
   2. Apply your derived formula to give an estimate for the unicity distance when m is 8.  When m is 12.  When m is 16.  When m is 32.  When m is 64.
   
   (Hint:  my answer for m=12 is about 4806.)
    
4. [2 points.] What does the result from the previous problem say about how easy or hard it is to cryptanalyze a block general substitution cipher with block size of just 64 bits?
   Be precise and refer to your answer to the previous question.
   Does your answer depend on the computational resources available for crypanalysis?
    
5. [3 points.] Prove (from scratch, without using the theorem mentioned in problem 2 above) that the Shift Cipher achieves perfect secrecy, if each key is used with probability 1/26.
   
   
6. [8 points.]  The problem from Homework 1 on computing the number of keys for the 2 by 2 Hill cipher turned out to be substantially harder than I thought.  Here is an outline of how you can go about proving it.
   1. Find the number of matrices whose determinant is even because one or both rows are even.
   2. Find the number of matrices whose determinant is even because one or both columns are even.
   3. Find the number of matrices whose determinant is even because all of the entries are odd.
   4. Use inclusion-exclusion to find the total number of matrices whose determinant is even.
   5. Find the number of matrices whose determinant is a multiple of 13 because the first column is a multiple of 13.
   6. Find the number of matrices whose determinant is a multiple of 13 where the first column is not a multiple of 13 but the second column is a multiple of the first modulo 13.
   7. Find the total number of matrices whose determinant is a multiple of 13.
   8. Find the number of matrices whose determinant is a multiple of 26 because they fit case (a) and (e).  (b) and (e).  (c) and (e).  (a) and (f). And so on...
   9. Use inclusion-exclusion to find the total number of matrices whose determinant is neither a multiple of 2 nor a multiple of 13.  You should get 157248.
      
      
7. [4 points.]  Now that you have the number of 2 by 2 Hill cipher keys whose determinant is relatively prime to 26, you can find the number which have determinant 1 as follows:
   1. Let a be a number relatively prime to 26.  Find a 2 by 2 matrix with determinant a.
   2. Show that your matrix has an inverse modulo 26.
   3. Use your matrix to establish a pairing between matrices with determinant 1 and matrices with determinant a.
   4. Now you know that there are the same number of matrices with determinant 1 as there are with determinant a, for every a which is relatively prime to 26.  Find the number of matrices whose determinant is 1.

The following problems are from Chapter 4 of your textbook.

8. [1 point.] Problem 4.9.(a). Use the Euclidean Algorithm.  Show all of the steps.
9. [2 points.] Problem 4.10. Be very complete.
10. [2 points.] Problem 4.11.
11. [4 points.] Problem 4.12. Be very complete.
12. [1 point.] Problem 4.13.(a). Use the Euclidean Algorithm or the Extended Euclidean Algorithm.  Show all of the steps.