Cryptography Reference
In-Depth Information
We now ratchet the complexity level up one notch and consider arithmetic
with polynomials of the form
f
(
x
)=
f
3
x
3
+
f
2
x
2
+
f
1
x
+
f
0
with coefficients
f
i
in
F
2
8
, that is, coefficients that are themselves polynomials. The coefficients
of such polynomials can be represented as fields of four bytes each. Now things
begin to get interesting: While addition of such polynomials
f
(
x
)
and
g
(
x
)
again takes place by means of a bitwise XOR of the coefficients, the product
h
(
x
)=
f
(
x
)
g
(
x
)
is calculated to be
h
(
x
)=
h
6
x
6
+
h
5
x
5
+
h
4
x
4
+
h
3
x
3
+
h
2
x
2
+
h
1
x
+
h
0
,
with coefficients
h
k
:=
i
+
j
=0
f
i
• g
j
, where the summation sign indicates
addition
F
2
8
.
After reduction of
h
(
x
)
by a polynomial of degree 4, one again obtains a
polynomial of degree 3 over
⊕
in
F
2
8
.
For this Rijndael uses the polynomial
M
(
x
):=
x
4
+1
. Usefully,
x
j
mod
M
(
x
)=
x
j
mod4
,sothat
h
(
x
)mod
M
(
x
)
can be easily computed as
d
(
x
):=
f
(
x
)
⊗ g
(
x
):=
h
(
x
)mod
M
(
x
)=
d
3
x
3
+
d
2
x
2
+
d
1
x
+
d
0
,
with
d
0
=
a
0
• b
0
⊕ a
3
• b
1
⊕ a
2
• b
2
⊕ a
1
• b
3
,
d
1
=
a
1
b
3
,
d
2
=
a
2
• b
0
⊕ a
1
• b
1
⊕ a
0
• b
2
⊕ a
3
• b
3
,
d
3
=
a
3
• b
0
⊕ a
2
• b
1
⊕ a
1
• b
2
⊕ a
0
• b
3
.
From this one concludes that the coefficients
d
i
can be computed by matrix
multiplication over
•
b
0
⊕
a
0
•
b
1
⊕
a
3
•
b
2
⊕
a
2
•
F
2
8
:
⎡
⎤
⎡
⎤
⎡
⎤
d
0
d
1
d
2
d
3
a
0
a
3
a
2
a
1
b
0
b
1
b
2
b
3
⎣
⎦
⎣
⎦
·
⎣
⎦
a
1
a
0
a
3
a
2
.
=
(11.1)
a
2
a
1
a
0
a
3
a
3
a
2
a
1
a
0
It is precisely this operation with the constant, invertible modulo
M
(
x
)
,
polynomial
a
(
x
):=
a
3
x
3
+
a
2
x
2
+
a
1
x
+
a
0
over
F
2
8
, with coefficients
a
0
(
x
)=
x
,
a
1
(
x
)=1
,
a
2
(
x
)=1
,and
a
3
(
x
)=
x
+1
, that is executed in the
so-called
MixColumns
transformation, which constitutes a principal component
of the round transformations of Rijndael.
11.2 The Rijndael Algorithm
Rijndael is a symmetric block encryption algorithm with variable block and key
lengths. It can process blocks of 128, 192, and 256 bits and keys of the same
lengths, where all combinations of block and key lengths are possible. The
accepted key lengths correspond to the guidelines for AES, though the “official”
