šŸ”®
Roll your own crypto
  • šŸ—žļøRoll your own crypto* šŸ”®
  • šŸ‘©ā€šŸ«Introduction to ECC
  • šŸ•“Galois Fields
  • āž°Elliptic Curve in Python
  • šŸŽÆRepresenting a point
  • āž°Group Theory
  • āž•Point Addition in Python
  • āœ–ļøScalar Multiplication in Python
  • šŸ–‹ļøECDSA
  • šŸŽ®Quiz: The Playstation 3 Hack
  • ā¤ļøConclusion
Powered by GitBook
On this page

Was this helpful?

Point Addition in Python

PreviousGroup TheoryNextScalar Multiplication in Python

Last updated 1 year ago

Was this helpful?

Recall from the discussion in Group Theory, we learnt how a generator point can be added to itself repeatedly to generate every element of the group. In this section, we'll understand how to perform this addition, and implement it in Python.

The theory behind point addition

To add two points PPPand QQQ on an elliptic curve, find the third point RRR where line joining PPP and QQQ intersects. This value of RRR is equal to āˆ’(P+Q)-(P+Q)āˆ’(P+Q). Reflecting the point along the X-axis will give us P+QP+QP+Q.

To find the coordinates of the third point of intersection, simply calculate the slope between P and Q, and extrapolate it using the general equation of elliptic curve.

Implementation in Python

from typing import Optional

inf = float("inf")

@dataclass
class Point:
    x: Optional[int]
    y: Optional[int]

    curve: EllipticCurve

    def __post_init__(self):
        # Ignore validation for I
        if self.x is None and self.y is None:
            return

        # Encapsulate int coordinates in FieldElement
        self.x = FieldElement(self.x, self.curve.field)
        self.y = FieldElement(self.y, self.curve.field)

        # Verify if the point satisfies the curve equation
        if self not in self.curve:
            raise ValueError

    def __add__(self, other):
        #################################################################
        # Point Addition for P₁ or Pā‚‚ = I   (identity)                  #
        #                                                               #
        # Formula:                                                      #
        #     P + I = P                                                 #
        #     I + P = P                                                 #
        #################################################################
        if self == I:
            return other

        if other == I:
            return self

        #################################################################
        # Point Addition for X₁ = Xā‚‚   (additive inverse)               #
        #                                                               #
        # Formula:                                                      #
        #     P + (-P) = I                                              #
        #     (-P) + P = I                                              #
        #################################################################
        if self.x == other.x and self.y == (-1 * other.y):
            return I

        #################################################################
        # Point Addition for X₁ ≠ Xā‚‚   (line with slope)                #
        #                                                               #
        # Formula:                                                      #
        #     S = (Yā‚‚ - Y₁) / (Xā‚‚ - X₁)                                 #
        #     Xā‚ƒ = S² - X₁ - Xā‚‚                                         #
        #     Yā‚ƒ = S(X₁ - Xā‚ƒ) - Y₁                                      #
        #################################################################
        if self.x != other.x:
            x1, x2 = self.x, other.x
            y1, y2 = self.y, other.y

            s = (y2 - y1) / (x2 - x1)
            x3 = s ** 2 - x1 - x2
            y3 = s * (x1 - x3) - y1

            return Point(
                x=x3.value,
                y=y3.value,
                curve=secp256k1
            )

        #################################################################
        # Point Addition for P₁ = Pā‚‚   (vertical tangent)               #
        #                                                               #
        # Formula:                                                      #
        #     S = āˆž                                                     #
        #     (Xā‚ƒ, Yā‚ƒ) = I                                              #
        #################################################################
        if self == other and self.y == inf:
            return I

        #################################################################
        # Point Addition for P₁ = Pā‚‚   (tangent with slope)             #
        #                                                               #
        # Formula:                                                      #
        #     S = (3X₁² + a) / 2Y₁         .. āˆ‚(Y²) = āˆ‚(X² + aX + b)    #
        #     Xā‚ƒ = S² - 2X₁                                             #
        #     Yā‚ƒ = S(X₁ - Xā‚ƒ) - Y₁                                      #
        #################################################################
        if self == other:
            x1, y1, a = self.x, self.y, self.curve.a

            s = (3 * x1 ** 2 + a) / (2 * y1)
            x3 = s ** 2 - 2 * x1
            y3 = s * (x1 - x3) - y1

            return Point(
                x=x3.value,
                y=y3.value,
                curve=secp256k1
            )

Point at Infinity

Also known as the identity point, it is the third point where P and Q meet, in the figure below.

P+(āˆ’P)=IP + (-P) = IP+(āˆ’P)=I

We can initialise the point at infinity like this:

I = Point(x=None, y=None, curve=secp256k1)

Resources

āž•
https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture14.pdf
Addition of two points on an elliptic curve over a field of real numbers.
Addition of two points on an elliptic curve over a finite field.
Point at infinity is the third point where the line joining P and Q meets the curve.