В этой статье мы рассмотрим несколько полезных и эффективных алгоритмов для эллиптической кривой E над полем GF(p) , заданной коротким уравнением Вейерштрасса

у^2 = х^3 + Ах + В 

  •  Алгоритм генерации точки на кривой E

  •  Алгоритм добавления точек

  •  Алгоритм удвоения точек

  •  Алгоритм нахождения целой кратной точки

  •  Алгоритм нахождения целой кратной точки (скалярное умножение)

  •  Алгоритм построения делителя D над кривой E с носителем supp(D) заданного размера d

  •  Алгоритм Миллера для вычисления значения функции Вейля n, P по делителю D такому, что supp(D) ∩ {P, O} = ∅

  •  Pairing Weil (Спаривание Вейля)

Модульные операции (целые числа) в конечном поле (или поле Галуа)

  1. x mod n означает «остаток n от деления x». Другими словами, если x = an + b и a, b ∈ integer, а также 0 ≤ b ≤ n − 1, то x mod n = b .

  2. Обратное : если ax = 1 mod n , то a является обратным значением x mod n . Есть два популярных метода решения :• Метод 1 : Попробуйте каждое значение для a < n, пока xa mod n = 1 .• Метод 2 : евклидов метод, который обычно используется для решения обратной задачи больших целых чисел, поэтому рекомендуется использовать метод 1 для решения обратной задачи малых целых чисел.

Операция с точками эллиптической кривой

Точка P(x 0 , y 0 ) на эллиптической кривой E означает: ее координаты 0 и 0 являются элементами поля, а координаты 0 и 0 удовлетворяют уравнению.

  1. Добавление точек на эллиптической кривой : пусть P, Q и R будут тремя точками на эллиптической кривой. Добавление очков P + Q = R.

  2. Удвоение точек на эллиптической кривой : пусть P, Q — две точки на эллиптической кривой. Удвоение очков P + P = 2P = Q

  3. Скалярное умножение : пусть P будет точкой на кривой E , определенной в уравнении

    • Скалярное умножение nP определяется как nP = P + P + P + … + P ( n раз), где n — целое число; nP также является точкой на той же кривой E .

    • Минимальное натуральное число a при aP = O называется порядком P .

    • Скалярное умножение широко требуется в криптосистемах с эллиптическими кривыми.

Делитель

Divisor (Делитель) D на кривой E — это удобный способ обозначить мультимножество точек на E , записанное в виде формальной суммы

  • Множество всех делителей на E обозначается Div F q (E) и образует группу, в которой сложение делителей естественно.

  • Делитель нуля: это делитель для всех n P = 0, делитель нуля 0 ∈ Div F q (E) .

  • Если поле q не является конкретным, его можно опустить и просто записать как Div(E) для обозначения группы делителей.

Делитель функции f на E

Делитель функции f на E используется для обозначения точек пересечения (и их кратностей) функций f и E .

Pairing Weil

Спаривание Вейля, которое обозначается m , принимает на вход пару точек P, Q ∈ E[m] и дает на выходе корень _m из единицы m( P , Q) . Билинейность спаривания Вейля выражается уравнениями

m (P 1 + P 2 , Q) = e m (P 1 , Q) * e m (P2, В),

m (P, Q 1 + Q 2 ) = e m (P, Q 1 ) * e m (P, Q 2 ).

Пара Вейля P и Q — это количество

где S ∈ E — любая точка, удовлетворяющая условию S ∉ {O, P, −Q, P − Q} . (Это гарантирует, что все величины в правой части определены и отличны от нуля.) Можно проверить, что значение m (P,Q) не зависит от выбора P , Q и S .

Эффективный алгоритм вычисления спаривания Вейля

Пусть E — эллиптическая кривая, и пусть P = (x P ,y P ) и Q = (x Q , y Q ) — ненулевые точки на E .

Пусть λ будет наклоном линии, соединяющей P и Q , или наклоном касательной к E в P, если P = Q. (Если линия вертикальна, мы полагаем λ = ∞.) Определим функцию g P, Q на E следующим образом:

затем

div(g P, Q ) = [P] + [Q] — [P + Q] — [ O ].

Алгоритм Миллера

Пусть m ≥ и запишите двоичное расширение m как

m = m 0 + m 1 * 2 + m 2 * 2 2 +···+ m n — 1 2 n — 1

при i ∈ {0, 1} и n — 1 ≠ 0 . Следующий алгоритм возвращает функцию P , делитель которой удовлетворяет условию

div( P ) = m [ P ] — [ mP ] — ( m — 1 ) [ O ],

где функции T, T и T, P, используемые алгоритмом, определены в (a).

В частности, если P ∈ E[m] , то div( P ) = m [ P ] − m [ O ].

Требование

  • Python 3.5

  • numpy

git clone https://github.com/demining/CryptoDeepTools.git

cd CryptoDeepTools/04AlgorithmsForSecp256k/

pip3 install numpy
├── Curves.py             <- Набор данных эллиптических кривых
├── Divisor.py            <- Создать делитель
├── EllipticCurve.py      <- Классы эллиптической кривой и точки на эллиптической кривой
├── EuclideanAlg.py       <- Расширенный алгоритм Евклида
├── Helper.py             <- Вспомогательные функции (обратные биты, мощность по модулю) 
├── Pairing.py            <- Спаривания Вейля, а так же Алгоритм Миллера
├── Tests.py              <- Модульные тесты для функций
├── Tonelli_ShanksAlg.py  <- Алгоритм Тонелли – Шенкса
├── main.py               <- main

Исходный код

Telegram: https://t.me/cryptodeeptech

Видеоматериал: https://youtu.be/gFbiBCNPsFk

Источник: https://cryptodeep.ru/algorithms-for-secp256k/


Комментарии (1)


  1. pohjalainen
    15.07.2022 08:20
    -1

    Гугл перевод такой гугл.

    Термин "дивизор" общепринят.

    Зачем вы "добавляете очки"?

    Ну и так далее.

    Плюс вы во введении обещаете рассмотреть алгоритмы. А в статье даете только определения, причем не на всё обещанное, да ссылку на гитхаб. Как-то нехорошо так поступать с читателями.