Elliptic Curve Mathematics

Projective Coordinates in Elliptic Curves

close button

Projective Coordinates in Elliptic Curves

By: Cailyn Yong and Bryan Wee

Previously, we were introduced to elliptic curves and point operations. So far, the elliptic curves we have seen are represented in the affine space, where points can be represented as (x,y)(x, y) coordinates. Affine group operations, as we will soon see, are costly as they require field divisions. In this article, we will see how projective coordinates can be used to sidestep these costs and achieve greater efficiency.

Since we are concerned with computational efficiency, we will only be studying curves that are restricted to prime fields. Hence, for all equations below, all field arithmetic is modulo arithmetic.

Cost of Affine Coordinates

Let us consider 2 affine coordinates, P=(x1,y1),Q=(x2,y2)P =(x_1, y_1), Q = (x_2, y_2), where PQP \neq Q, and recall how point addition is computed.

  1. If either point is OO, then P+QP+Q is given by the other point.

  2. Else if x1=x2x_1 = x_2, then P+Q=OP+Q=O.

  3. Else:
    • Let m=(y1y2)/(x1x2)m = (y_1 - y_2)/(x_1-x_2)
    • Then, x3=m2x1x2x_3 = m^2 - x_1 - x_2 and y3=m(x1x3)y1y_3 = m(x_1 - x_3) - y_1

Notice that in its worst case, point addition requires 2 multiplications, 6 additions/subtractions, and 1 division.

Let us recall how point doubling can be performed as well. To compute 2P=(x2,y2)2P = (x_2, y_2), where P=(x1,y1)P = (x_1,y_1):

  1. If P=OP=O or y1=0y_1 = 0, then 2P=O2P = O

  2. Else:
    • Let m=(3x12+a)/(2y1)m = ({3x_1}^2+a)/(2y_1)
    • Then, x2=m22x1x_2 = m^2 - 2x_1 and y2=m(x1x2)y1y_2 = m(x_1-x_2)-y_1

Point doubling involves 7 multiplications, 4 additions/subtractions, and 1 division.

Both point addition and doubling require 1 field division, which for prime fields, means modular division. This form of division requires the non-trivial act of finding a modular inverse, making it very expensive.

Projective Coordinates

Costs can be reduced by adopting a new coordinate system that avoids field division entirely. Given an affine coordinate (x,y)(x, y), we can transform it into a projective coordinate (X,Y,Z)(X, Y, Z) by taking an arbitrary non-zero value ZZ and assigning (X,Y,Z)=(xZ,yZ,Z)(X, Y, Z) = (xZ, yZ, Z).

For instance, (2,3)(2, 3) can be mapped to (4,6,2)(4, 6, 2) or (8,12,4)(8, 12, 4), with Z=2Z = 2 or Z=4Z = 4 respectively. Usually, zz is chosen to be 11 for convenience; affine coordinates (x,y)(x,y) would be transformed to (x,y,1)(x,y,1).

Projecting an entire elliptic curve yields the following curve equation.

Y2Z=X3+aXZ2+bZ3Y^2Z = X^3+aXZ^2+bZ^3

The diagram below visualizes how a projected curve might look like.

intro_elliptic_curves_03.webp

To convert projective coordinates (X,Y,Z)(X, Y, Z) back to affine coordinates (x,y)(x, y), all we have to do is divide the projective coordinate by ZZ.

(x,y)=(X/Z,Y/Z)(x, y) = (X/Z, Y/Z)

With projective coordinates, the formulae for point addition and point doubling require no field division. Take P=(X1,Y1,Z1)P = (X_1, Y_1, Z_1), Q=(X2,Y2,Z2)Q = (X_2, Y_2, Z_2), and PQP \neq Q. Let us see how we can compute P+Q=(X3,Y3,Z3)P + Q = (X_3, Y_3, Z_3).

  1. If either point is OO, then P+QP + Q is given by the other point.

  2. Else, let:
    u=Y2Z1Y1Z2u = Y_2Z_1 - Y_1Z_2
    v=X2Z1X1Z2v = X_2Z_1 - X_1Z_2
    A=u2Z1Z2v32v2X1Z2A = u^2Z_1Z_2 - v^3 - 2v^2X_1Z_2

  3. To perform point addition,
    X3=vAX_3 = vA
    Y3=u(v2X1Z2A)v3Y1Z2Y_3 = u(v^2X_1Z_2 - A) - v^3Y_1Z_2
    Z3=v3Z1Z2Z_3 = v^3Z_1Z_2

Next, given P=(X1,Y1,Z1)P = (X_1, Y_1, Z_1), how can compute 2P=(X2,Y2,Z2)2P = (X_2, Y_2, Z_2)?

  1. Let:
    w=aZ12+3X12w = a{Z_1}^2 + 3{X_1}^2
    s=Y1Z1s = Y_1Z_1
    B=X1Y1sB = X_1Y_1s
    h=w28Bh = w^2 - 8B

  2. To perform point doubling:
    X2=2hsX_2 = 2hs
    Y2=w(4Bh)8s2Y12Y_2 = w(4B-h)-8s^2{Y_1}^2
    Z2=8s3fZ_2 = 8s^3f

Both operations require more addition and multiplication than before, but demand zero divisions! Knowing this, we can much more efficiently manipulate elliptic curve points by:

  1. Converting affine coordinates to projective coordinates.

  2. Perform the required computation.

  3. Converting the results back to affine coordinates. (Only this step requires division)

Now, only two field divisions are required for any amount of consecutive point addition and doubling. This, in turn, saves a drastic amount of computation for elliptic curves over finite fields.

Jacobian Coordinates

A modified form of projective coordinates is Jacobian coordinates. For Jacobian coordinates, instead of multiplying xx and yy with ZZ like we did in the standard form of projective coordinates, we map affine coordinates (x,y)(x, y) to (X,Y,Z)=(xZ2,yZ3,Z)(X, Y, Z) = (x*Z^2, y*Z^3, Z).

Using Jacobian coordinates, elliptic curves adopt the following equation.

Y2=X3+aXZ4+bZ6Y^2 = X^3 + aXZ^4 + bZ^6

Here is the formula for point addition, assuming PQP \neq Q:

  1. If either point is OO, then P+QP + Q is given by the other point.

  2. Else, let:
    U1=X1Z22U_1 = X_1{Z_2}^2 and U2=X2Z12U_2 = X_2{Z_1}^2
    s=S1=Y1Z23s = S_1 = Y_1{Z_2}^3 and S2=Y2Z13S_2 = Y_2{Z_1}^3
    H=U2U1H = U_2 - U_1
    r=S2S1r = S_2 - S_1

  3. To perform point addition
    X3=r2H32U1H2X_3 = r^2 - H^3 - 2U_1H^2
    Y3=r(U1H2X3)S1H3Y_3 = r(U_1H^2-X_3) - S_1H^3
    Z3=HZ1Z2Z^3 = HZ_1Z_2

...and the formula for point doubling.

  1. If Y1=0,Y_1 = 0, then 2P=O2P = O.

  2. Else, let:
    S=4X1Y12S = 4X_1{Y_1}^2
    M=3X12+aZ14M = 3{X_1}^2 + a{Z_1}^4
    T=M22ST = M^2 - 2S

  3. To perform point doubling:
    S=X2=TS = X_2 = T
    Y2=M(ST)8Y14Y_2 = M(S-T) - 8{Y_1}^4
    Z2=2Y1Z1Z_2 = 2Y_1Z_1

Like before, these operations do not require field division. Jacobian coordinates offer a slight edge compared to standard projective coordinates because they trade multiplication for more addition/subtraction which tends to be cheaper.

Jacobian Coordinates ⇌ Affine Coordinates

Each instance of affine point addition/doubling requires one field division. This becomes extremely expensive once we consider consecutive curve operations (e.g., scalar multiplication). On the other hand, Jacobian coordinates demand no field divisions. We can exploit this fact to support affine point manipulation by:

1. Converting affine points to Jacobian points, with z=1z = 1.

(x,y)(x,y,1)(x, y) \rightarrow (x, y, 1)

2. Performing all necessary operations in Jacobian space.

3. Converting Jacobian points back to affine space. Let z1z^{-1} be the modular inverse of zz.

(x,y,z)(x(z1)2,y(z1)3)(x, y, z) \rightarrow (x * (z^{-1})^2, y * (z^{-1})^3)

This way, we only require one modular inversion for an arbitrary number of elliptic curve operations, saving a significant amount of computation!

Conclusion

In the previous article, we learned about the elliptic curve and the discrete logarithm problem. We then restricted the curve such that it can be computed by a computer with finite memory.

In this article, we transformed the curve onto a projective space and saw how it optimizes point arithmetic. After much math, we have arrived at a version of elliptic curves that is optimal for computers, and now have the necessary impetus to learn about elliptic curve cryptography.

If only I could read these glyphs a little faster...