Полезные и эффективные алгоритмы для эллиптической кривой secp256k1

Crypto Deep Tech

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

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

  •  Алгоритм генерации точки на кривой E
  •  Алгоритм добавления точек
  •  Алгоритм удвоения точек
  •  Алгоритм нахождения целой кратной точки
  •  Алгоритм нахождения целой кратной точки (скалярное умножение)
  •  Алгоритм построения делителя D над кривой E с носителем supp(D) заданного размера d
  •  Алгоритм Миллера для вычисления значения функции Вейля f 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 означает: ее координаты x 0 и y 0 являются элементами поля, а координаты x 0 и y 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 , записанное в виде формальной суммы

Полезные и эффективные алгоритмы для эллиптической кривой secp256k1
  • Множество всех делителей на E обозначается Div F q (E) и образует группу, в которой сложение делителей естественно.
  • Делитель нуля: это делитель для всех n P = 0, делитель нуля 0 ∈ Div F q (E) .
  • Если поле F q не является конкретным, его можно опустить и просто записать как Div(E) для обозначения группы делителей.

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

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

Pairing Weil

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

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

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

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

Полезные и эффективные алгоритмы для эллиптической кривой secp256k1

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

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

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

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

Полезные и эффективные алгоритмы для эллиптической кривой secp256k1

затем

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

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

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

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

Полезные и эффективные алгоритмы для эллиптической кривой secp256k1

В частности, если P ∈ E[m] , то div( f 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

Crypto Deep Tech