0
$\begingroup$

I am writing code for Elliptic Curve Cryptography. I have a class class EllipticCurvePoint.

class EllipticCurvePoint{
    FieldElement x, y;
};

I need to support point-at-infinity (which should behave as if it is an object of type EllipticCurvePoint). Only thing I can think of is to reserve (-1, -1) for this but x and y can assume values only from {0, 1, ..., p-1} (p being the Field they belong to). If I want to represent it this way, I would need to add support for -1 in the classes FieldElement and Field too.

I have also overloaded the + and the * operators which work perfectly fine for other points. But I cannot think of a way to represent point-at-infinity which can work homogeneously with the rest of the code and I wouldn't have to change the parent classes(Field and FieldElement).

Is there any elegant way to achieve this? Thanks a lot for your time!

$\endgroup$
1
$\begingroup$

I suppose it is a short Weierstrass curve. There are several possibilities:

  • Projective coordinates: a point $P = (x,y)$ is stored with three coordinates, $X$, $Y$ and $Z$ that satisfy $x=X/Z$ and $y=Y/Z$. We note $P=(X:Y:Z)$. That means a point can have more than one representation (it is the same as fractions, $\frac 3 4$ is the same as $\frac{15}{20}$). The curve equation $y^2 = x^3 + Ax + B$ becomes $Y^2Z = X^3 + AXZ^2 + BZ^3$ and the point at infinity is the point that have $Z=0$, then you can check that $\infty = (0:1:0)$ (or more generally, $(0:\lambda:0)$ for any nonzero $\lambda$).

  • Jacobian projective coordinates, same as above but with $x=X/Z^2$ and $y=Y/Z^3$ and the infinity point is $(1:1:0)$ or more generally $(\lambda^2 : \lambda^3 : 0)$ for any nonzero $\lambda$.

  • If you keep only affine coordinates, you can add a boolean is_infinity in you class.

Anyway, depending of how you will implement addition formulas on the curve, you must know that most of them won't work flawlessly with all the points, unless you use complete unified formula (see here for Weierstrass curves).

On a side note, you can take a look at Edwards curves where the infinity point has an affine representation (the Edwards form of Curve25519 or Curve448 are used for the cryptographic primitive signature EdDSA).

$\endgroup$
  • $\begingroup$ Another neat solution is to use a variant type (also known as tagged union) which distinguishes between a valid and an invalid point which should make it harder for code to ignore the is_infinity flag. $\endgroup$ – SEJPM Oct 13 at 11:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.