Cryptography Reference
In-Depth Information
Completing the square yields
y 1 = x 3 +2 x 2
5 x − 6 ,
1
where y 1 = y +1
2 x .
2.6 Other Coordinate Systems
The formulas for adding two points on an elliptic curve in Weierstrass form
require 2 multiplications, 1 squaring, and 1 inversion in the field. Although
finding inverses is fast, it is much slower than multiplication. In [27, p. 282],
it is estimated that inversion takes between 9 and 40 times as long as multi-
plication. Moreover, squaring takes about 0.8 the time of multiplication. In
many situations, this distinction makes no difference. However, if a central
computer needs to verify many signatures in a second, such distinctions can
become relevant. Therefore, it is sometimes advantageous to avoid inversion
in the formulas for point addition. In this section, we discuss a few alternative
formulas where this can be done.
2.6.1
Projective Coordinates
A natural method is to write all the points as points ( x : y : z ) in projective
space. By clearing denominators in the standard formulas for addition, we
obtain the following:
Let P i =( x i : y i : z i ), i =1 , 2, be points on the elliptic curve y 2 z =
x 3 + Axz 2 + Bz 3 .Then
( x 1 : y 1 : z 1 )+( x 2 : y 2 : z 2 )=( x 3 : y 3 : z 3 ) ,
where x 3 ,y 3 ,z 3 are computed as follows: When P 1
=
±
P 2 ,
w = u 2 z 1 z 2 − v 3
2 v 2 x 1 z 2 ,
u = y 2 z 1 − y 1 z 2 ,
v = x 2 z 1 − x 1 z 2 ,
y 3 = u ( v 2 x 1 z 2
v 3 y 1 z 2 ,
3 = v 3 z 1 z 2 .
x 3 = vw,
w )
When P 1 = P 2 ,
t = Az 1 +3 x 1 ,
w = t 2
u = y 1 z 1 ,
v = ux 1 y 1 ,
8 v,
8 y 1 u 2 ,
3 =8 u 3 .
x 3 =2 uw,
y 3 = t (4 v
w )
When P 1 = −P 2 ,wehave P 1 + P 2 = .
Point addition takes 12 multiplications and 2 squarings, while point dou-
bling takes 7 multiplications and 5 squarings. No inversions are needed. Since
Search WWH ::




Custom Search