Cryptography Reference
In-Depth Information
the fact that the x
2
coefficient is the negative of the sum of the three solutions of the equation. Since
we already know two of the solutions (they had better be
x
1
and
x
2
), we can calculate -
m
2
= -
x
3
-
x
2
-
x
1
, giving us
x
3
=
m
2
-
x
2
-
x
1
. Plugging this into the above equations will reveal that the other
coefficients come out as they should.
To calculate
y
3
, we use the fact that
y
3
=
mx
3
+
c
and that we know what
x
3
and
c
are. Since we had
to calculate
x
3
anyway, we'll just use that value, but we can simplify the
c
term a little. Plugging in
mx
3
+
c
for
y
3
, we get
Thus, we have found that
This addition procedure has identical properties to the above geometrical construction — it doesn't matter
which point is “first”:
P
+
Q
=
Q
+ P. We also know that we have an identity element of ∞. It also turns out that
if we have three points, say
P, Q
, and
R
on the elliptic curve, then we are guaranteed that
(P
+
Q)
+
R
=
P
+
(Q
+
R),
so that addition of points on the elliptic curve is associative. This fact is non-trivial to prove; thus, I refer
the reader to Reference [13] for more details.
Since we have all of these properties, we find that the elliptic curve points, together with addition, form an
abelian group, often denoted as
(E(F),
+), where
F
is the field that the coordinates for the points on the elliptic
curves come from.
Let's do a quick example of the addition of two rational points, so that we can make sure that we have the
concept down (and also as a simple test case for any computer implementation of elliptic curve point addition).
Our curve will be defined by
y
2
=
x
3
- 25
x
(therefore,
a
= - 25,
b
= 0), with two points
P
= (
x
1
,
y
1
= (-4, 6) and
Q
= (
x
2
,
y
2
) = (1681/44, -62,279/178).
Following the steps of the algorithm, we note that it does not fall into the cases where
P
=
Q
or
P
= -Q, so we
proceed to Step 3 — calculating m. For the rational numbers, the multiplicative inverse is found just by flipping
the numerator and denominator, thus
Step 4 was used just for the purposes of demonstration, so we skip ahead to the end of Step 5 and note that
and
y
3
=
m
(
x
3
-
x
2
) +
y
2
... I'm just going to leave out the calculation of those huge numbers and tell you that the answer is
Trust me. Or better yet, don't trust me, and verify yourself.
Search WWH ::
Custom Search