Как вычислить сложение точек с помощью системы координат Якобиана над эллиптическими кривыми
Я пишу небольшой проект по криптографии эллиптических кривых, и программа хорошо работает, когда я использую аффинную систему координат, что означает, что каждая точка представлена 2 координатами (x',y').
Теперь я пытаюсь заменить аффинную систему координат на якобианскую, в которой каждая точка представлена 3 координатами (x,y,z), x' = x/z² и y' = y/z³.
Я хотел бы узнать, как преобразовать аффинные координаты в якобинские**. В некоторых учебниках используется формула: (x,y) = (x,y,1) что означает, что координата z всегда равна единице. Но я не уверен, что это правильно.
Затем для дополнений точек по эллиптической кривой, чтобы вычислить P(x1,y1,z1) + Q(x2,y2,z2) = R(x3,y3,z3). Я использовал следующие формулы в своей программе:
u1 = x1.z2²
u2 = x2.z1²
s1 = y1.z2³
s2 = y2.z1³
h = u2 - u1
r = s2 - s1
x3 = r² - h³ - 2.u1.h²
Y3 = r. (U1.h² - x3) - s1.h³
z3 = z1.z2.h
Но когда я тестирую свою программу, я получаю некоторые отрицательные координаты, например, (-2854978200,-5344897546224,578). И когда я пытаюсь преобразовать результат обратно в аффинную систему координат с помощью формулы (x'=x/z²,y'=y/z³), я получаю (-8545, -27679), на самом деле координата x равна -8545.689..... Координата x якобиана не делится на z².
Что делать, если координаты не являются целыми числами? И если они отрицательные? Я пробовал MOD с размером поля моей кривой, но результат тоже не правильный.
Итак, точка с координатами якобиана (x,y,1) корректна, но не уникальна. Все точки, удовлетворяющие (a^2.x,a^3.y,a) эквивалентны. А в моей программе кривая определена в простом поле, поэтому когда я вычисляю u1, u2, s1, s2 ... я должен применять MOD p к каждой переменной?
А для преобразования конечного результата обратно в аффинные координаты, например, координату x, на самом деле это не деление, это модульная инверсия? Например, моя кривая определена в конечном простом поле p=11, и у меня есть точка с якобианскими координатами (15,3,2), чтобы преобразовать якобианскую координату x в аффинную координату x, я должен вычислить 2^2 = 4 => x = 4^-1 mod p => x = 3, и 15. 3 mod p = 1, поэтому аффинная координата x равна 1, верно?
Цель якобианских координат - избежать деления при сложении. Но, как сказал Томас Порнин, когда мы вычисляем P1 + P2 = P3, есть несколько особых случаев, которые нужно обработать.
- P1 и P2 оба бесконечны:
P3=infinite. - P1 бесконечен:
P3=P2. - P2 бесконечен:
P3=P1. - P1 и P2 имеют одинаковые координаты x, но разные координаты y или обе координаты y равны 0:
P3=infinite. - P1 и P2 имеют разные координаты x:
Addition formula. - P1 и P2 имеют одинаковые координаты:
Doubling formula.
А вот прототипы моих функций на C:
jac_addition(jacobian *, point *, jacobian *);
jac_doubling(jacobian *, jacobian *);
point - структура, представляющая точку, определенную в аффинной системе координат, и jacobian для якобианной системы.
Проблема в том, что когда я обрабатываю эти особые случаи, особенно 4-й, мне все равно приходится преобразовывать обе точки обратно в аффинные координаты, или я не могу сравнить их координаты, что означает, что мне все равно приходится вычислять деление.