Алгоритм деления точки эллиптической кривой Secp256k1 на число(скаляр)
Как реализовать алгоритм деления на число Z (скаляр) точки, лежащей на эллиптической кривой?
Кривая вида: y^2 = x^3 + A * x + B
A, B и число Z известны.
Точка произвольная, лежащая на кривой. Операции выполняются в кольце вычетов. Более детально:
В случае рассмотрения ЭК над конечном полем, алгоритм деления точки на 2 можно реализовать следующим образом:
ЭК – y^2=x^3+ax+b над полем GF(P),
n – количество точек (включая точку на бесконечности),
P и n – простые числа,
Q – точка на эллиптической кривой, которую необходимо поделить на 2,
W – точка на эллиптической кривой, которую получится в результате, деления Q на 2.
Алгоритм:
Q/2 = W --> W ≡ Q * (2^(-1))(mod n) то есть надо умножать Q на мультипликативно обратное число (inverse) по модулю.
Для 2 inverse (2^(-1)) (mod n) – это тоже самое, что ((n-1)/2)+1.
W ≡ Q * (((n-1)/2)+1)(mod n)
Для любого другого числа r:
W ≡ Q * (r^(-1) mod n)
написал код на python, но вместо деления на 2 точка умножается Результат деления точки на 2:
x=0xe493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13
y=0x51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922
а должно получится
x=0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y=0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
помогите добиться что-бы скрипт делил точку, а не умножал, совсем запутался уже.
# Координаты точки на кривой Secp256k1
x = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
# Коэффициенты кривой Secp256k1
# n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0x0000000000000000000000000000000000000000000000000000000000000000
b = 0x0000000000000000000000000000000000000000000000000000000000000007
# Функция для деления точки на 2
def divide_point_by_2(x, y, p, a, b):
# Вычисление модулярного обратного элемента
def mod_inverse(n, p):
return pow(n, p-2, p)
# Вычисление коэффициента наклона
s = (3 * pow(x, 2) + a) * mod_inverse(2 * y, p) % p
# Вычисление новых координат точки
xr = (pow(s, 2) - 2 * x) % p
yr = (s * (x - xr) - y) % p
return xr, yr
# Деление точки на 2
xr, yr = divide_point_by_2(x, y, p, a, b)
# Вывод результатов
print("Результат деления точки на 2:")
print("x =", hex(xr))
print("y =", hex(yr))