An analysis of efficient formulas for elliptic curve point addition over binary extension fields

We show the relationships among efficient formulas based on the Weierstrass equation for elliptic curve point addition over binary extension fields. We give a simple proof that there can be no Weierstrass point addition function in terms of x coordinates only (for distinct points), though there are formulas that include the x coordinate of a fourth point, or an indication of the y coordinates. We show that a curve is cryptographically weak unless the trace of the x coordinate of the generator is equal to the trace of the coefficient of the second-order x term in the simplified Weierstrass equation. We examine binary Edwards elliptic curve formulas and mapping of points with Weierstrass curves. We show that several elliptic curve points are not defined in binary Edwards groups unless the trace of the second-order coefficient is one. We determine that operating with the sum of coordinates, rather than the individual coordinates, incurs no significant lose of information if the number of points is odd. We find that in order to gain competitiveness in terms of implementation efficiency, requiring that the binary Edwards first- and second-order coefficients are equal excludes many recommended Weierstrass elliptic curves.