Эта серия коротких статей основана на моей оригинальной гигантской статье: Эллиптические кривые и ECDSA: все, что нужно знать, чтобы подписать транзакцию в биткойнах с нуля
Введение в серию
Эллиптические кривые очень просты. Алгоритм цифровой подписи эллиптических кривых (ECDSA) является ключевым элементом большинства блокчейнов, таких как Биткойн, Эфириум и т. д. По сути, это пара простых формул, работающих поверх свойств эллиптических кривых.
Тем не менее, нелегко найти хорошее объяснение в Интернете и собрать все части воедино. Но вот! В этой короткой серии статей мы это сделаем.
Для этой серии требуется знать не больше, чем математику средней школы.
Только последняя последняя часть серии предназначена для программистов.
Там мы реализуем ECDSA с нулевыми зависимостями, и это займет всего 100 строк кода.
В частях 1, 2 и 3 мы рассмотрим все концепции и формулы, необходимые для полного понимания и реализации алгоритма — одну за другой. . В конце этой серии мы получим полностью функционирующую демонстрацию, реализованную с нуля,с использованиемтолькоконцепций и формулобнаруженный здесь. Мы сможем извлечь открытый ключ из закрытого ключа, подписать сообщение и проверьте правильность подписи.
Сериал состоит из четырех частей; каждая часть использует концепции, обнаруженные в предыдущих частях:
- Магия эллиптических кривых [вы здесь]
- Магия эллиптических кривых в сочетании с конечными полями
- Использование магии эллиптических кривых для подписи и проверки сообщений
- Реализация ECDSA на Python с использованием нулевых зависимостей
Начнем здесь!
Мы все, наверное, знакомы со всеми этими графиками на координатных сетках, где переменная y каким-то образом зависит от x. Например, y = x, y = x² и т. д. Скорее всего, у всех нас есть некоторый опыт в этом. Давайте посмотрим на них:
Уравнение эллиптической кривой мало чем отличается! Оно имеет форму
y² = x³ + a*x + b. Что такое a и b? Просто какие-то произвольные константы. Давайте посмотрим, как это выглядит при a = 0, b = 7, как на кривой биткойна:
У него есть следующие три сверхважных свойства, на которых все работает:
Вот здесь может быть сложно понять почему. Вам даже может показаться, что это что-то бессвязное и не относящееся к делу. Но, пожалуйста, поверь мне. Эти свойства приведут нас к очень удивительному результату! А теперь давайте представим, что мы просто развлекаемся без всякой цели.
- Эллиптическая кривая симметрична вдоль оси 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. Если у нас есть точка 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
Михаил Караваев