В этой статье мы рассмотрим несколько полезных и эффективных алгоритмов для эллиптической кривой E над полем GF(p) , заданной коротким уравнением Вейерштрасса
у^2 = х^3 + Ах + В
- Алгоритм генерации точки на кривой E
- Алгоритм добавления точек
- Алгоритм удвоения точек
- Алгоритм нахождения целой кратной точки
- Алгоритм нахождения целой кратной точки (скалярное умножение)
- Алгоритм построения делителя D над кривой E с носителем supp(D) заданного размера d
- Алгоритм Миллера для вычисления значения функции Вейля f n, P по делителю D такому, что supp(D) ∩ {P, O} = ∅
- Pairing Weil (Спаривание Вейля)
Модульные операции (целые числа) в конечном поле (или поле Галуа)
- x mod n означает «остаток n от деления x». Другими словами, если x = an + b и a, b ∈ integer, а также 0 ≤ b ≤ n − 1, то x mod n = b .
- Обратное : если 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 удовлетворяют уравнению.
- Добавление точек на эллиптической кривой : пусть P, Q и R будут тремя точками на эллиптической кривой. Добавление очков P + Q = R.
- Удвоение точек на эллиптической кривой : пусть P, Q — две точки на эллиптической кривой. Удвоение очков P + P = 2P = Q
- Скалярное умножение : пусть 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) .
- Если поле 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 — это количество
где 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 следующим образом:
затем
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).
В частности, если 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
Источник: https://cryptodeep.ru/algorithms-for-secp256k/