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

yvt65v4c  于 2023-04-21  发布在  其他
关注(0)|答案(2)|浏览(264)

我用这段代码来用有限域把两个点加在一起

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__方法没有正确地计算新点,这里缺少了什么?

l7mqbcuq

l7mqbcuq1#

你应该在使用前测试每个模块
在字段中,减法是错误的!您计算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代码(test here),你可以比较结果,并为你的代码使用一个测试库。

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

yfjy0ee72#

我认为这条线:
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将不被视为域元素。

相关问题