Cryptography Reference
In-Depth Information
Note that all coefficients
a
i
,
b
i
and
c
i
are elements of
GF
(2), and that coeffi-
cient arithmetic is performed in
GF
(2). In general, the product polynomial
C
(
x
)
will have a degree higher than
m
1 and has to be reduced. The basic idea is an ap-
proach similar to the case of multiplication in prime fields: in
GF
(
p
), we multiply
the two integers, divide the result by a prime, and consider only the remainder. Here
is what we are doing in extension fields: The product of the multiplication is divided
by a certain polynomial, and we consider only the remainder after the polynomial
division. We need irreducible polynomials for the module reduction. We recall from
Sect. 2.3.1 that irreducible polynomials are roughly comparable to prime numbers,
i.e., their only factors are 1 and the polynomial itself.
−
Definition 4.3.4
Extension field multiplication
Let A
(
x
)
,
B
(
x
)
GF
(2
m
)
and let
∈
m
i
=0
p
i
x
i
,
P
(
x
)
≡
p
i
∈
GF
(2)
be an irreducible polynomial. Multiplication of the two elements
A
(
x
)
,
B
(
x
)
is performed as
C
(
x
)
≡
A
(
x
)
·
B
(
x
) mod
P
(
x
)
.
Thus, every field
GF
(2
m
) requires an irreducible polynomial
P
(
x
) of degree
m
with coefficients from
GF
(2). Note that not all polynomials are irreducible. For
example, the polynomial
x
4
+
x
3
+
x
+ 1 is reducible since
x
4
+
x
3
+
x
+ 1 =(
x
2
+
x
+ 1)(
x
2
+ 1)
and hence cannot be used to construct the extension field
GF
(2
4
). Since primitive
polynomials are a special type of irreducible polynomial, the polynomials in Ta-
ble 2.3 can be used for constructing fields
GF
(2
m
). For AES, the irreducible poly-
nomial
P
(
x
)=
x
8
+
x
4
+
x
3
+
x
+ 1
is used. It is part of the AES specification.
Example 4.6.
We want to multiply the two polynomials
A
(
x
)=
x
3
+
x
2
+ 1 and
B
(
x
)=
x
2
+
x
in the field
GF
(2
4
). The irreducible polynomial of this Galois field is
given as
P
(
x
)=
x
4
+
x
+ 1
.
The plain polynomial product is computed as:
C
(
x
)=
A
(
x
)
B
(
x
)=
x
5
+
x
3
+
x
2
+
x
.
·
We can now reduce
C
(
x
) using the polynomial division method we learned in
school. However, sometimes it is easier to reduce each of the leading terms
x
4
and
