4
$\begingroup$

I hear that there should be a point at infinity on secp256k1. I wounder how to calculate it and what does it even mean. I tried to calculate it as $P_{inf}=P+(-P)$ but this gives different results for different P. Are there more than one point at infinity?

Geometrically thinking on an elliptic curve, adding two points that are symmetric against x-axis, should not be feasible because any vertical line on x-y plane will only intersect the curve at TWO points not THREE.

$\endgroup$
7
$\begingroup$

Point at Infinity

Yes, there is a point at infinity $O$ (or denoted as $\infty$) on Elliptic Curves (EC). Let the EC be given in Weierstrass equation;

$$y^2 = x^3 +a x + b$$

$O$, the point at infinity can have different values according to the underlying coordinate system;

Coordinate Systems

For an elliptic curve over $\mathbb{F}_p$;

  • In Homogeneous Coordinates (also known as Projective Coordinate), the points are defined as $(x:y:z),z\neq 0$ corresponding to affine point $(\frac{x}{z},\frac{y}{z})$. The point at infinity is $(0:1:0)$ and negative value of $(x:y:z)$ is $(x:-y:z)$
  • In Jacobian Coordinate the points are defined as $(x:y:z),z\neq 0$ corresponding to affine point $(\frac{x}{z^2},\frac{y}{z^3})$. The point at infinity is $(1:1:0)$ and negative value of $(x:y:z)$ is $(x:-y:z)$

Now, what is $O$ in affine coordinates? Try to convert $O$ back into an affine coordinate! Well, we cannot represent it! See this answer Thus, we simply say it is $O$. But, magically, it can be encoded in implementations.

The Group Law

The points on an elliptic curve form an additive group with an identity $O$. For geometrical meaning please see the below image from Wikipedia Elliptic Curves The group law.

Geometric interpretation of addition on a Weierstrass curve

The Group Law on Affine Coordinates

Arithmetically can define the addition rules in affine coordinates. These are derived from the line intersection and tangent equations. The formulas are;

Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

  1. $P+O=O+P=P$
  2. If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
  3. If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align} x_3 = & \lambda^2 -x_1 - x_2 \mod p\\ y_3 = & \lambda(x_1-x_3) -y_1 \mod p \end{align}

$$ \lambda = \begin{cases} \frac{y_2-y_1}{x_2-x_1}, & \text{if $P \neq Q$} \\[2ex] \frac{3 x_1^2+a}{2y_1}, & \text{if $P = Q$} \\[2ex] \end{cases}$$

The Group Law on projective Coordinates

Let $P_i = (x_i : y_i : z_i ), i = 1, 2$, be points on the elliptic curve $$y^2 z = x^3 + Axz^2 + Bz^3.$$ Then $$(x_1 : y_1 : z_1 ) + (x_2 : y_2 : z_2 ) = (x_3 : y_3 : z_3 ).$$ The formulas are;

  1. $P_1 \neq \pm P_2$

    • $u = y_2 z_1 − y_1 z_2,$
    • $v = x_2 z_1 − x_1 z_2,$
    • $w = u^2 z_1 z_2 − v^3 − 2v^2 x_1 z_2,$ then

    $$x_3 = vw, \quad y_3 = u(v^2 x_1 z_2 − w) − v^3 y_1z_2, \quad z_3 = v^3 z_1 z_2$$

  2. $P_1 = P_2$

    • $t = a z_1^2 + 3x_1^2,$
    • $u = y_1 z_1,$
    • $v = u x_1 y_1,$
    • $w = t^2 − 8 v,$

$$x_3 = 2uw, \quad y_3 = t(4v − w) − 8y_1^2 u^2 , \quad z_3 = 8 u^3.$$

For Jacobian Coordinate operations see this link.

$\endgroup$
  • 1
    $\begingroup$ In 2 you mean P + Q = O (or P + -P) $\endgroup$ – dave_thompson_085 Jan 6 '19 at 10:13
  • $\begingroup$ @kelalaka the Wikipedia link you have supplied is saying that if P and Q are opposites of each other, we define $P + Q = O$. Why we cannot conclude $P+(-P)=O$ is always true? By the way what is the random looking output value is that my computer program in python is giving as output? finally is it possible to calculate $O$ so that for any randomly given $P$ the computer program can calculate $P+O=P$? $\endgroup$ – PouJa Jan 6 '19 at 10:57
  • $\begingroup$ The points are forming an additive group with identity $O$ so $P+(-P) = O$. Wikipedia also says the opposite of a point $P$ is $-P$. For the programming part, unfortunately, off-topic here. Please ask a question on StackOverflow. $\endgroup$ – kelalaka Jan 6 '19 at 11:17
2
$\begingroup$

What does (the point at infinity) even means?

That's an abstract point/concept required so that the addition of points on the Elliptic Curve is a group law; including:

  • Addition of any two elements $P$ and $Q$ of the group is an element of the group
  • There is a neutral element $\mathcal O$ such that for all $P$, $P+\mathcal O=P=\mathcal O+P$.

A possible definition: the point at infinity is a single extra element $\mathcal O$ added to the curve and the rules of point addition, such that for all $P$ on the curve (including the point at infinity $\mathcal O$), it holds $P+\mathcal O=P=\mathcal O+P$.

We can then define $-P$ as the point $Q$ such that $P+Q=\mathcal O=Q+P$, and for all $P$ it holds $P+(-P)=\mathcal O=(-P)+P$.

How to calculate (the point at infinity)

One does not, much line one does not calculate $+\infty$.

One may define a conventional representation of the point at infinity in the Cartesian coordinate system by picking any coordinate not on the curse, e.g. $(x,y)=(0,0)$ assuming $b\ne0$. With this convention, a point $(x,y)$ is on the curve if $(x,y)=(0,0)$ or if $y^2 = x^3 +a x + b$. And the addition law is extended as:

$$(x_0,y_0)+(x_1,y_1)=\begin{cases} (0,0)&\text{ if }(x_0,y_0)=(x_1,-y_1)\\ (x_0,y_0)&\text{ if }(x_1,y_1)=(0,0)\\ (x_1,y_1)&\text{ if }(x_0,y_0)=(0,0)\\ \text{per usual rules }&\text{ otherwise} \end{cases}$$

As noted in comment, the point at infinity has a more natural representation in projective coordinates.

A correct implementation of point addition should give a representation of the point at infinity $\mathcal O$ when asked to compute $P+(-P)$ for $P$ any point on the curve. Note that in Cartesian coordinates, if $P=(x,y)$ and $P\ne\mathcal O$, then $-P=(x,-y)$ or $-P=(x,(p-y)\bmod p)$ depending on conventions. The representation of $\mathcal O$ is not necessarily unique, therefore $P+(-P)=Q+(-Q)$ does not necessarily hold.

$\endgroup$
  • 1
    $\begingroup$ I like that angle of connecting with the group law that requires neutral element of the group operation. Another nice connection would be through projective coordinates - for projective coordinates (x,y,z) we have an affine representation (x/z. y/z) and the only point that cannot be represented that way is the case when z=0 which is exactly the point at infinity. $\endgroup$ – Krystian Feb 18 at 13:10
-1
$\begingroup$

For the secp256k1 curve, there is a point of infinity which is N the total points for this curve. To calculate use scalar multiplication of N and the base generator point for the curve. Another way is to go 2coin.org, go to the private key hex tab, enter the number 1 for the private key press enter. Then subtract by pressing -1 you will be at infinity, press one more time, you are at N-1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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