Trying to Add two Points on ECC but the third point is always not on the curve

user3741124_3741124 0
Viewed 113

I'm using this code to add two points together using finite Fields

    class FieldElement():

      def __init__(self,num,prime):
        if num>=prime or num < 0:
            error = "num s not in field"
            raise ValueError(error)
        self.num = num
        self.prime=prime
    
    def __eq__(self,other):
        if other is None:
            return
        return self.num == other.num and self.prime == other.prime
    def __ne__(self,other):
        return not (self == other)
    def __add__ (self,other):
        if self.prime != other.prime:
            raise ValueError("cannot add two numbers in diffirent fields")
        num = (self.num+other.num)%self.prime
        return self.__class__(num,self.prime)
    def __mul__(self,other):
        if self.prime != other.prime:
            raise ValueError("cannot add two numbers in different fields")
        num = (self.num * other.num)%self.prime
        return self.__class__(num,self.prime)

    def __pow__(self,exponent):
        n = exponent%(self.prime-1)
        num = pow(self.num,n,self.prime)
        return self.__class__(num,self.prime)
    def __sub__(self,other):
        if self.prime != other.prime:
            raise ValueError("cannot add two numbers in different fields")
        num = (other.num - self.num)%self.prime
        return self.__class__(num,self.prime)
    def __truediv__(self,other):
        if self.prime != other.prime:
            raise TypeError("cannot divide two numbers in different Fields")
        num = self.num * pow(other.num,self.prime-2,self.prime)%self.prime
        return self.__class__(num,self.prime)


   class Point ():
    def __init__(self, x,y,a,b):
        self.a = a
        self.b = b
        self.y = y
        self.x = x

        
        if self.x is None and self.y is None:
            return 

        if (self.y**2) != (self.x**3 + a*x + b):
            raise ValueError("{} , {} not in the Curve".format(x.num,y.num))
    def __repr__(self):
        return "Point({},{}){}_{}".format(self.x,self.y,self.a,self.b)
    def __eq__(self,other):
        return self.x == other.x and self.y == other.y and self.a == other.a and self.b == other.b
    def __add__(self,other):
        if other.a != self.a or other.b != self.b:
            raise TypeError("Points{},{} are the same curve".format(self,other))
        
        if self.x is None:
            return other
        if other.x is None:
            return self
        if other.x == self.x and other.y != self.y:
            return self.__class__(None,None,self.a,self.b)
        
        if self != other:
            
            s = (other.y-self.y)/(other.x-self.x)
            x = (s**2 - self.x - other.x)
            y = s*(self.x - x) - self.y
            
            return self.__class__(x,y,self.a,self.b)
        if self == other :
            s = (3*self.x**2+self.a)/(2* self.y)
            x = s**2-2*self.x
            y = s*(self.x-x)-self.y
            return self.__class__(x,y,self.a,self.b)
        if self == other and self.y == 0*self.x:
            return self.__class__(None,None,self.a,self.b)

    def __eq__(self,other):
        return self.x == other.x and self.y == other.y and self.a==other.a and self.b==other.b
    
    def __mul__(self,other):
        numX = self.x * other.x
        numY = self.y * other.y
        return self.__class__(numX,numY,self.a,self.b)

and the bellow code to test it ,

    from test import FieldElement,Point

      prime = 223
      a = FieldElement(num=0,prime=prime)
      b = FieldElement(num=7,prime=prime)
      x1 = FieldElement(num=47,prime=prime)
      y1 = FieldElement(num=71,prime=prime)
      x2 = FieldElement(num=17,prime=prime)
      y2 = FieldElement(num=56,prime=prime)

      p1 = Point(x1,y1,a,b)
      p2 = Point(x2,y2,a,b)
      p3 = p1+p2
      print(p3)

Whatever points I add I get the same error that the third point is not on the the curve, I think the problem is on if (self.y**2) != (self.x**3 + a*x + b) some how it's not checking the new point correctly or Point __add__ method does not calculate the new point correctly, what am missing here ?

elliptic-curve python debugging
2 Answers

You should test every module before use

In the Field, the subtraction is wrong! you calculate b-a not a-b

    def __sub__(self,other):
        if self.prime != other.prime:
            raise ValueError("cannot add two numbers in different fields")
        num = (other.num - self.num)%self.prime
        return self.__class__(num,self.prime)

must be

    def __sub__(self,other):
        if self.prime != other.prime:
            raise ValueError("cannot add two numbers in different fields")
        num = (self.num - other.num)%self.prime
        return self.__class__(num,self.prime)

The other problem as stated in the other answer doesn't make a problem since the first operand is the member of the class, however, you should use

        if (self.y**2) != (self.x**3 + self.a*self.x + self.b):

You should also implement __str__ for your field and point classes to print easy to test your code!

    def __str__(self):
        return num

I've tested and now works. The below is the SageMath Code (test here) that you can compare the result and use a test base for your code.

E = EllipticCurve(GF(223),[0,7])
print(E)
R1 = E(47,71)
R2 = E(17,56)
print(R1+R2)
user_18205530

I think that the line:

if (self.y**2) != (self.x**3 + a*x + b):

should be

if (self.y**2) != (self.x**3 + self.a*self.x + self.b):

as a, x and b will not be treated as field elements.

Daniel_Shiu_153526660
Related