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

Question

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

的代码部分

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

这是我的实用程序 class:

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

这是我的观点class：

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 returns 浮点数（精度有限）。我建议使用例如s.x * s.x 而不是 math.pow(s.x,2)，以防出现更大数字的精度问题。

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

python ECDSA implementation miscalculation on big integers

python

algorithm

ecdsa