Cryptography/Prime Curve/Standard Projective Coordinates

From Wikibooks, open books for an open world
Jump to navigation Jump to search

<Cryptography

Introduction[edit | edit source]

Standard Projective Coordinates are used to represent elliptic curve points on prime curves y^2 = x^3 + ax + b. Their usage might give a speed benefit over Affine Coordinates when the cost for field inversions is significantly higher than field multiplications. In Standard Projective Coordinates the triple (X, Y, Z) represents the affine point (X / Z, Y / Z).

Point Doubling (7M + 5S or 7M + 3S)[edit | edit source]

Let (X, Y, Z) be a point (unequal to the point at infinity) represented in Standard Projective Coordinates. Then its double (X', Y', Z') can be calculated by

if (Y == 0) 
 return POINT_AT_INFINITY
W = a*Z^2 + 3*X^2
S = Y*Z
B = X*Y*S
H = W^2 - 8*B
X' = 2*H*S
Y' = W*(4*B - H) - 8*Y^2*S^2
Z' = 8*S^3
return (X', Y', Z')

Note: if a = -3, then W can also be calculated as W = 3*(X + Z)*(X - Z), saving 2 field squarings.

Point Addition (12M + 2S)[edit | edit source]

Let (X1, Y1, Z1) and (X2, Y2, Z2) be two points (both unequal to the point at infinity) represented in Standard Projective Coordinates. Then the sum (X3, Y3, Z3) can be calculated by

U1 = Y2*Z1
U2 = Y1*Z2
V1 = X2*Z1
V2 = X1*Z2
if (V1 == V2)
  if (U1 != U2)
    return POINT_AT_INFINITY
  else
    return POINT_DOUBLE(X1, Y1, Z1)
U = U1 - U2
V = V1 - V2
W = Z1*Z2
A = U^2*W - V^3 - 2*V^2*V2
X3 = V*A
Y3 = U*(V^2*V2 - A) - V^3*U2
Z3 = V^3*W
return (X3, Y3, Z3)

Mixed Addition (with affine point) (9M + 2S)[edit | edit source]

Let (X1, Y1, Z1) be a point represented in Standard Projective Coordinates and (X2, Y2) a point in Affine Coordinates (both unequal to the point at infinity). A formula to add those points can be readily derived from the regular standard projective point addition by replacing each occurrence of "Z2" by "1" (and thereby dropping three field multiplications).