MA 479 / CSSE 490: Cryptography
Homework 3 problems inspired by Mathematics

Rose-Hulman Institute of Technology
A joint effort of the
Department of Mathematics
and the Department of Computer Science & Software Engineering
Spring term, 2002-2003

All these problems are paper-and-pencil problems. You will probably not find a computer program helpful on these problems. Show all steps of your work. I will give some partial credit, esepcially on multi-part problems.
  1. [1 point.] 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. [1 point.] 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 K1. (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. [3 points.] Consider the previous problem again, but now consider the right half of K1. 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 Chapter 3 of your textbook.

  5. [2 points.] Problem 3.1. Explain your answer carefully.
  6. [1 point.] Problem 3.5. You will want to use a result from your DISCO class on fixed points of permutations.
  7. [2 points.] Problem 3.7. Show all steps. (Note that there is a typo in the problem: the binary notation for hexidecimal C should be 1100, not 0100.)
  8. [2 points.] Problem 3.9. Be complete.
  9. [2 points.] Problem 3.10.
  10. [1 point.] Problem 3.12.
  11. [3 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.)