Cryptography Reference
In-Depth Information
added mod
p
. In other words, the sum consists in computing the
p
-adic expansion
of the integers and then adding the base-
p
digits without carry. On the other hand,
multiplying two integers in
p
n
consists simply of taking the polynomials
associated to these integers and multiplying them modulo
f
(so that, in contrast
with addition, multiplication depends on the particular choice of
f
). The matrix that
defines the multiplication table of
[
0
,
−
1
]
F
9
that we have just seen can be put in integer form
as follows (assuming that the result of computing the previous table in polynomial
form is the last output produced by Maple):
> subs(x = 3, %);
⎡
⎣
⎤
⎦
000000000
012345678
021687354
036258147
048561723
057813462
063174285
075426831
084732516
Looking at this matrix we see, for example, that the product of 3 by 5 is 8 in
F
9
which corresponds to the fact that the polynomial
x
(which corresponds to the
integer 3) multiplied by the polynomial
x
+
2 (corresponding to 5) gives as a result
the polynomial
x
2
in
Z
3
[
x
]
+
2
x
and the remainder of dividing this polynomial by
the irreducible
x
2
+
+
1 that we used to define the field is 2
x
2 which corresponds
to the integer 8.
x
3
Exercise 2.35
Consider
Z
3
[
x
]
f
with
f
=
+
2
x
+
1
∈ Z
3
[
x
]
. Prove that
f
is
irreducible and hence that it defines the field
F
3
3
. Compute the product of 25 by 11
when these integers are seen as elements of this field.
2.8.4 The Field of 256 Elements
The field
F
2
8
is especially important for cryptography because it is the one on whose
arithmetic the
Advanced Encryption Standard
is based. We are going to describe this
field in detail with the help of Maple. Although we have not used it so far, Maple has
a specific package for the arithmetic of finite fields, namely, the package
GF
whose
calling sequence is
> GF(p, n, f):
where
p
is a prime number,
n
a positive integer and
f
an irreducible polynomial
of degree
n
over
Z
p
, with the last parameter being optional (if not specified, Maple
itself chooses the irreducible polynomial of degree
n
to be used).
We are going to use this package, and the “first” irreducible polynomial of degree
8 over
,
x
8
x
4
x
3
Z
2
[
x
]
+
+
+
x
+
1 (already mentioned in a previous example), to
