просчет реализации ECDSA на больших целых - PullRequest
Новая
       13

просчет реализации ECDSA на больших целых

0 голосов
/ 18 мая 2018

Я пытаюсь реализовать ECDSA, используя python как часть моей домашней работы. У меня есть функция с именем multiplication, которая принимает два аргумента. Точка P и t вычисляют B= tP. Я реализовал этот алгоритм на основе итеративного двойного вычисления и сложенияАлгоритм на этой странице википедии проблема в том, что когда 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

Вот мой класс Util: 

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

Вот мой класс Point: 

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

Есть ли способ исправить это?

1 Ответ

0 голосов
/ 18 мая 2018

Это было только предположение:

math.pow возвращает число с плавающей запятой (с конечной точностью).Я бы предложил использовать, например, s.x * s.x вместо math.pow(s.x,2) в случае, если проблема касается проблем точности с большими числами.

...