Description
Ex. 1 — Finite fields
1. Show that X
2 + 1 is irreducible in F3[X].
2. Why does the multiplicative inverse of 1 + 2X mod X
2 + 1 exist in F3[X]?
3. Find the multiplicative inverse of 1 + 2X mod X
2 + 1, in F3[X].
Ex. 2 — AES
The goal of this exercise is to reshape the decryption of AES such that it has the same structure as
encryption.
1. First we determine the inverse of each layer.
a) Describe InvShiftRows the inverse operation of ShiftRows.
b) What is the inverse of the layer AddRoundKey?
c) Explain why the transformation InvMixColumns is given by the multiplication by the matrix
00001110 00001011 00001101 00001001
00001001 00001110 00001011 00001101
00001101 00001001 00001110 00001011
00001011 00001101 00001001 00001110
.
We call InvSubBytes the lookup table inverse of SubBytes.
2. Describe the decryption process using the previous transformations.
3. Why can InvShiftRows and InvSubBytes be applied on reverse order?
4. Similarly we want to inverse the order of application of AddRoundKey and InvMixColumns.
a) Why is it not possible to reverse the order of application of AddRoundKey and InvMixColumns?
b) Calling the initial matrix (ai,j ), the MixColumns matrix (mi,j ), and the AddRoundKey matrix
(ki,j ), what is the result of applying first MixColumns and then AddRoundKey?
c) Show that the inverse operation is given by
(ei,j ) → (mi,j )
−1
(ei,j ) ⊕ (mi,j )
−1
(ki,j ).
d) Define a new operations InvAddRoundKey such that “AddRounKey then InvMixColumns”
can be replaced by “InvMixColumns then InvAddRoundKey”.
5. Conclude on how to process the decryption.
6. What are the advantages of this strategy over simply reversing the order of application of the
transformations?
Ex. 3 — DES
1. Research and explain how the DES cryptosystem works.
2. Quickly explain linear and differential cryptanalysis.
3. What is triple DES and why was it used instead of double DES?
4. Explain how passwords are stored on Unix systems? Is it a problem?
Hint: check man passwd and then follow the suggested man pages
Ex. 4 — Programming
In the AES, choose two layers to implement in C. The 128 bits should be looked at as an unsigned
char pointer. Operations should be implemented using logical operators (and, or, and xor).
A bonus will be given for each extra layer implemented, and the generation of the S-Box. A big bonus
will reward a complete implementation of the AES.
