Cryptography Reference
In-Depth Information
Note that when
P
1
and
P
2
have coordinates in a field
L
that contains
A
and
B
,then
P
1
+
P
2
also has coordinates in
L
. Therefore
E
(
L
) is closed under
the above addition of points.
This addition of points might seem a little unnatural. Later (in Chapters 9
and 11), we'll interpret it as corresponding to some very natural operations,
but, for the present, let's show that it has some nice properties.
THEOREM 2.1
T he addition ofpointsonanellipticcurve
E
satisfi es the follow ing properties:
1. (com m utativity)
P
1
+
P
2
=
P
2
+
P
1
for all
P
1
,P
2
on
E
.
2. (existence of identity)
P
+
∞
=
P
for allpoints
P
on
E
.
3. (existence ofin verses) G iven
P
on
E
,there exists
P
on
E
with
P
+
P
=
∞
.Thispoint
P
willusuallybedenoted
−
P
.
4. (associativity)
(
P
1
+
P
2
)+
P
3
=
P
1
+(
P
2
+
P
3
)
for all
P
1
,P
2
,P
3
on
E
.
In o ther w ords,the pointson
E
form an additive abelian group w ith
∞
as the
identitye em ent.
PROOF
The commutativity is obvious, either from the formulas or from
the fact that the line through
P
1
and
P
2
isthesameasthelinethrough
P
2
and
P
1
. The identity property of
holds by definition. For inverses, let
P
be the reflection of
P
across the
x
-axis. Then
P
+
P
=
∞
.
Finally, we need to prove associativity. This is by far the most subtle and
nonobvious property of the addition of points on
E
. It is possible to define
many laws of composition satisfying (1), (2), (3) for points on
E
, either simpler
or more complicated than the one being considered. But it is very unlikely
that such a law will be associative. In fact, it is rather surprising that the
law of composition that we have defined is associative. After all, we start
with two points
P
1
and
P
2
and perform a certain procedure to obtain a third
point
P
1
+
P
2
. Then we repeat the procedure with
P
1
+
P
2
and
P
3
to obtain
(
P
1
+
P
2
)+
P
3
. If we instead start by adding
P
2
and
P
3
, then computing
P
1
+(
P
2
+
P
3
), there seems to be no obvious reason that this should give the
same point as the other computation.
The associative law can be verified by calculation with the formulas. There
are several cases, depending on whether or not
P
1
=
P
2
, and whether or not
P
3
=(
P
1
+
P
2
), etc., and this makes the proof rather messy. However, we
prefer a different approach, which we give in Section 2.4.
∞
y
).
For the generalized Weierstrass equation (2.1), this is no longer the case. If
P
=(
x, y
) is on the curve described by (2.1), then (see Exercise 2.9)
Warning:
For the Weierstrass equation, if
P
=(
x, y
), then
−
P
=(
x,
−
−P
=(
x, −a
1
x − a
3
− y
)
.
Search WWH ::
Custom Search