Applicability of RFC-6090 point doubling formula in homogeneous coordinates

b) over all curves that can be represented as $y^2 = x^3 + ax + b$ ?

Elliptic curve of the form $y^2 = x^3 + ax + b$ is called the short Weierstrass equation (form). This short form is obtained from the (general Weierstrass equation ) $$Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6$$ by change of variables (transformations) if the characteristic $p$ of the field $p>3$. By doing this we get an isomorphic curve and the operation is reversible.

What's the applicability of the point doubling formula in section 3.1. of RFC-6090? Can it work with all valid curve points that're not point-at-infinity,

The arithmetic with projective coordinates

In the projective coordinates, the equation of $E$ is

$$Y^2 Z = X^3 + AXZ^2 + BZ^3.$$

• A point $(X_1 : Y_1 : Z_1 )$ on $E$ corresponds to the affine point $(X_1/Z_1,Y_1/Z_1)$ when $Z_1 \neq 0$

• When $Z_1$ we have the point at infinity $P_\infty = (0:1:0)$ which doesn't have representation on the affine coordinates.

• Opposite (negative) of a point $(X_1 : Y_1 : Z_1 )$ is $(X_1 : -Y_1 : Z_1 )$

Let $P_i = (X_i : Y_i : Z_i ), i = 1, 2$, be points on the homogenized elliptic curve

Then $$(X_1 : Y_1 : Z_1 ) + (X_2 : Y_2 : Z_2 ) = (X_3 : Y_3 : Z_3 ).$$

Formulas from Handbook of Elliptic and Hyperelliptic Curve Cryptography

• The addition formula $P_1 \neq \pm P_2$ with 12M+2S;

  • $A = Y_2 Z_1 − Y_1 Z_2,$

  • $B = X_2 Z_1 − X_1 Z_2,$

  • $C = A^2 Z_1 Z_2 − B^3 − 2B^2 X_1 Z_2,$ then

    $$X_3 = BC, \quad Y_3 = A(B^2 X_1 Z_2 − C) − B^3 Y_1Z_2, \quad Z_3 = B^3 Z_1 Z_2$$

• The doubling formula $P_1 = P_2$ with 7M+5S;

  • $A = a Z_1^2 + 3X_1^2,$

  • $B = Y_1 Z_1,$

  • $C = B X_1 Y_1,$

  • $D = A^2 − 8 C,$

    $$X_3 = 2BD, \quad Y_3 = A(4C − D) − 8Y_1^2 B^2 , \quad Z_3 = 8 B^3.$$

RF9060 formulas

RFC Shows a pseudo-code for adding and doubling ( there is an errata for this and here the corrected version is represented);

Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on the elliptic curve, and let u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2.

We observe that the points P1 and P2 are equal if and only if u and v are both equal to zero. Otherwise, if either P1 or P2 are equal to the point at infinity, v is zero and u is nonzero (but the converse implication does not hold).

 if P1 is the point at infinity,
    P3 = P2
 else if P2 is the point at infinity,
    P3 = P1
 else if P1=-P2 as projective points
    P3 = (0,1,0)
 else if P1 does not equal P2
    X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)
    Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3
    Z3 = v^3 * Z1 * Z2
 else    // P2 equals P1, P3 = P1 * P1
     w = 3 * X1^2 + a * Z1^2
    X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)
    Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3
    Z3 = 8 * (Y1 * Z1)^3

One has to use the equations to see that the special cases for $P_\infty$ is needed. And, yes, it works for all points other than the $P_\infty$. That is handled in the first two steps of the pseudocode.

Note 1: This RFC uses product for point addition that one must take care of. There is no product in an elliptic curve, we have point addition and scalar multiplication. The points are forming an Abelian group under point addition and with usual scalar multiplication, we can have only Z-Module.

Note 2: RFC6090 formula has the same cost as Handbook.

Note 3: Both formulas are verified with SageMath and they are correct according to SageMath's formulas. While testing Curve25519 is used. One can easily change this using the code from neuromancer

Note 4: Remove the special cases with $P_\infty$ then see that the results are not correct (most of the time it fails due to the result is not a point on the curve)