MA 479 / CSSE 479: Cryptography
Homework 4 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, 2003-2004

All these problems are paper-and-pencil problems. Please do not use a (electronic) computer when doing these problems. Calculators are okay.

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.] Carefully write up your answer to the Exercise from the worksheet from class entitled "A Simplified AES Algorithm". (You did most of this in class.)

  2. [2 points.] Show that the matrix given below, with entries in GF(24), is the inverse of the matrix used in the Mix Columns step of S-AES.
    [ x3+1   x ]
    [ x   x3+1 ]

  3. [6 points.] Carefully write up a complete decryption of the ciphertext 0000 0111 0011 1000, using the key 1010 0111 0011 1011 and the S-AES algorithm. You should get the plaintext we started with in the Exercise from the worksheet from class. Note that the inverse of the S-boxes can be done with a reverse table lookup. The inverse of the Mix Columns step is given by the matrix in the previous problem.

  4. [12 points.] Perform a differential cryptanalysis of one-round S-AES. Use the following plaintext-ciphertext pairs:
    Plaintext   Ciphertext
    0100 1110 0110 1111   0010 0010 0100 1101
    0111 0100 0110 1111   0000 1010 0001 0001
    0100 1101 0111 0010   1101 0101 1101 0000
    0110 1111 0111 0010   1100 0001 0100 1111
    Recover the first nibble of the key. (Let me know if you get stuck; I have further hints.)

  5. [20 points.] Get a description of linear cryptanalysis from me and perform a linear cryptanalysis of one-round S-AES.

  6. [20 points.] Get a description of the "Square Attack" from me and perform a square attack cryptanalysis of four-round S-AES.


    The following problems are from Chapter 4 of your textbook.

  7. [1 point.] Problem 4.17. Completely justify your answer.
  8. [1 point.] Problem 4.18(a). Use the Euclidean Algorithm or the Extended Euclidean Algorithm. Show all steps.
  9. [2 points.] Problem 4.19. Use the Euclidean Algorithm or the Extended Euclidean Algorithm. Show all steps.


    The following problems are from Chapter 5 of your textbook.

  10. [1 point.] Problem 5.2.
  11. [2 points.] Problem 5.3.
  12. [2 points.] Problem 5.4.