Эта серия коротких статей основана на моей оригинальной гигантской статье: Эллиптические кривые и ECDSA: все, что нужно знать, чтобы подписать транзакцию в биткойнах с нуля

Введение в серию

Эллиптические кривые очень просты. Алгоритм цифровой подписи эллиптических кривых (ECDSA) является ключевым элементом большинства блокчейнов, таких как Биткойн, Эфириум и т. д. По сути, это пара простых формул, работающих поверх свойств эллиптических кривых.

Тем не менее, нелегко найти хорошее объяснение в Интернете и собрать все части воедино. Но вот! В этой короткой серии статей мы это сделаем.

Для этой серии требуется знать не больше, чем математику средней школы.

Только последняя последняя часть серии предназначена для программистов.
Там мы реализуем ECDSA с нулевыми зависимостями, и это займет всего 100 строк кода.

В частях 1, 2 и 3 мы рассмотрим все концепции и формулы, необходимые для полного понимания и реализации алгоритма — одну за другой. . В конце этой серии мы получим полностью функционирующую демонстрацию, реализованную с нуля,с использованиемтолькоконцепций и формулобнаруженный здесь. Мы сможем извлечь открытый ключ из закрытого ключа, подписать сообщение и проверьте правильность подписи.

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

  1. Магия эллиптических кривых [вы здесь]
  2. Магия эллиптических кривых в сочетании с конечными полями
  3. Использование магии эллиптических кривых для подписи и проверки сообщений
  4. Реализация ECDSA на Python с использованием нулевых зависимостей

Начнем здесь!

Мы все, наверное, знакомы со всеми этими графиками на координатных сетках, где переменная y каким-то образом зависит от x. Например, y = x, y = x² и т. д. Скорее всего, у всех нас есть некоторый опыт в этом. Давайте посмотрим на них:

Уравнение эллиптической кривой мало чем отличается! Оно имеет форму
y² = x³ + a*x + b. Что такое a и b? Просто какие-то произвольные константы. Давайте посмотрим, как это выглядит при a = 0, b = 7, как на кривой биткойна:

У него есть следующие три сверхважных свойства, на которых все работает:

Вот здесь может быть сложно понять почему. Вам даже может показаться, что это что-то бессвязное и не относящееся к делу. Но, пожалуйста, поверь мне. Эти свойства приведут нас к очень удивительному результату! А теперь давайте представим, что мы просто развлекаемся без всякой цели.

  1. Эллиптическая кривая симметрична вдоль оси x. Это означает, что для любой точки на кривой A мы можем получить ее зеркальную точку, называемую -A, просто отразив ее координату y:

2. Если провести прямую через любую из двух точек, не лежащих на одной вертикальной линии, то она пересечет кривую ровно еще в одной точке!
Проведем прямую через точки A и B и назовем третью точку — C. Затем отразим его, чтобы получить точку C:

Другой пример:

Эта точка C называется суммой точек A и B. Таким образом, A + B = C.

3. Если мы проведем касательную линию через любую точку A, лежащую на кривой, она пересечет кривую ровно в одной точке. . Мы назовем эту точку -2A. Мы уже знаем, как получить 2A:

Самый простой способ представить себе касательную — представить, что она дважды пересекает точку A. Как будто он пересекает кривую не в двух точках, а в трех: А, А, -2А.

Вот и все! Мы определили три операции на эллиптической кривой: умножение точки на -1, сложение двух точек вместе и удвоение точки.

И здесь начинает работать алгебра эллиптических кривых.

Теперь у нас есть следующая картинка с точками A, 2A и -2A:

Проведем линию через A и 2A. Третья точка, которую мы получим, будет -3A. Затем просто отразите его, чтобы получить 3A:

Вы, наверное, еще не понимаете, зачем мы все это делаем. Просто посмотрите еще на один шаг. Что, если мы попытаемся провести линию между 3A и -2A?

Вы видите волшебство? Проводя линию между 3A и -2A, мы получаем -A. точка, которая является отражением нашей исходной точки A по оси X!

То, что мы только что определили в трех пунктах выше, — это алгебра эллиптических кривых.

Просто попытайтесь понять силу этих трех операций: по сути, теперь мы можем выполнять операции над точками, лежащими на кривой, как если бы они были не точками, а просто числами!

Что мы можем делать с точками на кривой:

  • Добавление двух точек (A + B)
  • Вычитание двух точек A — B = (A + (-B))
  • Удвоение точки (умножение на два) 2*A
  • Умножение на любое целое число (сочетая предыдущие операции вместе, мы можем получить любое целое * Point)

Что мы не можем сделать:

  • Умножение двух точек
  • Деление точки над другой точкой
  • Деление точки на скалярное значение

Например, чтобы получить 10A:
2A = A + A
4A = 2A + 2A
8A = 4A + 4A
10A = 8А + 2А

Также приятно отметить, что мы можем выполнять вычисления с логарифмическим числом операций. Таким образом, приблизительное количество операций, необходимых для вычисления n*Point, равно O(log2(n))!

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

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

  1. Умножение точки на -1. Если у нас есть точка A(x, y), мы можем легко получить
    -A, умножив ее координату y на -1. -A(x, -y). Пример:
    -1 * A(2, 2) → -A(2, -2)
    -1 * A(1, -1) → -A(1, 1)< br /> -1 * A(5, 8) → -A(5, -8)
    -1 * A(5, -8) → -A(5, 8)

2. Складываем две точки вместе. Мы можем сложить две точки вместе, но с одним условием: они не должны лежать на одной вертикали (их координаты x не должны совпадать). Это формула сложения A и B (A + B = C):

3. Добавление точки к себе (умножение точки на 2). Это очень похоже на операцию сложения двух точек, но немного отличается:

Вот и все! Время практиковаться!

Попробуем сложить здесь A и B (используем приближение до 3 точек после запятой):

Согласно формуле, определенной выше для сложения двух точек,

Теперь найдем нашу точку C графически:

Это работает! Да, с небольшой проблемой близости из-за округления. Но это работает!
Для лучшего понимания рекомендую попробовать выполнить все эти операции самостоятельно.

Это все, что нам нужно было знать об эллиптических кривых и операциях над ними, которые мы должны уметь выполнять!

Все хорошо, но нам понадобится еще пара свойств для построения криптографической системы.

Следующая часть: Магия эллиптических кривых в сочетании с конечными полями

Пишите мне:
[email protected]
https://t.me/exemak
Михаил Караваев