Cryptography Reference
In-Depth Information
group on which we can build our cryptosystem. Of course, the mere existence of a
cyclic group is not sufficient. The DL problem in this group must also be computa-
tionally hard, which means that it must have good one-way properties.
We start by considering certain polynomials (e.g., functions with sums of expo-
nents of
x
and
y
), and we plot them over the real numbers.
Example 9.1.
Let's look at the polynomial equation
x
2
+
y
2
=
r
2
over the real num-
bers
R
. If we plot all the pairs (
x
,
y
) which fulfill this equation in a coordinate sys-
y
x
Fig. 9.1
Plot of all points (
x
,
y
) which fulfill the equation
x
2
+
y
2
=
r
2
over
R
tem, we obtain a circle as shown in Fig. 9.1.
We now look at other polynomial equations over the real numbers.
Example 9.2.
A slight generalization of the circle equation is to introduce coeffi-
cients to the two terms
x
2
and
y
2
, i.e., we look at the set of solutions to the equation
a
x
2
+
b
y
2
=
c
over the real numbers. It turns out that we obtain an ellipse, as
·
·
y
x
x
2
+
b
y
2
=
c
over
Fig. 9.2
Plot of all points (
x
,
y
) which fulfill the equation
a
·
·
R
shown in Figure 9.2.
9.1.1 Definition of Elliptic Curves
From the two examples above, we conclude that we can form certain types of curves
from polynomial equations. By “curves”, we mean the set of points (
x
,
y
) which are
