Cryptography Reference
In-Depth Information
3
2
P3
1
P2
0
P1
−
1
−
2
−
3
−
3
−
2
−
1
0
1
2
3
Figure 3-6:
Point multiplication on an elliptic curve
So, given two points p
1
(x
1
,y
1
), p
2
(x
2
, y
2
), “addition” of points p
3
p
1
p
2
is defi ned as:
x
3
l
2
x
1
x
2
y
3
l
(x
1
x
3
)
y
1
where
y
2
y
1
l
x
2
x
1
(that is, the slope of the line through
p
1
and
p
2
). You may be able to spot a problem
with this defi nition, though: How do you add a point to itself? A point all by
itself has no slope —
0
0
in this case. So you need a special rule for “doubling”
l
a point. Given p
1
(x
1
, y
1
), 2p
1
is defi ned as:
x
3
l
2
2x
1
y
3
l
(x
1
x
3
)
y
1
where
3x
2
1
a
l
2y
1
Remember that
a
was one of the constants in the defi nition of the curve.
So, armed with a point addition and a point-doubling routine, you can defi ne
multiplication of a point by a scalar in terms of double and add. Recall that, for
integer operations, double-and-add was a “nice” speed-up. In terms of elliptic
Search WWH ::
Custom Search