Cryptography Reference
In-Depth Information
where the term collinear here means that there is a line that intersects
E
at the three
points
P
,
,
R
counting multiplicity and including the possibility that some of these
points are equal to the point at infinity.
We are now going to give the explicit formulas for the addition of points that will
be used in cryptographic algorithms. These formulas are based on the
chord-tangent
method
and give an expression for the coordinates of
P
1
+
Q
P
2
in terms of those of
P
1
and
P
2
.
Theorem 11.1
Let E be an elliptic curve given by a Weierstrass equation
y
2
x
3
=
+
ax
+
b
over a field of characteristic
=
2
,
3
and let P
1
,P
2
be points in E . Then the following
assertions hold:
1.
If P
1
=
O
then P
1
+
P
2
=
P
2
, otherwise if P
2
=
O
then P
1
+
P
2
=
P
1
.
2.
If P
1
=
O
and P
2
=
O
, write P
i
=
(
x
i
,
y
i
)
for i
=
1
,
2
. The following formulas
hold:
a.
If x
1
=
x
2
and y
1
=−
y
2
then P
1
+
P
2
=
O
.
If x
1
=
x
2
or y
1
=−
b.
y
2
then set
⎧
⎨
y
2
−
y
1
if P
1
=
P
2
x
2
−
x
1
m
=
⎩
3
x
1
+
a
if P
1
=
P
2
,
2
y
1
and let
m
2
x
3
=
−
x
1
−
x
2
and y
3
=
m
(
x
1
−
x
3
)
−
y
1
.
Then P
1
+
P
2
=
(
x
3
,
y
3
)
.
Proof
The cases 1 and 2 (a) are clear after our previous discussion. For case 2 (b)
note that if
P
1
=
P
2
then
m
is the slope of the tangent line at
P
1
; in the latter case we may use implicit
differentiation of the equation of the curve, just as we did in the computation with
Maple in Example 11.2, and we find that the slope is indeed
m
P
2
, then
m
is the slope of the line through
P
1
and
P
2
and if
P
1
=
3
x
1
+
a
=
. In either
2
y
1
case, the line
L
P
1
P
2
has equation
y
=
mx
+
t
, where
t
=
y
1
−
mx
1
. Substituting the
equation for
L
P
1
P
2
in the equation for
E
gives the identity:
x
3
2
+
ax
+
b
=
(
mx
+
t
)
,
which can be written in the form:
x
3
m
2
x
2
t
2
−
+
(
a
−
2
mt
)
x
+
(
b
−
)
=
0
.
