python - 尝试在 ECC 上添加两个点,但第三个点始终不在曲线上
问题描述
我正在使用此代码使用有限字段将两个点相加
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)
和下面的代码来测试它,
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__
方法没有正确计算新点,这里缺少什么?
解决方案
您应该在使用前测试每个模块
在现场,减法是错误的!你算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)
推荐阅读
- c# - 如何在 SQL Server 中根据条件使用 select 语句
- powerbi - 奇怪的 DataFormat.Error:我们无法转换为数字。详情:南
- jmeter - 在 html 报告中生成部分数据
- r - 在 R 中将 na.rm = T 用于 ntile() 时出错
- javascript - Javascript中的IOS Geolocation在返回网页后确实拒绝工作
- flutter - 即使父小部件重建,仍保留小部件的状态
- arrays - 如何从 c 中的字母数组中删除最后一个字符?
- java - Transaction support with asyc channel( executor channel)
- mysql - 使用 Spring Boot 进行远程数据库连接
- python - 多个数据框