Дополнение по эллиптическим кривым

_{Отказ от ответственности: это не делает никакой справедливости по богатой теме эллиптических кривых. Это сильно упрощено. Поскольку в последнее время эллиптические кривые привлекли большое внимание средств массовой информации в контексте шифрования, я хотел дать небольшое представление о том, как на самом деле работает «расчет» по эллиптической кривой.}

Введение

Эллиптические кривые - это множества точек (x,y)на плоскости формы y^2 = x^3+Ax+B. (Кроме того, 4A^3+27B^2 ≠ 0чтобы избежать неприятных особенностей.) Вы можете рассмотреть эти кривые в любой области. Если вы используете поле действительных чисел, кривые можно визуализировать, и они выглядят так:

_{Источник}

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

Как работает сложение?

Примечание: добавление точек на эллиптических кривых не является интуитивно понятным. Такое дополнение определяется так, как оно есть, потому что оно обладает определенными хорошими свойствами. Это странно, но это работает.

Поскольку эллиптические кривые образуют группу, существует аддитивная идентичность, которая эквивалентна 0. То есть добавление 0к любой точке не изменит результат. Эта аддитивная идентичность является «точкой» на бесконечности. Все линии на плоскости включают эту точку на бесконечности, поэтому ее добавление не имеет значения.

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

_{Источник}

Естественный вопрос: что это P+Q? Хорошо, если P+Q+R = 0, тогда P+Q = -R(альтернативно написано как R'). Где -R? Именно здесь R + (-R) = 0, который находится на другой стороне оси х от Rтак, чтобы линия , проходящая через них в вертикальном положении , пересекающихся только R, -Rи 0. Вы можете увидеть это в первой части этого изображения:

_{Источник}

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

Как найти пересечения прямых и эллиптических кривых

В случае двух разных точек

Обычно проходит ровно одна линия через две точки P=(x0,y0), Q=(x1,y1). Предполагая, что он не вертикальный и две точки различны, мы можем записать это как y = m*x+q. Когда мы хотим найти точки пересечения с эллиптической кривой, мы можем просто написать

0 = x^3+Ax+B-y^2 = x^3+Ax+B-(m*x+q)^2

который является полиномом третьей степени. Как правило, их не так просто решить, но мы уже знаем два нуля этого многочлена: две xкоординаты x0, x1двух точек, которые мы хотим добавить!

Таким образом, мы вычленяем линейные множители (x-x0)и получаем (x-x1)третий линейный множитель, корнем которого является x-координата точки R. ( -Rтоже из-за симметрии. Обратите внимание, что если R = (x2,y2)тогда -R = (x2,-y2). Это -из группы; это не векторный минус.)

В случае добавления одной точки Pк себе

В этом случае мы должны вычислить тангенс кривой в P=(x0,y0). Мы можем напрямую написать mи qс точки зрения A,B,x0,y0:

     3*x0^2 + A
m = ------------
        2*y0

     -x0^3 + A*x0 + 2*B
q = --------------------
          2*y0

Мы получаем уравнение y = m*x+qи можем действовать так же, как в предыдущем абзаце.

Полное дерево дел

Вот полный список того, как обращаться со всеми этими случаями:

Позвольте P,Qбыть точки на эллиптической кривой (включая точку "бесконечности" 0)

• Если P = 0или Q = 0, то P+Q = Qили P+Q = P, соответственно
• Остальное P ≠ 0а Q ≠ 0, так пусть P = (x0,y0)и Q = (x1,y1):
  • Если P = -Q(это означает x0 = x1и y0 = -y1), тоP+Q = 0
  • еще P ≠ -Q
    • Если x0 = x1тогда у нас есть P=Qи мы вычисляем касательную (см. Раздел выше), чтобы получить R. затемP+Q = P+P = 2P = -R
    • Иначе: мы можем построить линию формы y = m*x+yчерез эти две точки (см. Раздел выше) для расчета R. затемP+Q=-R

Конечные поля

Для этой задачи мы будем рассматривать только поля размера, pгде pпростое число (и из-за некоторых деталей p ≠ 2, p ≠ 3). Это имеет то преимущество, что вы можете просто рассчитать mod p. Арифметика в других областях намного сложнее.

Это в этом примере мы устанавливаем p = 5и все равенства здесь являются конгруэнциями mod 5.

2+4 ≡ 6 ≡ 1
2-4 ≡ -2 ≡ 3
2*4 ≡ 8 ≡ 3
2/4 ≡ 2*4 ≡ 3 because 4*4 ≡ 16 ≡ 1, therefore 1/4 ≡ 4

Вызов

Учитывая параметры A,Bэллиптической кривой, характеристику простого поля pи две точки P,Qна эллиптической кривой, вернуть их сумму.

• Вы можете предположить, что параметры A,Bдействительно описывают эллиптическую кривую, это означает, что 4A^3+27B^2 ≠ 0.
• Вы можете предположить, что P,Qна самом деле это точки на эллиптической кривой или 0-точке.
• Вы можете предположить, что p ≠ 2,3это главное.

Тестовые случаи

Я сделал (не очень элегантную) реализацию в MATLAB / Octave, которую вы можете использовать для своих собственных тестов: ideone.com Я надеюсь, что это правильно. По крайней мере, он воспроизвел несколько расчетов, которые я сделал вручную.

Обратите внимание на тривиальные тестовые случаи, которые работают для всех кривых, которые мы здесь рассматриваем:

Добавление нуля: P+0 = P добавление обратного:(x,y) + (x,-y) = 0

Для p = 7, A = 0, B = 5двух точек P = (3,2)и Q = (6,2)находятся на эллиптической кривой. Тогда имеет место следующее:

2*Q = Q+Q = P
2*P = P+P = (5,2)
3*P = P+P+P = (5,2)+P = (6,5)
4*P = P+P+P+P = (5,2)+(5,2) = (6,5)+(5,2) = Q

Все точки на эллиптической кривой (3,2),(5,2),(6,2),(3,5),(5,5),(6,5),0

Ибо p = 13, A = 3, B = 8мы получаем

(1,8)+(9,7) = (2,10)
(2,3)+(12,11) = (9,7)
2*(9,6) = (9,7)
3*(9,6) = 0

Для p = 17, A = 2, B = 2и P=(5,1) мы получаем

2*P = (6,3)
3*P = (10,6)
4*P = (3,1)
5*P = (9,16)
6*P = (16,13)
7*P = (0,6)
8*P = (13,7)
9*P = (7,6)
10*P = (7,11)

Если вы действительно амбициозны, возьмите

p = 1550031797834347859248576414813139942411
A = 1009296542191532464076260367525816293976
x0 = 1317953763239595888465524145589872695690
y0 = 434829348619031278460656303481105428081
x1 = 1247392211317907151303247721489640699240
y1 = 207534858442090452193999571026315995117

и попытаться найти натуральное число nтакое, что n*(x0,y0) = (x1,y1). Дополнительная информация здесь.

аппендикс

Прежде всего, большое СПАСИБО @ El'endiaStarman за просмотр и редактирование моего черновика!

Почему эллиптические кривые?

Ну, это может выглядеть как какое-то произвольное уравнение, но это не так, оно довольно общее: обычно мы рассматриваем эти геометрические «фигуры» в проективной плоскости ( именно отсюда исходит «бесконечность». Там мы считаем все однородным полиномы третьей степени. (Те, которые имеют более низкую или более высокую степень, будут слишком сложными или просто тривиальными для изучения.) После применения некоторых ограничений для получения нужных нам свойств и после дегомогенизации этих полиномов (проецирование в одну из трех аффинных плоскостей ) мы в конечном итоге с уравнениями, такими какy^2+a*x*y+b*y = x^3+c*x^2+d*x+eЭто эллиптическая кривая в длинной форме Вейерштрасса. Это в основном те же кривые, которые мы рассматривали, но только несколько искаженные. С помощью линейного преобразования координат вы можете легко сделать из этого короткое уравнение Вейерштраса. пример , в котором до сих пор хранятся все интересные свойства.

Почему мы исключили p=2,3?

Это связано с тем, что для короткой формы Вейерштрасса нам нужно ограничение 4A^3+27B^2 ≠ 0, чтобы избежать сингулярностей (подробнее об этом ниже). В поле характеристики 2, которое мы имеем, 4 = 0и в поле характеристики 3, которое мы имеем 27 = 0, это делает невозможным получение кривых в короткой форме Вейерштрасса для этих типов полей.

Каковы особенности?

Если уравнение 4A^3+27B^2=0выполнено, у нас есть особенности типа следующего: как вы видите в этих точках, вы не можете найти производную и, следовательно, не касательную, которая «убивает» операцию. Вы можете посмотреть на уравнения y^2 = x^3илиy^2 = x^3-3*x+2

В любом случае, почему они называются эллиптическими кривыми ?

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

Какое отношение они имеют к криптографии?

Есть способы вычислить nP = P+P+...+Pочень эффективно. Это можно использовать, например, при обмене ключами Диффи-Хеллмана . Модульная арифметика может быть заменена сложением на торсионных подгруппах, это только точки на кривой, имеющие конечный порядок. (Это означает, что mP = 0для некоторых m, что в основном просто расчет mod m).

Pyth, 105 100 байт

A,@Q3eQ?qGZH?qHZG?&=YqhHhGqeG%_eHhQZ_m%dhQ,-*J?Y*+*3^hG2@Q1^*2eG-hQ2*-eGeH^-hGhH-hQ2-hGK--^J2hGhHeGK

Ввод ожидается как (p, A, P, Q), где Pи Qдве точки формы (x, y)или, если они являются специальной 0точкой, так же, как 0. Вы можете попробовать это онлайн здесь . Последние два примера показывают, как 0работает спец .

Чтобы сэкономить несколько байтов, я использую только mod pокончательный ответ. Это означает, что он работает x0^pнесколько раз без модульного возведения в степень, поэтому он может быть очень медленным.

Он работает, следуя примерно той же логике, что и эта функция Python:

def add_ellip(p, A, P, Q): # points are in format (x, y)
    z = 0 # representing special 0 point

    if (P == z):
        return Q
    if (Q == z):
        return P

    if P[0] == Q[0]:
        if (P == (Q[0], -Q[1] % p)):
            return z
        else:
            m = ((3*pow(P[0], 2, p) + A)*pow(2*P[1], p-2, p)) % p
    else:
        m = (P[1] - Q[1])*pow(P[0] - Q[0], p-2, p) % p

    x = (pow(m, 2, p) - P[0] - Q[0]) % p
    y = (m*(P[0] - x) - P[1]) % p
    return (x, y)

Это в значительной степени зависит от того факта, что модульная мультипликативная обратная xравна, x^(p-2) mod pесли pпростое число. Таким образом, мы можем вычислить mнаклон линии, найдя модульную мультипликативную инверсию знаменателя и умножив ее на числитель. Довольно удобно. Функция Python должна вычислять большие задачи немного эффективнее из-за использования pow.

Я также использовал ярлыки, показанные на странице Википедии на эту тему . Это довольно интересно, я использую Aтолько один раз, а Bне совсем.

Также просто для удовольствия:

def pow2floor(x):
    p = 1
    x >>= 1
    while (x > 0):
        x >>= 1
        p <<= 1
    return p

def multi_nP(p, A, n, P):
    d = {}

    def rec_helper(n, P):
        if (n == 0):
            return (0, 0)
        elif (n == 1):
            return P
        elif (n in d):
            return d[n]
        else:
            p2f = pow2floor(n)
            remainder = n - p2f

            lower_half = rec_helper(p2f//2, P)
            d[p2f//2] = lower_half
            nP = add_ellip(p, A, lower_half, lower_half)

            if (remainder):
                nP = add_ellip(p, A, nP, rec_helper(remainder, P))

            d[n] = nP
            return nP

    return rec_helper(n, P)

multi_nPФункция вычисляет n*Pдля заданного целого числа nи точки P. Он использует рекурсивную стратегию, разделяясь nна две части p2fи remainderтакие, которые p2f + remainder = nи те p2f = 2^k. Затем мы снова вызываем функцию для этих частей, добавляя результат с помощью add_ellip. Я также использовал базовый подход динамического программирования, сохраняя уже вычисленные значения в формате dict d.

Следующая функция теоретически решит бонусный вопрос, используя ту же стратегию:

def find_nPQ(p, A, P, Q): # P is input point, Q is what we're looking for
    d = {}
    found_Q = False

    def rec_helper(n, P):
        if (n == 0):
            return (0, 0)
        elif (n == 1):
            return P
        elif (n in d):
            return d[n]
        else:
            p2f = pow2floor(n)
            remainder = n - p2f

            lower_half = rec_helper(p2f//2, P)
            d[p2f//2] = lower_half

            nP = add_ellip(p, A, lower_half, lower_half)

            if (remainder):
                nP = add_ellip(p, A, nP, rec_helper(remainder, P))

            d[n] = nP
            return nP


    for x in range(p):
        xP = rec_helper(x, P)
        if (xP == Q):
            return x

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

Python 3, 193 191 байт

Решение, основанное на ответе Pyth от Rhyzomatic и их логике Python. Особенно. Мне понравилось, как они нашли третий корень монического кубического полинома, x^3 + bx^2 + cx + dкогда у вас есть два корня, x_1и x_2, отметив это, b == x_1 + x_2 + x_3вычитая соответственно. Я планирую добавить объяснение, сыграть в гольф и, возможно, перенести его в Ruby, если Ruby окажется короче.

def e(p,A,B,P,Q):
 if P==0:return Q
 if Q==0:return P
 f,g=P;j,k=Q
 if f==j:
  if g==-k%p:return 0
  m=(3*f*f+A)*pow(2*j,p-2)
 else:m=(g-k)*pow(f-j,p-2)
 x=m*m-f-j;y=m*(f-x)-g;return(x%p,y%p)

Ungolfing:

def elliptic_curve_addition(p, A, B, P, Q):
    if P == 0:
        return Q
    if Q == 0:
        return P
    f,q = P
    j,k = Q
    if f==j:
        if g == (-k) % p:
            return 0
        m = (3 * f**2 + A) * pow(2*j, p-2)
    else:
        m = (g-k) * pow(f-j, p-2)
    x = m**2 - f - j
    y = m * (f-x) - g
    return (x%p, y%p)