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
Search WWH ::




Custom Search