Cryptography Reference
In-Depth Information
ric constructions from above through analytic expressions, i.e., formulae. As stated
above, these formulae only involve the four basic algebraic operations. These op-
erations can be performed in any field, not only over the field of the real numbers
(cf. Sect. 4.2). In particular, we can take the curve equation from above, but we now
consider it over prime fields
GF
(
p
) rather than over the real numbers. This yields
the following analytical expressions for the group operation.
Elliptic Curve Point Addition and Point Doubling
x
3
=
s
2
−
x
1
−
x
2
mod
p
y
3
=
s
(
x
1
−
x
3
)
−
y
1
mod
p
where
s
=
y
2
−
y
1
mod
p
;if
P
=
Q
(point addition)
x
2
−
x
1
3
x
1
+
a
2
y
1
mod
p
;if
P
=
Q
(point doubling)
Note that the parameter
s
is the slope of the line through
P
and
Q
in the case of
point addition, or the slope of the tangent through
P
in the case of point doubling.
Even though we made major headway towards the establishment of a finite group,
we are not there yet. One thing that is still missing is an identity (or neutral) element
O
such that:
P
+
O
=
P
for all points
P
on the elliptic curve. It turns out that there isn't any point (
x
,
y
) that
fulfills the condition. Instead we
define
an abstract
point at infinity
as the neutral
element
. This point at infinity can be visualized as a point that is located towards
“plus” infinity along the
y
-axis or towards “minus” infinity along the
y
-axis.
According the group definition, we can now also define the inverse
O
−
P
of any
group element
P
as:
P
+(
−
P
)=
O
.
The question is how do we find
P
? If we apply the tangent-and-chord method
from above, it turns out that the inverse of the point
P
=(
x
p
,
y
p
) is the point
−
−
P
=
(
x
p
,
y
p
), i.e., the point that is reflected along the
x
-axis. Figure 9.6 shows the point
P
together with its inverse. Note that finding the inverse of a point
P
=(
x
p
,
y
p
) is
now trivial. We simply take the negative of its
y
coordinate. In the case of elliptic
curves over a prime field
GF
(
p
) (the most interesting case in cryptography), this is
easily achieved since
−
−
y
p
≡
p
−
y
p
mod
p
, hence
−
P
=(
x
p
,
p
−
y
p
)
.
Now that we have defined all group properties for elliptic curves, we now look at
an example for the group operation.
Example 9.4.
We consider a curve over the small field
Z
17
:
