Cryptography Reference
In-Depth Information
x
2
Let
P
(
x
)
(
P
(
x
)). Any polynomial
over
Z
2
can be reduced modulo
P
(
x
) into a polynomial of degree at most 1, so we have
only four classes of polynomials:
=
+
x
+
1in
Z
2
[
x
]. We consider GF(4) as
Z
2
[
x
]
/
the class
c
0
of polynomials congruent to 0
the class
c
1
of polynomials congruent to 1
the class
c
2
of polynomials congruent to
x
the class
c
3
of polynomials congruent to
x
+
1
Therefore GF(4)
. Addition is quite straightforward, as well as mul-
tiplication by
c
0
or
c
1
. We however have to explain how to compute
c
2
×
={
c
0
,
c
1
,
c
2
,
c
3
}
c
2
,
c
2
×
c
3
,
c
2
is
x
2
and
c
3
×
c
3
.
c
2
×
which is equal to
x
+
1 after reduction modulo
P
(
x
) since
x
2
c
3
. Similarly, we have
x
2
=
x
+
1
+
P
(
x
) thus
c
2
×
c
2
=
+
x
=
1
+
P
(
x
), thus
c
1
, and
x
2
c
2
×
c
3
=
+
1
=
x
+
P
(
x
), thus
c
3
×
c
3
=
c
2
. Here are the addition and
multiplication tables.
+
c
0
c
1
c
2
c
3
×
c
0
c
1
c
2
c
3
c
0
c
0
c
1
c
2
c
3
c
0
c
0
c
0
c
0
c
0
c
1
c
1
c
0
c
3
c
2
c
1
c
0
c
1
c
2
c
3
c
2
c
2
c
3
c
0
c
1
c
2
c
0
c
2
c
3
c
1
c
3
c
3
c
2
c
1
c
0
c
3
c
0
c
3
c
1
c
2
We notice that the additive group is isomorphic to
Z
2
×
Z
2
(and not to
Z
4
!), that
c
0
and
c
1
are neutral elements for the addition and the multiplication respectively, that all
elements but
c
0
are invertible, and that GF(4)
∗
is isomorphic to
Z
3
.
6.5
Elliptic Curves over Finite Fields
Elliptic curves are odd structures. They are curves of equations like
y
2
x
3
b
.
This looks like the curve in Fig. 6.8 when
x
and
y
are real numbers, depending on the
parameters
a
and
b
. They are used to define new types of groups for cryptography. For
completeness we give all necessary material to implement algorithms on elliptic curves
over finite fields.
=
+
ax
+
6.5.1
Characteristic
p
>
3
Let us first define an
elliptic curve
and
point addition
.
Definition 6.8.
Given a finite field
K
of characteristic p
>
3
and given a
,
b
∈
K
such
that
4
a
3
27
b
3
+
=
0
,welet
K
2
;
y
2
x
3
E
a
,
b
={
O
}∪{
(
x
,
y
)
∈
=
+
ax
+
b
}
.
Search WWH ::
Custom Search