Форум сайта python.su
0
Всем здравствуйте! В процессе реализации алгоритма электронной подписи по ГОСТ 34.10-2012 возникла необходимость умножать точки эллиптической кривой на целые числа, иными словами складывать их друг с другом определенное количество раз. Проблема в том, что целые числа в данном алгоритме близки к 2^256 и 2^512. По сути имеется цикл while, который выполняется немыслимое количество раз, близкое как раз к 2^256. Я понимаю, что за разумные промежутки времени этот цикл не закончится.
def MultiPointEK(num, point, a, mod): x1 = point[0] y1 = point[1] newpoint = TwicePointEK(point, a, mod) counter = 2 [b]while counter < num: newpoint = AdditivePointsEK(point, newpoint, mod, a) counter += 1[/b] finpoint = [newpoint[0], newpoint[1]] return finpoint
def AdditivePointsEK(point1, point2, mod, a): if point1[0] == point2[0] and point1[1] == point2[1]: x = point1[0] y = point1[1] p = [x, y] finpoint = TwicePointEK(p, a, mod) else: x1 = point1[0] x2 = point2[0] y1 = point1[1] y2 = point2[1] promezh = (x2 - x1) % mod promezh = evqlid(mod, promezh) h = ((y2 - y1) * promezh) % mod x3 = (h**2 - x1 - x2) % mod while x3 < 0: x3 += mod y3 = (h * (x1 - x3) - y1) % mod while y3 < 0: y3 += mod finpoint = [x3, y3] return finpoint
Отредактировано PaRUS (Май 23, 2016 15:00:09)
Офлайн
88
Офлайн
0
Shaman
https://habrahabr.ru/company/virgilsecurity/blog/301048/
Офлайн
88
Самый простой способ ускориться - запустить на pypy.
Офлайн