python ECDSA实现对大整数的计算错误

Question

我正在尝试使用 python 实现 ECDSA 作为我作业的一部分，我有一个名为 multiplication 的函数，它有两个参数 Point P 和 t 计算 B= tP .我已经在 this wikipedia page 上实现了基于迭代 double 和 add 算法的算法，问题是当 p 协调很小(一位或两位数)时，该算法工作正常但是当协调很大(大约 70 位)时，结果与什么不同它应该是。这是我计算乘法的代码部分:

def addition(self, p, q):
    if p.is_infinite:
        return q
    elif q.is_infinite:
        return p
    else :
        if (q.x - p.x) == 0:
            point = Point.Point(0, 0)
            point.is_infinite = True
            return point
        s = int(((q.y - p.y) * Utils.Utils.mode_inverse(q.x - p.x, self.prime)) % self.prime)
    xr = int((math.pow(s, 2) - p.x - q.x) % self.prime)
    yr = int(((s * (p.x - xr)) - p.y) % self.prime)
    r = Point.Point(xr, yr)
    return r

def double(self, p):
    if p.is_infinite:
        return p
    if p.y == 0:
        point = Point.Point(0, 0)
        point.is_infinite = True
        return point
    s = int((((3 * math.pow(p.x, 2)) + self.a) * Utils.Utils.mode_inverse(2 * p.y, self.prime)) % self.prime)
    xr = int((math.pow(s, 2) - p.x - p.x) % self.prime)
    yr = int(((s * (p.x - xr)) - p.y) % self.prime)
    r = Point.Point(xr, yr)
    return r

def multiplication(self, p, t):
    bin_t = bin(t)[2:]
    Q = Point.Point(p.x, p.y)
    Q.is_infinite = True
    for i, digit in enumerate(bin_t):
        Q = self.double(Q)
        if digit == '1':
            Q = self.addition(Q, p)
    return Q

这是我的 Util 类:

class Utils(object):
    @staticmethod
    def mode_inverse(a, m):
        return pow(a, m - 2, m)

这是我的点类:

class Point(object):

    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.is_infinite = False

我使用 Curve P-224 参数是:

p = 26959946667150639794667015087019630673557916260026308143510066298881

a = -3

b = 18958286285566608000408668544493926415504680968679321075787234672564

Gx = 19277929113566293071110308034699488026831934219452440156649784352033

Gy = 19926808758034470970197974370888749184205991990603949537637343198772

根据计算器 http://www.christelbach.com/eccalculator.aspx，计算 2G 我应该得到这个结果:

Px = 11838696407187388799350957250141035264678915751356546206913969278886

Py = 2966624012289393637077209076615926844583158638456025172915528198331

但我实际得到的是:

Px = 15364035107168693070617763393106849380516103015030577748254379737088

Py = 7033137909116168824469040716130881489351924269422358605872723100109

有什么办法可以解决这个问题吗？

Answer 1

这只是一个猜测:

math.pow 返回 float (具有有限精度)。我建议使用例如s.x * s.x 而不是 math.pow(s.x,2) 以防遇到更大数字的精度问题。