Cryptography Reference
In-Depth Information
> F256:-ConvertOut(g);
F256:-ConvertIn(%);
xˆ2+x+1
(xˆ2 +x+1)mod2
Maple performs the
F256
arithmetic by means of the functions
F256:-'+'
,
F256:-'
−
'
,
F256:-'*'
,
F256:'
ˆ
'
,
F256:-inverse
, and
F256:-'/'
.
Field elements must be passed to these functions as binary polynomials. For the
addition we will not make use of these functions and, for efficiency, we will
instead use the previously given function
BitXor
. The multiplication can then be
defined as:
> mult256 := (a, b) -> F256:-output(F256:-'*'(F256:-input(a), F256:-input(b))):
For example,
> mult256(89, 175);
198
We will see that this operation is heavily used in the Advanced Encryption Stan-
dard and hence, for efficiency, it is convenient to have it implemented by means of a
lookup table. This can be done in the same way as in our implementation of
BitXor
.
Exercise 2.37
Construct a Maple 2-dimensional
(0..255, 0..255)
Array
containing the multiplication table of
F256
and use it to define a more
efficient multiplication function.
Another operation that will be used in the sequel is the computation of inverses
in
F256
, which we shall also implement by means of a lookup table. For now, note
that the function
(F256:-output@F256:-inverse@F256:-input)
gives
the inverse of a nonzero byte (as an integer in the 1
..
255 range). For example, the
inverse of 73 in this field is 100 because:
> (F256:-output@F256:-inverse@F256:-input)(73);
100
2.8.5 The Multiplicative Group of a Finite Field
p
n
, be a finite field with
q
elements. We are going to see that the
group of units of this field, i.e., the multiplicative abelian group
Let
F
q
, with
q
=
F
q
= F
q
−{
0
}
of
all the nonzero elements of
F
q
, is cyclic. First we show:
Theorem 2.23
For every divisor d of q
−
1
there are
φ(
d
)
elements of order d
F
q
.
in
∈ F
q
be an element of order
d
, i.e., an element such that
a
d
Proof
Let
a
=
1 and no
a
2
a
d
lower power with positive exponent is equal to 1. Then the powers
a
,
,...,
=
∈ F
q
are all distinct and are zeros of the polynomial
x
d
1
. Since by
Corollary 2.4 this polynomial has at most
d
zeros, we see that its zeros are all powers
−
1
∈ F
q
[
x
]
