Cryptography Reference
In-Depth Information
We notice several things from this elliptic curve plot.
1
First, the elliptic curve
is symmetric with respect to the
x
-axis. This follows directl
y from the fa
ct that for
all values
x
i
which are on the elliptic curve, both
y
i
=
x
i
+
a
x
i
+
b
and
y
i
=
·
x
i
+
a
−
x
i
+
b
are solutions. Second, there is one intersection with the
x
-axis.
This follows from the fact that it is a cubic equation if we solve for
y
= 0 which has
one real solution (the intersection with the
x
-axis) and two complex solutions (which
do not show up in the plot). There are also elliptic curves with three intersections
with the
x
-axis.
We now return to our original goal of finding a curve with a large cyclic group,
which is needed for constructing a discrete logarithm problem. The first task for
finding a group is done, namely identifying a set of elements. In the elliptic curve
case, the group elements are the points that fulfill Eq. (9.1). The next question at
hand is: How do we define a group operation with those points? Of course, we have
to make sure that the group laws from Definition 4.3.1 in Sect. 4.2 hold for the
operation.
·
9.1.2 Group Operations on Elliptic Curves
Let's denote the group operation with the addition symbol
2
“+”. “Addition” means
that given two points and their coordinates, say
P
=(
x
1
,
y
1
) and
Q
=(
x
2
,
y
2
),we
have to compute the coordinates of a third point
R
such that:
P
+
Q
=
R
(
x
1
,
y
1
)+(
x
2
,
y
2
)=(
x
3
,
y
3
)
As we will see below, it turns out that this addition operation looks quite arbi-
trary. Luckily, there is a nice geometric interpretation of the addition operation if we
consider a curve defined over the real numbers. For this geometric interpretation,
we have to distinguish two cases: the addition of two distinct points (named point
addition) and the addition of one point to itself (named point doubling).
Point Addition P
+
Q
This is the case where we compute
R
=
P
+
Q
and
P
=
Q
. The construction works as follows: Draw a line through
P
and
Q
and obtain a
third point of intersection between the elliptic curve and the line. Mirror this third
intersection point along the
x
-axis. This mirrored point is, by definition, the point
R
.
Figure 9.4 shows the point addition on an elliptic curve over the real numbers.
Point Doubling P
+
P
This is the case where we compute
P
+
Q
but
P
=
Q
. Hence,
we can write
R
=
P
+
P
= 2
P
. We need a slightly different construction here. We
1
Note that elliptic curves are not ellipses. They play a role in determining the circumference of
ellipses, hence the name.
2
Note that the choice of naming the operation “addition” is completely arbitrary; we could have
also called it multiplication.
