Cryptography Reference
In-Depth Information
path as an element of the field
GF
(2
8
) and manipulates the data by performing
arithmetic in this finite field.
However, if the order of a finite field is not prime, and 2
8
is clearly not a prime,
the addition and multiplication operation cannot be represented by addition and mul-
tiplication of integers modulo 2
8
. Such fields with
m
>
1 are called
extension fields
.
In order to deal with extension fields we need (1) a different notation for field ele-
ments and (2) different rules for performing arithmetic with the elements. We will
see in the following that elements of extension fields can be represented as
poly-
nomials
, and that computation in the extension field is achieved by performing a
certain type of
polynomial arithmetic
.
In extension fields
GF
(2
m
) elements are not represented as integers but as poly-
nomials with coefficients in
GF
(2). The polynomials have a maximum degree of
m
1, so that there are
m
coefficients in total for every element. In the field
GF
(2
8
),
which is used in AES, each element
A
−
GF
(2
8
) is thus represented as:
∈
A
(
x
)=
a
7
x
7
+
···
+
a
1
x
+
a
0
,
a
i
∈
GF
(2)=
{
0
,
1
}
.
Note that there are exactly 256 = 2
8
such polynomials. The set of these 256 polyno-
mials is the finite field
GF
(2
8
). It is also important to observe that every polynomial
can simply be stored in digital form as an 8-bit vector
A
=(
a
7
,
a
6
,
a
5
,
a
4
,
a
3
,
a
2
,
a
1
,
a
0
)
.
In particular, we do
not
have to store the factors
x
7
,
x
6
, etc. It is clear from the bit
positions to which power
x
i
each coefficient belongs.
4.3.4 Addition and Subtraction in
GF
(2
m
)
Let's now look at addition and subtraction in extension fields. The key addition layer
of AES uses addition. It turns out that these operations are straightforward. They are
simply achieved by performing standard polynomial addition and subtraction: We
merely add or subtract coefficients with equal powers of
x
. The coefficient additions
or subtractions are done in the underlying field
GF
(2).
