Cryptography Reference
In-Depth Information
4.11.
The MixColumn transformation of AES consists of a matrix-vector multipli-
cation in the field
GF
(2
8
) with
P
(
x
)=
x
8
+
x
4
+
x
3
+
x
+ 1. Let
b
=(
b
7
x
7
+
...
+
b
0
)
be one of the (four) input bytes to the vector-matrix multiplication. Each input byte
is multiplied with the constants 01, 02 and 03. Your task is to provide exact equa-
tions for computing those three constant multiplications. We denote the result by
d
=(
d
7
x
7
+
...
+
d
0
).
1. Equations for computing the 8 bits of
d
= 01
·
b
.
2. Equations for computing the 8 bits of
d
= 02
·
b
.
3. Equations for computing the 8 bits of
d
= 03
·
b
.
Note:
The AES specification uses “01” to represent the polynomial 1, “02” to rep-
resent the polynomial
x
, and “03” to represent
x
+ 1.
4.12.
We now look at the gate (or bit) complexity of the MixColumn function, using
the results from problem 4.11. We recall from the discussion of stream ciphers that
a 2-input XOR gate performs a
GF
(2) addition.
1. How many 2-input XOR gates are required to perform one constant multiplica-
tion by 01, 02 and 03, respectively, in
GF
(2
8
).
2. What is the overall gate complexity of a hardware implementation of one matrix-
vector multiplication?
3. What is the overall gate complexity of a hardware implementation of the entire
Diffusion layer? We assume permutations require no gates.
4.13.
We consider the first part of the ByteSub operation, i.e, the Galois field inver-
sion.
1. Using Table 4.2, what is the inverse of the bytes 29, F3 and 01, where each byte
is given in hexadecimal notation?
2. Verify your answer by performing a
GF
(2
8
) multiplication with your answer and
the input byte. Note that you have to represent each byte first as polynomials in
GF
(2
8
). The MSB of each byte represents the
x
7
coefficient.
4.14.
Your task is to compute the S-Box, i.e., the ByteSub, values for the input bytes
29, F3 and 01, where each byte is given in hexadecimal notation.
1. First, look up the inverses using Table 4.2 to obtain values
B
. Now, perform the
affine mapping by computing the matrix-vector multiplication and addition.
2. Verify your result using the S-Box Table 4.3.
3. What is the value of
S
(0)?
4.15.
Derive
the bit representation for the following round constants within the key
schedule:
RC
[8]
RC
[9]
RC
[10]
