尝试在 ECC 上添加两个点，但第三个点始终不在曲线上

Question

我正在使用此代码使用有限域将两个点加在一起

    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)

和下面的代码来测试它，

    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)

无论我添加什么点，我都会得到同样的错误，即第三点不在曲线上，我认为问题出在

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

一些它如何不正确检查新点或

Point __add__

方法不计算新点正确，这里缺少什么？

Answer 1

您应该在使用前测试每个模块

Field里，减法是错误的！你计算

b-a

不是

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)

必须

    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)

另一个答案中所述的另一个问题不会造成问题，因为第一个操作数是类的成员，但是，您应该使用

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

您还应该为您的字段和点类实现

__str__

，以轻松打印以测试您的代码！

    def __str__(self):
        return num

我已经测试过，现在可以用了。以下是 SageMath 代码 （在此处测试） 您可以比较结果并为您的代码使用测试基础。

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

Answer 2

我认为这条线：

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

应该是

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

因为 a、x 和 b 不会被视为字段元素。