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

Question

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 different 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 ?

kelalaka · Accepted Answer · 2021-11-09T16:10:08.797

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)

yah , it is the __sub__ method I knew it was little something I missed , thank you for the advice — user3741124, Mar 08 '21 at 10:01
Step-by-Step testing And each module should have a testing unit that tests it so that during the modifications you can see that where a modification breaks. — kelalaka, Mar 08 '21 at 10:05
Also, once you have a working code, you can ask at codereview.se to review your code. You will learn a lot of experience from that. — kelalaka, Mar 08 '21 at 13:41

score 1 · Answer 2 · edited Mar 08 '21 at 07:27

1

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.

edited Mar 08 '21 at 07:27

fgrieu

2,724
1
23
53

answered Mar 08 '21 at 07:13

Daniel S

111
2

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

2 Answers2