Cryptography Reference
In-Depth Information
multiplication is achieved by multiplying polynomials over
Z
2
modulo an
irreducible polynomial of degree 8. In the case of the AES, the irreducible
polynomial is
f
(
x
)=
x
8
+
x
4
+
x
3
+
x
+1
.
The modular reduction by
f
(
x
) ensures that the result is a binary polynomial
of degree less than 8 and—according to (10.4)—that it can hence be repre-
sented in a single byte. Note that the multiplication is associative and that
the polynomial 1 (i.e.,
or
0x01
in the byte representation) is the
multiplicative identity element for the multiplication operation.
{
00000001
}
Remember from Section 3.3.6 that
Z
2
[
x
]
f
is a field if
f
(
x
) is an irreducible
polynomial over
Z
2
. In the case of the AES, the degree of
f
is 8, and hence
Z
2
[
x
]
f
is isomorph to
F
2
8
. In the sequel, we use the term
AES field
to refer to this field. The
fact that the AES field is a field means that every onzero element
b
(
x
) (i.e., every
nonzero polynomial over
Z
2
with degree less than 8) has a multiplicative inverse
b
−
1
(
x
) and that this element can be found using the extended Euclid algorithm.
Multiplying the polynomial defined in (10.4) with the polynomial
x
(or
{
00000010
}
or
0x02
in the byte representation) results in the following polynomial:
7
b
7
x
8
+
b
6
x
7
+
b
5
x
6
+
b
4
x
5
+
b
3
x
4
+
b
2
x
3
+
b
1
x
2
+
b
0
x
=
b
i
x
i
+1
i
=0
Again, this polynomial must be reduced modulo
f
(
x
).If
b
7
=0, then the
result is already in reduced form. Otherwise, if
b
7
=1, then the reduction is
accomplished by subtracting (i.e., adding modulo 2) the polynomial
f
(
x
). It follows
that multiplication by
x
can be implemented efficiently at the byte level as a shift
left and a subsequent conditional addition modulo 2 with
f
(
x
).
10.2.2.2
State
Internally, the AES operates on a two-dimensional array
s
of bytes, called the
State
.
The State consists of 4 rows and
N
b
columns (where
N
b
is the block length divided
by 32). In the current AES specification,
N
b
is always 4 (for all official versions of
the AES). Note, however, that this need not be the case and that there may be future
versions of the AES that work with larger values for
N
b
.
