You may turn these problems in electronically to the drop boxes or on paper. If you do your problems electronically, please use a proper equation editor rather than trying to fake the mathematical symbols!

Drop box submissions are due at midnight on the due date. Paper submissions are due in class or in the box outside my office by 5:00 p.m.

Show your work on all problems.

I will give some partial credit, especially on multi-part problems.

1. [2 points.] Give an example of an S-box that you could use with S-DES that has the following properties: 1) You could encrypt and decrypt with it, i.e. the operation of S-DES would remain reversible, but 2) the operation of S-DES would not be cryptographically secure. Explain carefully how you could attack your S-box and/or what important functions of an S-box are not present in your S-box. (You may use the same S-box for S0 and S1 if you want.)

2. [2 points.] Repeat the previous exercise with another S-box which is different in some non-trivial way. (If you are not sure if your new S-box is non-trivially different, please ask.)

3. [2 points.] Consider the differential cryptanalysis of one-round S-DES. Suppose that each plaintext-ciphertext pair gives you 4 possible values of the left half of K₁. (This is not really true; see the next problem.) What is the maximum number of plaintext-ciphertext pairs that you could try without narrowing down the left half of the key to exactly one choice? You may assume that two different plaintext-ciphertext pairs will not give you exactly the same set of 4 possible values. (This is not really true either.)

   Hint: Notice that the correct key will be contained in every possible set of values, so you can disregard it. The question therefore boils down to how many three-element sets can you choose so that the intersection of all of the sets has at least one element (the incorrect key which you cannot yet eliminate).

4. [2 points.] Consider the previous problem again, but now consider the right half of K₁. Now some plaintext-ciphertext pairs give you 3 or 5 possible half-keys, instead of 4. What is the maximum number of plaintext-ciphertext pairs that you could try without narrowing down the right half of the key to exactly one choice? You may need to figure out how many pairs result in 3 possible values, how many result in 4, and how many result in 5.

   
   The following problems are from the worksheet from class entitled "Differential Cryptanalysis, An Exercise".

5. [3 points.] Answer question 5 of the worksheet. You will probably want to consider the previous two problems.
6. [3 points.] Carefully write up your answers to questions 1-4 and 6 of the worksheet. (You did this in class.)
7. [2 points.] Answer questions 8-10 of the worksheet.
8. [6 points.] Answer questions 11-12 of the worksheet.
9. [6 points.] Answer question 13 of the worksheet.

   
   The following problems are from Chapter 3 of your textbook.

10. [2 points.] Problem 3.1. Explain your answer carefully.
11. [2 points.] Problem 3.5. You will want to use a result from your DISCO class on fixed points of permutations.
12. [2 points.] Problem 3.9. Be complete.
13. [2 points.] Problem 3.10.
14. [2 points.] Problem 3.12.
15. [4 points.] Problem 3.13. (Hint for part (b): show that a chosen plaintext attack can do a little better than looking at all 256 keys.)
16. [4 points.] Problems 3.15 and 3.16.