Алгоритм Монтгомери по лестнице работает медленнее, чем предполагалось - PullRequest
Новая
       58

Алгоритм Монтгомери по лестнице работает медленнее, чем предполагалось

1 голос
/ 31 января 2020

Я реализовывал лестницу Монтгомери в python, и когда я попытался запустить ее, она была довольно маленькой, она стала очень медленной. Что я делаю не так? 

def addPoints(xp, zp, xq, zq, xpq, zpq):
    u = (xp + zp) * (xq - zq)
    v = (xp - zp) * (xq + zq)
    w = u + v
    t = u - v
    w = w * w
    t = t * t
    X = w * zpq
    Z = t * xpq
    return X, Z

def duplicatePoint(xp, zp, b):
    u = xp + zp
    v = xp - zp
    u = u * u
    v = v * v
    uv = u - v
    t = b * uv + v
    x2p = u * v
    z2p = uv * t
    return x2p, z2p

def montgomeryLadder(k, px, pz, a24):
    qx, qz = px, pz
    rx, rz = duplicatePoint(px, pz, a24)
    for i in bin(k)[3:]:
        print(i)
        if i == 1:
            qx, qz = addPoints(rx, rz, qx, qz, px, pz)
            rx, rz = duplicatePoint(rx, rz, a24)
        else:
            rx, rz = addPoints(qx, qz, rx, rz, px, pz)
            qx, qz = duplicatePoint(qx, qz, a24)

    return qx, qz

Алгоритм показан здесь: https://www.iacr.org/archive/ches2006/10/10.pdf

Я знаю, что он не должен работать так медленно, потому что он должен быть одним из самых быстрых алгоритмов скалярного умножения точек на кривой эллипти c. Тестовый пример, который я использовал, был: montgomeryLadder(80219347, 3, 2, 5), и я на 100% уверен, что он не должен работать так.

...