Cryptography Reference
In-Depth Information
⎛
⎝
⎞
⎠
⎛
⎝
⎞
⎠
⎛
⎝
⎞
⎠
C
0
C
1
C
2
C
3
02 03 01 01
01 02 03 01
01 01 02 03
03 01 01 02
B
0
B
5
B
10
B
15
=
.
The second column of output bytes (
C
4
,
C
5
,
C
6
,
C
7
) is computed by multiplying
the four input bytes (
B
4
,
B
9
,
B
14
,
B
3
) by the same constant matrix, and so on. Fig-
ure 4.3 shows which input bytes are used in each of the four MixColumn operations.
We discuss now the details of the vector-matrix multiplication which forms the
MixColum operations. We recall that each state byte
C
i
and
B
i
is an 8-bit value
representing an element from
GF
(2
8
). All arithmetic involving the coefficients is
done in this Galois field. For the constants in the matrix a hexadecimal notation is
used: “01” refers to the
GF
(2
8
) polynomial with the coefficients (0000 0001), i.e., it
is the element 1 of the Galois field; “02” refers to the polynomial with the bit vector
(0000 0010), i.e., to the polynomial
x
; and “03” refers to the polynomial with the bit
vector (0000 0011), i.e., the Galois field element
x
+ 1.
The additions in the vector-matrix multiplication are
GF
(2
8
) additions, that is
simple bitwise XORs of the respective bytes. For the multiplication of the con-
stants, we have to realize multiplications with the constants 01, 02 and 03. These
are quite efficient, and in fact, the three constants were chosen such that software
implementation is easy. Multiplication by 01 is multiplication by the identity and
does not involve any explicit operation. Multiplication by 02 and 03 can be done
through table look-up in two 256-by-8 tables. As an alternative, multiplication by
02 can also be implemented as a multiplication by
x
, which is a left shift by one bit,
and a modular reduction with
P
(
x
)=
x
8
+
x
4
+
x
3
+
x
+ 1. Similarly, multiplication
by 03, which represents the polynomial (
x
+ 1), can be implemented by a left shift
by one bit and addition of the original value followed by a modular reduction with
P
(
x
).
Example 4.11.
We continue with our example from Sect. 4.4.1 and assume that the
input state to the MixColumn layer is
B
=(25
,
25
,...,
25)
.
In this special case, only two multiplications in
GF
(2
8
) have to be done. These are
02
·
25 and 03
·
25, which can be computed in polynomial notation:
(
x
5
+
x
2
+ 1)
=
x
6
+
x
3
+
x
,
02
·
25 =
x
·
(
x
5
+
x
2
+ 1)
=(
x
6
+
x
3
+
x
)+(
x
5
+
x
2
+ 1)
=
x
6
+
x
5
+
x
3
+
x
2
+
x
+ 1
.
03
·
25 =(
x
+ 1)
·
Since both intermediate values have a degree smaller than 8, no modular reduction
with
P
(
x
) is necessary.
The output bytes of
C
result from the following addition in
GF
(2
8
):
