В основе современных криптографических систем лежит не только арифметика, но и элегантная геометрия эллиптических кривых.
Эллиптическая кривая задаётся уравнением вида:
y^2 = x^3 + ax + b.
при этом важно, чтобы дискриминант не обращался в ноль — это гарантирует гладкость кривой.
сама кривая есть на первой картинке
Здесь операция сложения точек на кривой определяется весьма своеобразно: для сложения двух разных точек P и Q проводится прямая через них, а затем найденная третья точка отражается относительно оси x.
На картинке показано как получается результат P+Q=R’
При удвоении точки применяется касательная, которая пересекается с кривой, и аналогично выполняется отражение.
На картинке 2*P=S’
Для криптографических применений, таких как формирование ключей, вычисления ведутся не над вещественными числами, а в конечных полях (например, GF(p)).
Если кратко, то конечное поле, это штука, где все операции выполняются по модулю p. То есть уравнение будет вида:
y^2 mod p = (x^3 + ax + b) mod p.
Точек в кадрате p*p будет p-1 или около того (я забыл если честно).
На второй картинке показан пример такого поля. И тут тоже есть геометрическая интерпретация для сложения.
Нахера нам эти поля и кривые?
В криптографии важно, чтобы все вычисления были дискретными (то есть, с целыми числами) и имели ограниченное число вариантов. Это позволяет избежать проблем с точностью и сделать вычисления эффективными.
Конечные поля позволяют нам выполнять операции по модулю, которые позволяют нам производить вычисления достаточно легко в одну сторону и почти не обратимо в обратную.
Вот пример:
3^3 mod 17 = 27 mod 17 = 10
При этом, если мы не знаем степень, то получить x можно только перебрав кучу не верных кандидатов:
3^x mod 17 = 12 — найдите x…
Если что, ответ 29 🙂
Аналогично, в эллиптических кривых используется операция, которая записывается как
Q = d * G,
где G — базовая точка, а d — приватный ключ (по сути тот самый x, который нереально найти при наших вычислительных ресурсах).
Эта операция представляет собой повторное сложение точки G с собой d раз и является аддитивным аналогом возведения в степень.
То есть у нас есть операция, которую легко выполнить в одну сторону, но почти не реально в другую сторону (при больших d и p (прям оооочень больших))
Эти операции лежат в основе ECDSA — алгоритма цифровой подписи на эллиптических кривых. При генерации ключей выбирается базовая точка G с большим простым порядком p. Приватный ключ d — случайное число, а публичный вычисляется как Q = d * G
пример на картинке 3.
Задача восстановления d по Q сводится к поиску дискретного логарифма — математической проблеме, которую решить практически невозможно без перебора (то что описано выше).
От криптографических примитивов мы переходим к тому, как всё это используется для создания целостных систем хранения данных.
А вот здесь
тыц можно поиграть с элиптическими кривыми и посмотреть как появляются точки P, Q и R.
[4/8]