cryptotools/Cryptotools/Groups/elliptic.py

#!/usr/bin/env python3

from Cryptotools.Groups.point import Point
from math import sqrt
import numpy as np


class Elliptic:
    """
        This class generate a group for Elliptic Curve
        An Elliptic Curve is a algebraic group from the Group theory branch.

        An Elliptic Curve is a set of points from this equation (Weierstrass equations): $y2 = x3 + ax + b$


        To generate points of $E(F_p)$, first, we need to generate all square modulos
        The, for all X, we increment it until $X < n$ and if exist a square modulos
        It's a point of the list $E(F_p)$

        Attributes:
            n (Integer): It's the modulo
            a (Integer): 
            b (Integer): 
            squares (Dict): Dictionary which contain quadratic nonresidue. The key is the quadratic nonresidue and for each entry, we have a list of point for the quadratic nonresidue
            E (List): List of all Points
            order (Int): Order (length) of the group
    """
    def __init__(self, n, a, b):
        self._n = n
        self._a = a
        self._b = b

        self._squares = dict()
        self._E = list()
        self._order = 0

    def quadraticResidues(self):
        """
            This function generate all quadratic modulo of n.
            A quadratic: if exist and satisfy $x^2 \equiv q mod n$, means it's a square modulo n and q is quadratic nonresidue modulo n
            https://en.wikipedia.org/wiki/Quadratic_residue

            For instance, n = 13, q = 9
            For all x belongs to n
                for x in n:
                    if x ** 2 % n == q:
                        print(x, q)
        """
        for q in range(self._n):
            x2 = pow(q, 2) % self._n
            if x2 not in self._squares:
                self._squares[x2] = list()
            self._squares[x2].append(q)

    def getQuadraticResidues(self) -> dict:
        """
            This function return the dict contains all squares modulo of n

            Returns:
                Return a dictionary of squares modulo
        """
        return self._squares

    def pointsE(self):
        """
            This function generate all points for $E(F_p)$. Each entry in the list contain another list of two entries: x and y

            Returns:
                Return the list of points of E(F_p)
        """
        self._E.append(Point(0, 0))
        for x in range(self._n):
            y = (pow(x, 3) + (x * self._a) + self._b) % self._n

            # If not quadratic residue, no point in the curve
            # and x not produce a point in the curve
            if y in self._squares:
                for e in self._squares[y]:
                    self._E.append(Point(x, e))
        return self._E

    def additionTable(self):
        raise NotImplementedError

    def _slope(self):
        raise NotImplementedError

    def _curves(self):
        self._curves = dict()
        self._curves["weierstrass"] = weierstrass
        self._curves["curve25519"] = curve25519
        self._curves["curve448"] = curve448

    def weierstrass(self, x):
        raise NotImplementedError

    def curve448(self, x):
        raise NotImplementedError
        
    def curve25519(self, x):
        """
            This function generate a curve based on the Montgomery's curve.
            Using that formula: y2 = x^3 + 486662\times x^2 + x
        """
        y = pow(x, 3) + 486662 * pow(x, 2) + x
        if y > 0:
            return sqrt(y)
        else:
            return 0

    def add(self, P, Q) -> Point:
        """
            This function operathe addition operation on two points P and Q

            Args:
                P (Object): The first Point on the curve
                Q (Object): The second Point on the curve

            Returns:
                Return the Point object R
        """

        ## Check if P or Q are infinity
        if (P.x, P.y) == (0, 0) and (Q.x, Q.y) == (0, 0):
            return Point(0, 0)
        elif (P.x, P.y) == (0, 0):
            return Point(Q.x, Q.y)
        elif (Q.x, Q.y) == (0, 0):
            return Point(P.x, P.y)

        # point doubling
        if P.x == Q.x:
            # Infinity
            if P.y != Q.y or Q.y == 0:
                return Point(0, 0)

            # Point doubling
            try:
                inv = pow(2 * P.y, -1, self._n); # It's working with the inverse modular, WHY ???
                m = ((3 * pow(P.x, 2)) + self._a) * inv % self._n
            except ValueError:
                return Point(0, 0)

        else:
            try:
                inv = pow(Q.x - P.x, -1, self._n)
                m = ((Q.y - P.y) * inv) % self._n
            except ValueError:
                # May call this Exception: base is not invertible for the given modulus
                # I return an Infinity point until I fixed that
                return Point(0, 0)

        xr = int((pow(m, 2) - P.x - Q.x)) % self._n
        
        yr = int((m * (P.x - xr)) - P.y) % self._n
        return Point(xr, yr)

    def scalar(self, P, n) -> Point:
        """
            This function compute a Scalar Multiplication of P, n time. This algorithm is also known as Double and Add.

            Args:
                P (point): the Point to multiplication
                n (Integer): multiplicate n time P

            Returns:
                Return the result of the Scalar multiplication
        """
        binary = bin(n)[2:]
        binary = binary[::-1] # We need to reverse the binary
        
        nP = Point(0, 0)
        Rtmp = P

        for b in binary:
            if b == '1':
                nP = self.add(nP, Rtmp)
            Rtmp = self.add(Rtmp, Rtmp)  # Double P
             
        return nP

    def pointExist(self, P) -> bool:
        """
            This function determine if the Point P(x, y) exist in the Curve
            To identify if a point P (x, y) lies on the curve
            We need to compute y ** 2 mod n
            Then, we compute x ** 3 + ax + b mod n
            If both are equal, the point exist, otherwise not

            Args:
                P (Point): The point to check if exist in the curve

            Returns:
                Return True if lies on the curve otherwise it's False
        """
        y2 = pow(P.y, 2) % self._n
        x3 = (pow(P.x, 3) + (self._a * P.x) + self._b) % self._n
        if y2 == x3:
            return True

        return False

    def findOrder(self) -> int:
        """
            This function find the order of the Curve over Fp

            Returns:
                Return the order of the Curve
        """
        l = list()
        l.append(Point(0, 0))

        # It's the same of the function pointsE
        for x in range(self._n):
            r = (pow(x, 3) + (self._a * x) + self._b) % self._n
            if r in self._squares:
                for s in self._squares[r]:
                    P = Point(x, s)
                    l.append(P)
                
        self._order = len(l)
        return self._order

    @property
    def order(self) -> int:
        """
            This function return the order of the Group
        """
        return self._order

    @property
    def cofactor(self) -> int:
        """
            This function return the cofactor. A cofactor describe the relation between the number of points and the group.
            It's based on the Lagrange's theorem.
        """
        if self._order == 0:
            raise ValueError("You must generate the order of the group")
        return self._order / self._n