Cryptography Reference
In-Depth Information
MixColumns() Transformation
The MixColumns() transformation operates on each column of the State individu-
ally. This means that the transformation is repeated four times (once for each column
of the State). More specifically, we consider the four bytes
s
0
,c
,s
1
,c
,s
2
,c
,and
s
3
,c
of column
c
(0
c<
4) of the State, denoted by
s
0
,s
1
,s
2
,and
s
3
(the column
number is omitted for clarity in exposition), and we use these bytes to represent the
coefficients of a four-term polynomial
≤
s
(
x
)=
s
3
x
3
+
s
2
x
2
+
s
1
x
+
s
0
over
F
2
8
. In a short representation,
s
(
x
) can also be written as [
s
0
,s
1
,s
2
,s
3
].
Because the coefficients of
s
(
x
) are bytes (i.e., elements of
F
2
8
), the polynomial
s
(
x
) is over
F
2
8
, and hence it is not an element of the AES field.
Against this background, the MixColumns() transformation on a column is
defined by multiplying the corresponding column polynomial
s
(
x
) with a fixed
polynomial
c
(
x
) of degree 3. Again, a polynomial is used to reduce the product
and to make sure that the resulting polynomial is of degree 3. The fixed polynomial
c
(
x
) is
c
(
x
)=
c
3
x
3
+
c
2
x
2
+
c
1
x
+
c
0
with
c
3
=
0x03
(i.e.,
{
00000011
}
),
c
2
=
0x01
(i.e.,
{
00000001
}
),
c
1
=
0x01
(i.e.,
{
), and the polynomial to reduce the
product is
x
4
+1. Note that this polynomial is reducible in
00000001
}
), and
c
0
=
0x02
(i.e.,
{
00000010
}
F
2
(i.e.,
x
4
+1 = (
x
+1)
4
)
and that the only reason for the multiplication being performed modulo
x
4
+1is to
make sure that the operation outputs a polynomial of degree 3 at most (i.e., to achieve
a transformation from a value that matches into a column to another value that also
matches into a column).
In essence, the MixColumns() transformation maps
s
(
x
) to the following
polynomial:
s
(
x
)(mod
x
4
+1)
c
(
x
)
·
Alternatively speaking, the MixColumns() transformation can also be achieved
by implementing the following linear algebraic transformation for each column
c
(0
≤
c<
4):
