Как складывать точки на эллиптической кривой
Перейти к содержимому

Как складывать точки на эллиптической кривой

  • автор:

Алгоритм скалярного умножения для эллиптической кривой

на хабре есть статья по данной тематике https://habr.com/ru/post/335906/ Для операции сложения там все описано подробно, а для умножения одна единственная формула. введите сюда описание изображения Допустим у нас есть входные данные. Px, Py. [4,6.78] Подскажите как найти для этих точек Qx, Qy введите сюда описание изображения

Отслеживать
задан 17 мая 2020 в 16:08
3,782 6 6 золотых знаков 36 36 серебряных знаков 80 80 бронзовых знаков

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Здесь на слайде 7 есть формула сложения точек и формула удвоения точки эллиптической кривой:
https://mipt.ru/education/chair/radio_engineering/infsec/2008/seminars/Seminar_6.pdf
Под удвоением точки понимаем операцию Q = 2 * P = P + P

  1. Путь простой, но медленный

Для Q = n * P производим n сложений точки P: Q = (((P + P) + P) + P) + .
Складывать точки мы умеем по формуле со слайда.
Это работает медленно.

Для нахождения точки Q = n * P применим алгоритм, работающий так же, как и бинарное возведение в степень.

Например, для Q = 6 * P:
Q = 6 * P = 2 * (P + 2 * P)
В получившемся выражении фигурируют только операции сложения и удвоения, а их мы умеем выполнять.

Q = P Пока n > 0: Если n - чётное, то Q = 2 * Q, n = n / 2 иначе Q = P + 2 * Q, n = (n - 1) / 2 

Вывод формул для сложения точек на эллиптической кривой

Зарегистрирован:
31 мар 2024, 21:05
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации

Уважаемые математики, добрый день!

Ни как не могу получить вывод формул для сложения точек на эллиптичесукой кривой.

Есть 2 точки: [x1,y1] и [x2,y2]
Надо получить 3ю точку [x,y]

В интернете удается найти только уже готовые формулы:
x = k^2 — x₁ — x₂
y = k⋅(-x + x₁) — y₁
где: k= (-y₁ + y₂)/(-x₁ + x₂)

Пытаюсь сам вывести, но упираюсь в кубическое уравнение. При этом понимаю, что два корня (две точки [x1,y1] и [x2,y2]) уже есть, но как продолжить вывод вышеуказанных формул, не пойму.

Общая формула прямой
y = k*x+b

Формула прямой, проходящей черех точки (x1,y1) и (x2,y2)
y = x⋅(-y₁ + y₂)/( -x₁ + x₂ ) + (-x₁⋅y₂ + x₂⋅y₁)/(-x₁ + x₂)

Коэффициент k
k = (-y₁ + y₂)/(-x₁ + x₂)

Коэффициент b
(-x₁⋅y₂ + x₂⋅y₁)/(-x₁ + x₂)

Формула эллиптической кривой
y^2 = x^3 + 7

Приравниваем формулу прямой к формуле эллиптической кривой
x^3 + 7 = (b + k⋅x)^2

Раскрываем скобки
x^3 + 7 = b^2 + 2⋅b⋅k⋅x + k^2 ⋅x^2

При этом, два корня уже известно [x1,y1] и [x2,y2], более того, эти корни уже присутствуют в коэффициентах k и b. Подскажите, пожалуйста, как действовать дальше, что бы получить формулы для 3го корня? Конечно, это все в натуральнх числах и по модулю.

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

Точка 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 , записанное в виде формальной суммы

  • Множество всех делителей на 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) . Билинейность спаривания Вейля выражается уравнениями

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

где S ∈ E — любая точка, удовлетворяющая условию S ∉ . (Это гарантирует, что все величины в правой части определены и отличны от нуля.) Можно проверить, что значение 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 следующим образом:

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

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

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

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

Требование

  • Python 3.5
  • numpy
git clone https://github.com/demining/CryptoDeepTools.git cd CryptoDeepTools/04AlgorithmsForSecp256k/ pip3 install numpy
├── Curves.py  

Эллиптическая кривая

y 2 + a1xy + a3y = x 3 + a2x 2 + a4x + a6.

Если ≠ 2 , 3 , то уравнение с помощью теории чисел. Например, они были использованы Эндрю Уайлзом (совместно Ричардом Тейлором ) в доказательстве Великой теоремы Ферма. Они примененяются в Криптография, основанная на эллиптических кривых ). В частности, на эллиптических кривых основан российский стандат факторизации (см.

  • 1 Эллиптические кривые над действительными числами
  • 2 Групповой закон
  • 3 Эллиптические кривые над полем комплексных чисел
  • 4 Эллиптические кривые над произвольным полем
  • 5 Связь с теорией чисел
  • 6 Алгоритмы, использующие эллиптические кривые
  • 7 Список литературы
  • 8 Внешние ссылки

Эллиптические кривые над действительными числами [ ]

Считаем, что характеристика поля — не 2 и 3. Тогда эллиптическая кривая — y 2 = x 3 + a x + b ,

где a и b — действительные числа. Этот вид уравнений называется y 2 = x 3 − x и y 2 = x 3 − x + 1 . Файл:ECexamples01.png

Δ = − 16 ( 4 a 3 + 27 b 2 )

не должен быть равен нулю.

Если кривая не имеет особых точек, то её график имеет две части, если дискриминант положителен, и одну — если отрицателен. Например, для графиков выше в первом случае дискриминант равен 64, а во втором он равен −368.

Групповой закон [ ]

Описанная группа может быть описана и алгебраически. Пусть дана кривая y² = x³ − pxq над полем K (чья характеристика не равна ни 2, ни 3), и точки P = (xP, yP) и Q = (xQ, yQ) на кривой, допустим, что xPxQ. Пусть s = (yPyQ)/(xPxQ); так как K — поле, то s чётко определено. Тогда мы можем определить R = P + Q = (xR, yR) следующим образом:

Если xP = xQ, то у нас два варианта: если yP = −yQ, то сумма определена как 0; значит, обратную точку к любой точке на кривой можно найти, отразив её по оси Ox. Если yP = yQ ≠ 0, то R = P + P = 2P = (xR, yR) определяется так:

Если yP = yQ = 0, то P + P = 0.

Эллиптические кривые над полем комплексных чисел [ ]

Формулировка эллиптических кривых как вложения комплексную проективную плоскость следует напрямую из любопытного свойства эллиптических функций Вейерштрасса . Эти функции и их первые производные связаны формулой

Здесь g 2 > и g 3 — константы; ℘ ( z ) — эллиптическая функция Вейерштрасса , а ℘ ′ ( z ) — её производная. Видно, что соотношение — в виде эллиптической кривой (над комплексными числами). Функции Вейерштрасса дважды периодичны; то есть, они являются периодом в отношении структуры Λ по сути, функции Вейерштрасса натурально определены на торе T = C / Λ /\Lambda> . Этот тор может быть вложен в комплексную проективную плоскость отображением

Это отображение — j-инвариантом .

Можно показать, что

g 2 = 4 1 / 3 3 ( λ 2 − λ + 1 ) > (\lambda^2-\lambda+1)>

g 3 = 1 27 ( λ + 1 ) ( 2 λ 2 − 5 λ + 2 ) (\lambda+1)(2\lambda^2-5\lambda+2)> ,

Здесь λ иногда называют лямбда-функцией модуляра .

Отметим, что теорема об униформации утверждает, что любая Эллиптические кривые над произвольным полем [ ]

Эллиптические кривые могут быть определены над любым полем K; формально, эллиптическая кривая определяется как невырожденная проективная алгебраическая кривая над K с Связь с теорией чисел [ ]

Этот факт можно истолковать и доказать с помощью некоторых общих тем; см. Локальная дзета-функция , Арифметика абелевых многообразий .

Алгоритмы, использующие эллиптические кривые [ ]

Список литературы [ ]

  • Н. Коблиц Курс теории чисел и криптографии = A Course in Number Theory and Cryptography. — Москва: Научное издательство "ТВП", 2001. — С. 254. ISBN 5-85484-014-6
  • Н. Коблиц Введение в эллиптические кривые и модулярные формы = Introduction to Elliptic Curves and Modular Forms. — Новокузнецк: ИО НФМИ, 2000. — С. 312. ISBN 5-80323-325-0
  • С. Ленг Эллиптические функции = Elliptic functions. — Новокузнецк: ИО НФМИ, 2000. — С. 312. ISBN 5-80323-326-9
  • Joseph H. Silverman The Arithmetic of Elliptic Curves. — New York: Springer, 1986. — С. 402. ISBN 0-387-96203-4

Внешние ссылки [ ]

  • The Mathematical Atlas: 14H52 Elliptic Curves
  • Эллиптическая криптография ca:Corba el·líptica pl:Krzywe eliptyczne

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *