Как вычислить сложение точек, используя систему координат Якоби по эллиптическим кривым

Question

Я пишу небольшой проект криптографии с эллиптическими кривыми, и программа работает хорошо, когда я использую аффинную систему координат, что означает, что каждая точка представлена ​​двумя координатами (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².

Что делать, если координаты не являются целыми числами?А если они отрицательные?Я попытался изменить размер поля моей кривой, но результат также не верен.

Таким образом, точка, использующая якобианские координаты (x,y,1), верна, но не уникальна.Все точки, удовлетворяющие (a^2.x,a^3.y,a), эквивалентны.И в моей программе кривая определена в простом поле, поэтому, когда я вычисляю u1, u2, s1, s2 ..., я должен применить MOD p к каждой переменной?

И для преобразования конечного результата обратно в аффинные координаты, например, координата Xна самом деле это не деление, это модульное обратное? Например, моя кривая определена в конечном простом поле p=11, и у меня есть точка, использующая якобианские координаты (15,3,2), для преобразованияЯкобианская координата х для аффинной координаты х, я должен вычислить 2^2 = 4 => x = 4^-1 mod p => x = 3 и 15.3 mod p = 1, поэтому аффинная координата х равна 1, верно?

Цель якобианских координат - избежать деления во времядополнение.Но, как сказал Томас Порнин, когда мы вычисляем P1 + P2 = P3, есть несколько особых случаев, которые нужно обработать.

1. P1 и P2 оба бесконечны: P3=infinite.
2. P1 бесконечен: P3=P2.
3. P2 бесконечен: P3=P1.
4. P1 и P2 имеют одинаковую координату x, но разные координаты y или обе координаты y равны 0: P3=infinite.
5. P1 и P2 имеют разные координаты x: Addition formula.
6. P1 и P2 имеют одинаковые координаты: Doubling formula.

А вот прототипы моих функций C:

jac_addition(jacobian *, point *, jacobian *);
jac_doubling(jacobian *, jacobian *);

point - это структура, представляющая точку, определенную в аффинной системе координат, и jacobian для якобианской системы.

Проблема заключается в том, что я рассматриваю эти особые случаи, особенночетвертое - мне все еще нужно преобразовать обе точки обратно в аффинные координаты, или я не могу сравнить их координаты, а это значит, что мне все еще нужно вычислить деление.

Answer 1

Якобианская форма проективных координат (как и любая другая форма) не является уникальной - для каждого значения Z (кроме 0) вы получаете другие X и Y без фактического изменения точки.

Таким образом, если у вас есть точка в аффинных координатах (X', Y'), пара (X', Y', 1) является проективным представителем этой точки, а также (4·X', 8·Y', 2), (9·X', 27·Y', 3) и т. Д. Та, у которой 1, является самой простой чтобы создать, поэтому обычно вы бы использовали этот.

В то время как можно определять (и изучать) эллиптические кривые по любому полю, и многие математики изучают кривые, определенные по комплексным числам, для криптографического использования координаты являются элементами некоторого конечного поля. В простейшем случае у нас есть простое поле (то есть целые числа по модулю простого числа), и вам придется выполнять сложение, вычитание, умножение и деление (и, возможно, возведение в степень) в этом поле.

Пока Z не равен нулю, вы должны иметь возможность делить на Z² - это эквивалентно умножению на обратное значение Z², и такой элемент существует, и его можно эффективно рассчитать с использованием расширенного евклидова алгоритм.

Это проще всего, если ваш язык программирования поставляется с некоторой библиотекой больших чисел, в которой предопределены необходимые операции, такие как класс BigInteger Java (с его методами mod, modPow и modInverse).

Рассматриваемое поле (то есть модуль) является частью определения эллиптической кривой, и операции над одним полем дают совершенно другие результаты, чем операции в другом. Поэтому убедитесь, что вы используете правильное поле.

Answer 2

При работе с эллиптическими кривыми координаты находятся в поле . Для криптографии это конечное поле ; в вашем случае "целые числа по модулю простого числа p ". Все операции предназначены для этой области, т. Е. Вы должны выполнять каждое сложение, умножение или инверсию по модулю p .

При добавлении очков есть несколько особых случаев, которые вы должны специально обработать:

• Существует специальная «точка на бесконечности», у которой нет координат x и y . Это «ноль» кривой сложения. В обычной процедуре сложения точек у вас должен быть способ кодировать «точку на бесконечности» и проверять ее специально.

• При добавлении (x, y) к (x ', y') может случиться так, что x = x '. В этом случае либо y = y ', а затем это удвоение точки , которое имеет свою особую формулу (если вы примените универсальную формулу, вы в конечном итоге разделитесь на ноль, что не будет работать); или y = -y ', в этом случае сумма является «точкой на бесконечности».

Таким образом, универсальная формула должна применяться только после того, как вы обработаете специальный случай. В целом, в кривой y ² = x ³ + a · x + b , сумма (x ₁ , y ₁ ) и (x ₂ , y ₂ ) равно (x ₃ , y ₃ ) такое, что x ₃ = f ² -x ₁ -x ₂ и y ₃ = f · (x ₁ -x ₃ ) - y ₁ , где f = (y ₂ -y ₁ ) / (x ₂ -x ₁ ) . Это подразумевает вычисление одного деления, двух умножений и нескольких вычитаний (все операции выполняются с целыми числами по модулю p , как описано выше).

Деление и инверсия по модулю p относительно дороги (модульное деление обычно стоит столько же, сколько около 80 умножений), поэтому в некоторых ситуациях мы используем проективные или якобианские системы координат . Якобианские координаты означают представление точки в виде трех значений (X, Y, Z) * ​​1104 * (все они в конечном поле, т.е. целые числа по модулю p ), такие что x = X / Z ² и y = Y / Z ³ .

Каждая точка (x, y) имеет много возможных представлений как (X, Y, Z) * ​​1120 *. Преобразование в Якобианские координаты легко выполнить, установив X = x , Y = y и Z = 1 : (x, y, 1) - совершенно верное якобианское представление точки (x, y) . Преобразование из координат Якобиана сложнее в вычислительном отношении: вам нужно выполнить модульную инверсию и несколько умножений (вы вычисляете U = 1 / Z , затем x = X · U ² и y = Y · U ³ ).

С помощью якобианских координат сложение двух точек производится в дюжине полевых умножений, без деления вообще. Вы получаете только якобианское представление результата, поэтому вам все равно придется делать модульную инверсию или деление в некоторой точке; однако (и именно поэтому вы беспокоитесь об использовании якобианских координат), это деление может быть взаимным. Если вам нужно сделать около сотни последовательных сложений точек (как это обычно бывает в криптографическом контексте при «умножении» точки на целое число), то вы можете использовать повсеместно представления Якоби и выполнять одно преобразование обратно в декартовы координаты (х, у) в конце. Таким образом, вместо 200 умножений и 100 делений, вы делаете 1000 умножений и 1 инверсию; поскольку инверсия стоит столько же, сколько и 80 умножений, выигрыш заметен.

Попробуйте воспользоваться этой книгой ; любая хорошая библиотека колледжа должна иметь такую. Все это объясняется очень четко.

Answer 3

Вот пример в Python:

def to_jacobian((Xp, Yp)):
    """
    Convert point to Jacobian coordinates

    :param (Xp,Yp,Zp): First Point you want to add
    :return: Point in Jacobian coordinates
    """
    return (Xp, Yp, 1)

def from_jacobian((Xp, Yp, Zp), P):
    """
    Convert point back from Jacobian coordinates

    :param (Xp,Yp,Zp): First Point you want to add
    :param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p)
    :return: Point in default coordinates
    """
    z = inv(Zp, P)
    return ((Xp * z**2) % P, (Yp * z**3) % P)

def jacobian_add((Xp, Yp, Zp), (Xq, Yq, Zq), A, P):
    """
    Add two points in elliptic curves

    :param (Xp,Yp,Zp): First Point you want to add
    :param (Xq,Yq,Zq): Second Point you want to add
    :param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p)
    :param A: Coefficient of the first-order term of the equation Y^2 = X^3 + A*X + B (mod p)
    :return: Point that represents the sum of First and Second Point
    """
    if not Yp:
        return (Xq, Yq, Zq)
    if not Yq:
        return (Xp, Yp, Zp)
    U1 = (Xp * Zq ** 2) % P
    U2 = (Xq * Zp ** 2) % P
    S1 = (Yp * Zq ** 3) % P
    S2 = (Yq * Zp ** 3) % P
    if U1 == U2:
        if S1 != S2:
            return (0, 0, 1)
        return jacobian_double((Xp, Yp, Zp), A, P)
    H = U2 - U1
    R = S2 - S1
    H2 = (H * H) % P
    H3 = (H * H2) % P
    U1H2 = (U1 * H2) % P
    nx = (R ** 2 - H3 - 2 * U1H2) % P
    ny = (R * (U1H2 - nx) - S1 * H3) % P
    nz = (H * Zp * Zq) % P
    return (nx, ny, nz)

Таким образом, вы можете суммировать с:

def fast_add(a, b, A, P):
    return from_jacobian(jacobian_add(to_jacobian(a), to_jacobian(b), A, P), P)