Point group operation

From Elliptic Curve Crypto
Caveat emptor: This article is incomplete, and more critical than others at this site. See any of various theses on the topic [1][2]. This is proof that the unlearned and obstinate men, who have so far purported to implement “elliptic curve cryptography” and put their patented cryptographic schemes to widespread use under that name, had already been served with adequate instructions and examples, when they insisted on calling the law and getting all the details wrong in their official implementations and protocols.

Geometric derivation

A point group operation on an elliptic curve is derived by geometric considerations on the curve in Weierstraß normal form over the real numbers.

Because it is defined by an algebraic equation in the third degree, a straight line can intersect such a curve at at most three points in the Euclidean plane.

Point addition

The basic point group operation consists in finding the reflection across the x-axis of the third point of intersection of the curve with a line through two given points on the curve.

Some or all of the points on the elliptic curve, together with the point group operation , make out an Abelian group.

An additional point at infinity is adjoined to the plane, and considered to lie on the curve, although it is not given coördinates in the real numbers. This point is the group identity. The group inverse consists in taking the reflection of a point across the x-axis.

Point-doubling

The special case of the addition operation of a point with itself, called point-doubling, is defined similarly, but by considering the line tangent to the curve at that point rather than through two distinct points.

Algebraic derivation

Let be the resolvent equation of the line passing through two given points P and Q of an elliptic curve . Square the resolvent on both sides, place it over the equation for the elliptic curve, (here the Weierstraß normal form,) and subtract to find the resultant equation.


Divide the factors for the two given points P and Q together with the leading coefficient

into the resultant to find the x-coördinate of the third point R on the elliptic curve through which the same line passes.

The remainder might be set equal to zero term by term (as we know it is having obtained three linear factors of a cubic equation) and then (with the variable x eliminated) a system of two quadratic equations [3] is left to sort out and solve for m and c, the coefficients of the resolvent equation for the line passing through P and Q.

However, we already know the slope m of the resolvent line equation, up to four choices of sign for yP and yQ respectively, and we have the x-coördinate of the third point in terms of it, from the quotient already calculated. The special case of point-doubling (when Q=P) is addressed by taking the derivative of the elliptic curve through that point to calculate the slope of the tangent line.

Now

or

reflecting across the x-axis to find the “sum” point opposite R.

  1. Noraldeen Alyounes. Elliptiska kurvor och kryptografi. Examensarbete i matematik, Uppsala Universitet, Februari 2020. https://uu.diva-portal.org/smash/get/diva2:1395121/FULLTEXT01.pdf
  2. Gunendra Bikram Bidari. An algorithmic approach to elliptic curve cryptography. Thesis, ME in Computer Engineering, Kathmandu University, 2014. Lambert Academic Publishing, 2015.
  3. Adelaide Denis. “A Discussion of the Cases when Two Quadratic Equations Involving Two Variables can be Solved by the Method of Quadratics.” The American Mathematical Monthly, vol. 10, no. 8/9, Aug. - Sep., 1903. File:Denis-DiscussionCasesTwo-1903-9-jam8-join.pdf https://www.jstor.org/stable/2971350