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

Question

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

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

Таким образом, точка с использованием якобианских координат (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 для якобинской системы.

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

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², и такой элемент существует, и его можно эффективно рассчитать с использованием расширенного евклидова алгоритма.

Это проще всего, если ваш язык программирования поставляется с некоторой библиотекой больших чисел, в которой предопределены необходимые операции, например, в Java. BigInteger класс (с его 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) (все они в конечном поле, т. Е. Целые числа по модулю p), такие что x = X / Z² и y = Y / Z³.

Каждая точка (x,y) имеет много возможных представлений в виде (X, Y, Z). Преобразование в якобианские координаты легко, если установить 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)