Я пытаюсь реализовать алгоритм «удвоить и добавить», чтобы быстро умножить точки на эллиптической кривой в Python (3, пожалуйста).
Основываясь на этом предыдущем ответе (о сложении и удвоении),
Сложение точек эллиптической кривой над конечным полем в Python а>
страница Википедии,
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
и мой учебник («Информационная безопасность» Марка Стэмпа) я придумал следующий код:
def point_add(N_x, N_y, Q_x, Q_y, p):
m = (Q_y - N_y) * pow((Q_x-N_x), p-2, p)
ret_x = (m ** 2 - N_x - Q_x) % p
ret_y = (m*(N_x - ret_x) - N_y) % p
return ret_x, ret_y
def point_double(N_x, N_y, a, p):
m = (3*(N_x ** 2)+a) * pow(2*N_y, p-2, p)
ret_x = (m ** 2 - N_x - Q_x) % p
ret_y = (m*(N_x - ret_x) - N_y) % p
return ret_x, ret_y
multiplier_A = 44
multiplier_B = 57
a = 10
b = -21
p = 41
N_x = 3
N_y = 6
Q_x = 0
Q_y = 0
multiplier_A = list(bin(multiplier_A)[2:])
multiplier_B = list(bin(multiplier_B)[2:])
for x_a in multiplier_A:
if x_a == '1':
Q_x, Q_y = point_add(N_x, N_y, Q_x, Q_y, p)
N_x, N_y = point_double(N_x, N_y, a, p)
print(Q_x, Q_y)
Что, конечно же, возвращает неверный результат.
Где я ошибаюсь? Новая реализация с нуля также более чем приветствуется.
ОБНОВЛЕНИЕ
Я хочу умножить точку (3,6) на multiplier_A
и multiplier_B
. Пока я пытаюсь делать только multiplier_A(3,6)
.
a
, b
и p
— параметры эллиптической кривой.