Криптография на эллиптических кривых (ECC): Математика нового века

Эллиптическая кривая в криптографии — это математическое уравнение вида y² = x³ + ax + b. График этого уравнения выглядит как плавная, симметричная относительно оси X кривая с петлей или изгибами. Однако для программирования мы переносим эту кривую из поля бесконечных вещественных чисел в конечное поле Галуа (по модулю большого простого числа P). Визуально график превращается в облако хаотично разбросанных точек, но математические свойства кривой полностью сохраняются.

Главный прорыв ECC заключается в создании алгебраической группы точек кривой. Математики ввели уникальную операцию "сложения" точек. Если взять точки P и Q на кривой и провести через них прямую, она пересечет кривую в третьей точке R. Если отразить эту точку R симметрично оси X, мы получим точку S, которая математически считается "суммой" P + Q. Если точка прибавляется сама к себе (P + P), проводится касательная к кривой.

Из этого "сложения" естественным образом вытекает скалярное "умножение" точки: P + P + P... n раз = n*P. В дискретной математике эта операция умножения (многократного геометрического сложения) выполняется очень быстро с помощью алгоритма "двойного сложения".

А теперь самое главное: Проблема дискретного логарифмирования на эллиптических кривых (ECDLP). Суть ее в следующем: если вам даны исходная точка P (базовая точка) и конечная точка T (результат), то восстановить скалярный множитель n (сколько раз точку P прибавили саму к себе) вычислительно невозможно, если n — достаточно большое случайное число.

Зависимость сложности взлома ECDLP от размера ключа кардинально отличается от факторизации RSA. Математически доказано, что ключ ECC длиной всего 256 бит обеспечивает точно такой же уровень криптографической стойкости, как гигантский ключ RSA длиной 3072 бита! Это колоссальная экономия процессорного времени, заряда батареи и пропускной способности сети.

Сегодня протокол ECC полностью вытесняет конкурентов. Знаменитая кривая secp256k1 лежит в основе цифровых подписей Bitcoin и всех блокчейн-технологий. Кривая Curve25519 используется в протоколах Signal и WhatsApp для обеспечения сквозного шифрования (End-to-End Encryption). А современные HTTPS-сертификаты в вашем браузере используют алгоритм ECDSA.