Как добавить точки эллиптической кривой в python?
Я пытаюсь реализовать простую программу шифрования эллиптической кривой, но я не могу получить ожидаемый результат удвоения и добавления точки P до 12P. Уравнение кривой y^2 = x^3 +ax + b mod p. Согласно этому сайту 3P = [10, 6] когда P = [5, 1] пока получу 3p = [10, 5]. Уравнения, которые я использую, можно найти в Википедии.
P = [5, 1]
prime = 17
a = 2
b = 2
def gcdExtended(a, b):
if a == 0:
return b, 0, 1
gcd, x1, y1 = gcdExtended(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
def double_point(point: list):
x = point[0]
y = point[1]
s = ((3*(x**2)+a) * (gcdExtended(2*y, prime)[1])) % prime
newx = (s**2 - x - x) % prime
newy = (s * (x - newx) - y) % prime
return [newx, newy]
def add_points(P: list, Q: list):
x1 = P[0]
y1 = P[1]
x2 = Q[0]
y2 = Q[1]
s = ((y2 - y1) * ((gcdExtended(x2-x1, prime))[1] % prime)) % prime
newx = (s**2 - x1 - x2) % prime
newy = (s * (x1 - newx) - y1) % prime
return [newx, newy]
Q = P
index = 2
while True:
if Q[0] == P[0] and Q[1] == P[1]:
print("doubling")
Q = double_point(P)
else:
print("adding")
Q = add_points(Q, P)
if index == 12 :
break
print(f"{index}P = {Q}")
index += 1
Ответы 2
Вы поменяли местами P и Q в add_points. Также небольшое упрощение в вашем расчете s:
def add_points(P: list, Q: list):
x1 = P[0]
y1 = P[1]
x2 = Q[0]
y2 = Q[1]
#s = ((y2 - y1) * ((gcdExtended(x2-x1, prime))[1] % prime)) % prime
s = (y2-y1) * (gcdExtended(x2-x1, prime)[1] % prime)
newx = (s**2 - x1 - x2) % prime
newy = (s * (x1 - newx) - y1) % prime
return [newx, newy]
Q = P
index = 2
while True:
if Q[0] == P[0] and Q[1] == P[1]:
print("doubling")
Q = double_point(P)
else:
print("adding")
Q = add_points(P, Q)
if index == 12 :
break
print(f"{index}P = {Q}")
index += 1
что приводит к
doubling
2P = [6, 3]
adding
3P = [10, 6]
adding
4P = [3, 1]
adding
5P = [9, 16]
adding
6P = [16, 13]
adding
7P = [0, 6]
adding
8P = [13, 8]
adding
9P = [8, 7]
adding
10P = [8, 10]
adding
11P = [13, 9]
adding
Если точку [5,1] добавлять последовательно, получается следующая последовательность:
1P = [ 5, 1]
2P = [ 6, 3]
3P = [10, 6]
4P = [ 3, 1]
5P = [ 9, 16]
6P = [16, 13]
7P = [ 0, 6]
8P = [13, 7]
9P = [ 7, 6]
10P = [ 7, 11]
11P = [13, 10]
12P = [ 0, 11]
13P = [16, 4]
14P = [ 9, 1]
15P = [ 3, 16]
16P = [10, 11]
17P = [ 6, 14]
18P = [ 5, 16]
19P = point at infinity
Это можно проверить, например. здесь.
Проблема в опубликованном коде заключается в том, что метод определения модульной инверсии gcdExtended(a, b) действителен только для положительных a и b. В то время как в double_point и add_pointsb имеет значение prime (= 17 > 0), a может принимать отрицательные значения.
gcdExtended обычно возвращает неверные значения для отрицательного a:
- Модульная инверсия 5 или -12 равна 7: 5 x 7 mod17 = 35 mod17 = 1 и 7 x (-12) mod17 = -84 mod17 = 85 mod17 = 1.
gcdExtendedвозвращает следующие значения:gcdExtended(5, 17)[1] = 7(верно) иgcdExtended(-12, 17)[1] = -7(ложно).
Чтобы разрешить отрицательные значения для a, например. могут быть определены следующие методы, см. здесь:
def sign(x):
return 1 if x >= 0 else -1
def gcdExtendedGeneralized(a, b):
gcd, x1, y1 = gcdExtended(abs(a), b)
return gcd, (sign(a) * x1) % b, y1 % b
Замена gcdExtended на gcdExtendedGeneralized в double_point и add_points дает правильные значения (обратите внимание, что текущая реализация не учитывает точку в бесконечности).
На самом деле сложение точек должно быть коммутативным, поэтому замена
PиQвadd_points(P, Q)не должна иметь никакого эффекта.