Cryptography Reference
In-Depth Information
x
5
individually:
x
4
= 1
·
P
(
x
)+(
x
+ 1)
x
4
≡
x
+ 1mod
P
(
x
)
x
5
x
2
+
x
mod
P
(
x
)
.
≡
Now, we only have to insert the reduced expression for
x
5
into the intermediate
result
C
(
x
):
x
5
+
x
3
+
x
2
+
x
mod
P
(
x
)
C
(
x
)
≡
(
x
2
+
x
)+(
x
3
+
x
2
+
x
)=
x
3
C
(
x
)
≡
x
3
.
A
(
x
)
·
B
(
x
)
≡
It is important not to confuse multiplication in
GF
(2
m
) with integer multiplica-
tion, especially if we are concerned with software implementations of Galois fields.
Recall that the polynomials, i.e., the field elements, are normally stored as bit vec-
tors in the computers. If we look at the multiplication from the previous example,
the following very atypical operation is being performed on the bit level:
A
·
B
=
C
(
x
3
+
x
2
+ 1)
(
x
2
+
x
)=
x
3
·
(0110)=(1000).
This computation is
not
identical to integer arithmetic. If the polynomials are in-
terpreted as integers, i.e., (1101)
2
= 13
10
and (0110)
2
= 6
10
, the result would have
been (1001110)
2
= 78
10
, which is clearly not the same as the Galois field multipli-
cation product. Hence, even though we can represent field elements as integers data
types, we cannot make use of the integer arithmetic provided
(1101)
·
4.3.6 Inversion in
GF
(2
m
)
Inversion in
GF
(2
8
) is the core operation of the Byte Substitution transformation,
which contains the AES S-Boxes. For a given finite field
GF
(2
m
) and the corre-
sponding irreducible reduction polynomial
P
(
x
),theinverse
A
−
1
of a nonzero ele-
GF
(2
m
) is defined as:
ment
A
∈
A
−
1
(
x
)
·
A
(
x
)=1mod
P
(
x
)
.
For small fields — in practice this often means fields with 2
16
or fewer elements
— lookup tables which contain the precomputed inverses of all field elements are
often used. Table 4.2 shows the values which are used within the S-Box of AES.
The table contains all inverses in
GF
(2
8
) modulo
P
(
x
)=
x
8
+
x
4
+
x
3
+
x
+ 1in
hexadecimal notation. A special case is the entry for the field element 0, for which