DRAFT:� I will finish up the instructions ASAP, but this should get you started.

For the following problems:

 

1.      [4 points]� This problem investigates the Hill cipher.

a.       Using the big-Oh notation, how fast is encoding in a Hill cipher, as a function of the length n of the ciphertext and the dimension m of the key? How about decoding?

b.      Create software that can encode and decode using a Hill cipher.

2.      [4 points]� Create software that can perform a fast known plaintext attack on a Hill cipher, given the dimension m. �How fast are your algorithms, as a function of �?

3.      [1 point, after doing the previous problem]
Same as previous, but without knowing m.

4.      [4 points] This problem investigates the question:

How hard is it to break a Vigenere cipher by brute-force search?

Recall that a Vigenere cipher is �

Recall that brute-force search is �

a.       How many keys are possible in a Vigenere cipher whose key is length m and whose alphabet has 26 letters?

b.      Given a key, how can you tell whether that key is the �right� key?� [Hint:� many answers are possible here.]

c.       Write software that meets the following specification:

                                                   i.      Input:� a string of characters (the ciphertext) and a key length m.

                                                 ii.      Output:� All possible plaintexts �

5.      [8 points] Improve your software from the previous problem to produce the possible plaintexts in order of likelihood.� It would be good if your user interface allowed the user to specify �give me the top 10 possible plaintexts� � It would be good if your software for this part worked for any cipher.

6.      [12 points] Write software to break Vigenere using index of coincidence �

7.      [8 points] Show that a Hill cipher is not susceptible to a single-letter frequency attack.

8.      [1 point]� Students in class suggested two ways to decode a 3x + 2 affine cipher:� table lookup and subtract 2 and divide by 3 (mod 26).� Which is better?� Why?� (Give advantages and disadvantages of each).� Extend your answer to a general ax + b affine cipher.