One of the key concepts in elliptic curve theory is the point at infinity, also known as the neutral element or identity element. In this post, we’ll explore the significance of this point in elliptic curve cryptography, and how it relates to the addition law and neutral element of the curve. We’ll also take a look at common forms of elliptic curves, including the Weierstrass, Koblitz, Edwards curves, and Twisted Edwards Curves and how they define their respective neutral elements. By the end of this post, you’ll have a deeper understanding of the role that the point at infinity plays in elliptic curve cryptography.
Vlog
Why It Is Being Called Neutral or Identity
Elliptic curves are a type of mathematical curve used in cryptography, particularly in public-key cryptography. One of the key concepts in elliptic curve theory is the point at infinity, denoted as O.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
At first glance, O may seem like an abstract concept, but it’s actually an important part of the geometry of elliptic curves. To understand O, we need to look at how elliptic curves are defined.
Weierstrass Form
Elliptic curves can be in many different forms, but one of the most common forms is the Weierstrass.
This curve defines a curve in a two-dimensional plane, with x and y as the coordinates. However, the curve doesn’t end at any specific point; it goes off to infinity in both positive and negative directions. This is where the point at infinity, O, comes in.
When we talk about the negative of a point on an elliptic curve, we’re talking about the point that when added to the original point, results in O.
R + (-R) = O
As you can see the turquoise line intersecting both R and -R with same x coordinates will intersect the curve at the point at infinity.
Let’s remember the addition law for Weierstrass curves
P(x1, y1) + Q(x2, y2) = R(x3, y3)
ß = (y2 – y1) / (x2 – x1)
x3 = ß2 – x1 – x2
y3 = ß(x1 – x3) – y1
If the coordinates of point P is (x, y), then coordinates of -P is (x, -y) because Weierstrass curves are symmetric about x-axis. Let’s replace those points into addition law.
ß = (-y – y) / (x – x)
So, slope beta is going to be infinite! Then, we will not be able to calculate x3 and y3.
Notice that we just have a point O instead of positive and negative infinite. If you imagine projecting a Weierstrass curve onto a sphere in 3D space, then the positive and negative infinite points become the same point on that sphere.
This point is sometimes called the neutral element or identity element of the curve because it doesn’t change the value of any other point when added to it. This can be proven from the addition of a point and its negative point is point at infinity statement.
P + (-P) = O
P + (-P) + O = 0
P + O = P
Koblitz Curves
Now, let’s look at some variations of elliptic curves and their neutral element. Koblitz curves, for example, have the same point at infinity as Weierstrass curves. This is because Koblitz curves are a type of Weierstrass curve with a specific choice of parameters that make them easier to implement in hardware.
Let’s remember the addition law of Koblitz curves.
P(x1, y1) + Q(x2, y2) = R(x3, y3)
ß = (y1-y2)/(x1-x2)
x3 = ß2 + ß – x1 – x2 – a
y3 = ß(x1 – x3) – x3 – y1
Besides, negative point of a point (x, y) was (x, -(x+y)) in Koblitz curves. Please follow the tutorial of Koblitz curves if you wonder how to calculate the negative point of a given point.
If we add those points according to the addition law:
ß = (-(x+y) – y) / (x – x)
Slope beta is going to be infinity, and we will not be able to calculate x3, y3.
Edwards Curves
On the other hand, Edwards curves are a little bit different than Weierstrass. In these curves, the point (0, 1) is used as the neutral element or identity element instead of point at infinity.
The graph of an Edwards curve doesn’t appear to go off to infinity in the same way that the graph of a Weierstrass curve and Koblitz curve do. This is because Edwards curves are often represented using a projection that maps the curve onto a finite space. That is why, we are calling it as neutral element or identity element instead of infinite point in Edwards curves. However, it’s important to note that the curve itself is still infinite and has points that go off to infinity.
In Edwards curves, point O related calculation results are same with Weierstrass or Koblitz curves. The only difference is Point O has concrete coordinates which is (0, 1) whereas Weierstrass and Koblitz curves have an point at infinity with abstract coordinates.
P + (-P) = O = (0, 1)
P + O = P + (0, 1) = P
Let’s remember the addition law of Edwards curves
(x1, y1) + (x2, y2) = (x3, y3)
x3 = (x1y2 + x2y1)/(1+dx1y1x2y2)
y3 = (y1y2 – x1x2)/(1 – dx1y1x2y2)
If we replace the (x2, y2) to the neutral point (0, 1)
x3 = (x1.1 +0.y1)/(1+dx1y1.0.1) = x1
y3 = (y1.1 – x1.0)/(1 – dx1y1.0.1) = y1
Then, the third point will be first point (x1, y1) itself. So, really point (0, 1) is neutral element or identity element for Edwards curves.
Similarly, we can prove P + (-P) = O statement. Negative point of (x, y) is (-x, y) in Edwards curves. Let’s add these points.
x3 = (x1y2 + x2y1)/(1+dx1y1x2y2) = (xy – xy) / (1 – xyxy) = 0 / (1 – xyxy) = 0
y3 = (y1y2 – x1x2)/(1 – dx1y1x2y2) = (yy + xx) / (1 + dxxyy )
Here, edwards curve formula was x2 + y2 = 1 + dx2y2. If we replace the left hand side of this calculation in the y3 calculation:
y3 = (yy + xx) / (1 + dxxyy) = (1 + dx2y2) / (1 + dxxyy) = 1
Really, we got neutral point (0, 1) if we add (x, y) and (x, -y). So, we proven the addition law for neutral element on edwards curves.
Similarly, twisted Edwards curves have same neutral point but they come with a little bit different addition laws.
Conclusion
In summary, the point at infinity and neutral element are integral concepts in elliptic curve cryptography. They are essential for the addition law of elliptic curves and are used in various cryptographic applications. Understanding these concepts is crucial for comprehending the underlying algebraic structures and security properties of elliptic curves.
Like this blog? Support me on Patreon
