Начать проще всего с обычной функции
y = x². Представим, что нужно умножить 3 на 4 без калькулятора. На параболе выбираем точку с координатами (-3, 9), поскольку квадрат -3 равен 9, и вторую точку (4, 16), поскольку квадрат 4 равен 16. Теперь проводим через две точки прямую. Линия пересечёт ось y в точке (0, 12). Число 12 и будет результатом умножения 3 × 4. Scientific American предлагает даже собрать физический вариант такого «параболического калькулятора». Параболу можно нарисовать на картоне, установить колышки в точках с целыми координатами и натянуть между нужными колышками нить. Место, где натянутая нить проходит через вертикальную ось, показывает произведение. Для небольших целых чисел конструкция работает почти как механическое вычислительное устройство.
Никакого совпадения здесь нет. Свойство напрямую следует из уравнения параболы.
Пусть требуется перемножить произвольные числа
a и b. На графике y = x² выбираются точки (-a, a²) и (b, b²). Через них проводится прямая. Наклон такой прямой можно вычислить по двум точкам. Разница координат по вертикали равна
b² - a², а по горизонтали b + a. Поэтому коэффициент наклона равен (b² - a²)/(b + a). Выражение
b² - a² раскладывается как (b - a)(b + a). После сокращения остаётся просто b - a. Теперь возьмём точку
(-a, a²) и запишем уравнение проходящей через неё прямой. При x = 0, то есть непосредственно на оси y, высота линии получится равной a² + a(b - a). После раскрытия скобок остаётся ab. Другими словами, вертикальная координата пересечения всегда совпадает с произведением исходных чисел.
Тот же принцип работает не только с положительными целыми числами. Можно перемножать отрицательные и дробные значения, хотя графический способ быстро теряет практический смысл. Чем менее удобны координаты, тем сложнее точно определить результат по рисунку. Параболический калькулятор интересен не скоростью вычислений, а тем, что обычное арифметическое действие неожиданно превращается в геометрическую операцию.
Есть даже небольшой особый случай. Если
b = -a, две выбранные точки совпадут, поэтому провести через них обычную секущую уже нельзя. Вместо секущей можно взять касательную к параболе в данной точке. Пересечение касательной с осью y снова даст нужное произведение -a². Подобная замена секущей касательной ещё раз появится при переходе к эллиптическим кривым. Именно здесь школьная головоломка становится интересной для криптографии. Современные криптографы постоянно ищут математические операции с сильной асимметрией вычислительной сложности. В одну сторону вычисление должно выполняться быстро даже на обычном компьютере. Обратная задача должна становиться настолько трудной, чтобы перебор потребовал нереалистичных ресурсов.
Самый известный пример даёт RSA. Компьютеру сравнительно легко перемножить два очень больших простых числа. Если же предоставить только произведение, восстановить исходные простые множители для правильно выбранных размеров становится значительно сложнее. Безопасность RSA связана именно с вычислительной сложностью факторизации больших целых чисел.
Криптография на эллиптических кривых, или ECC, использует другую трудную математическую задачу. Причём связь с параболическим калькулятором здесь прежде всего концептуальная. Современные системы ECC не шифруют информацию с помощью графика
y = x². Парабола показывает более общую идею, когда геометрические действия над точками кривой задают арифметические операции. Эллиптическая кривая в одной из классических форм описывается уравнением вроде
y² = x³ + ax + b. Название немного сбивает с толку. Эллиптическая кривая вовсе не является эллипсом. Термин появился из другой области математики, связанной с эллиптическими интегралами. Коэффициенты
a и b выбирают так, чтобы кривая не имела разрывов, острых углов и самопересечений. Для стандартной формы требуется выполнение условия 4a³ + 27b² ≠ 0. При подходящих коэффициентах получается гладкая кривая, на точках которой можно определить необычное сложение. Представим две точки
P и Q на эллиптической кривой. Через P и Q проводится прямая. Кубическая природа уравнения приводит к интересному свойству. Прямая обычно пересекает эллиптическую кривую ещё в одной точке. Назовём третью точку R. После этого
R отражают относительно горизонтальной оси. Получившаяся точка объявляется суммой P + Q. На первый взгляд подобное «сложение» выглядит произвольным математическим трюком. Однако операция обладает привычными для арифметики свойствами. Точки эллиптической кривой вместе со специальной точкой, которую называют точкой на бесконечности, образуют математическую группу.
Точка на бесконечности играет роль нуля. Для любой точки
P выполняется аналог привычного равенства P + 0 = P. У каждой точки существует обратная. Если P имеет координаты (x, y), то в обычном геометрическом представлении обратной будет точка (x, -y). Их сумма даёт точку на бесконечности. Можно складывать и точку саму с собой. Через две одинаковые точки прямую провести нельзя, поэтому вместо секущей используется касательная к кривой в точке
P. Касательная пересекает кривую ещё раз, затем третья точка отражается относительно горизонтальной оси. Получается 2P. Дальше операцию можно повторять.
P + P + P превращается в 3P, дальнейшее сложение даёт 4P, 5P и так далее. Многократное сложение одной точки называют скалярным умножением. Запись kP означает, что точку P сложили с собой k раз. Именно скалярное умножение становится одной из центральных операций ECC.
Наивный способ вычислить
1 000 000P потребовал бы почти миллион последовательных сложений. Компьютеру так поступать не приходится. Алгоритмы используют приёмы, напоминающие быстрое возведение числа в степень. Точки удваивают и складывают в соответствии с двоичным представлением множителя. Количество операций растёт примерно пропорционально числу битов в k, а не самому значению k. Поэтому вычислить
Q = kP, зная P и огромное число k, сравнительно легко. Но теперь попробуем выполнить обратную операцию. Пусть известны
P и Q, причём известно, что Q = kP. Требуется найти неизвестное k. Задача называется проблемой дискретного логарифма на эллиптической кривой, или ECDLP. Для правильно выбранных кривых и достаточно больших параметров эффективного классического алгоритма решения такой задачи не известно.
Асимметрия получается почти идеальной для криптографии. Владелец секретного ключа знает число
k и быстро вычисляет связанную с ним публичную точку Q. Посторонний видит P и Q, но восстановить секретный множитель k практически не может. Здесь скрывается ещё одно существенное отличие от картинки в учебнике. Настоящая криптография обычно работает не с непрерывной эллиптической кривой над обычными вещественными числами. Вычисления проводят над конечным полем.
Проще говоря, координаты ограничиваются конечным набором чисел, а арифметика выполняется по модулю большого простого числа. После достижения определённого значения счёт словно начинается заново.
Если работать, например, по модулю 17, число 18 превращается в 1, 19 в 2, а 34 в 0. Криптографические системы используют не 17, конечно, а огромные простые числа, содержащие сотни битов.
Из-за модульной арифметики привычная гладкая линия на графике исчезает. Эллиптическая «кривая» над конечным полем визуально выглядит как набор отдельных точек. Соединять точки настоящей линейкой уже бессмысленно. Однако алгебраические формулы, соответствующие геометрическим операциям, продолжают работать.
Именно поэтому картинка с прямой, пересекающей кривую, служит способом понять принцип, а компьютер выполняет операции исключительно с числами.
Для распространённого уровня классической защиты примерно в 128 бит достаточно эллиптической кривой с параметрами порядка 256 бит. Для сравнения, NIST сопоставляет такой уровень стойкости примерно с RSA-модулем длиной 3072 бит.
Разница в размерах имеет практические последствия. Более компактные параметры и ключи уменьшают объём передаваемых данных и часто позволяют выполнять операции эффективнее. Поэтому ECC особенно привлекательна для сетевых протоколов, смартфонов, встраиваемой электроники и других систем, где приходится учитывать вычислительную мощность, память, энергопотребление и сетевой трафик.
Идею использовать эллиптические кривые в криптографии независимо развивали Виктор Миллер и Нил Коблиц в середине 1980-х годов. За последующие десятилетия ECC прошла путь от сравнительно экзотической области теории чисел до повседневной инфраструктуры цифровой безопасности.
Сегодня семейство технологий на эллиптических кривых включает несколько разных задач. ECDH позволяет двум сторонам получить общий секрет через открытый канал. ECDSA применяется для цифровых подписей. EdDSA предлагает другой способ построения подписей на специальных эллиптических кривых. X25519 используется для обмена ключами и основан на Curve25519.
В RFC 7748 для X25519 используется поле по модулю
2²⁵⁵ - 19. Входные и выходные значения X25519 кодируются 32 байтами. Стандарт также описывает Curve448 и функцию X448 для более высокого уровня безопасности. Эллиптические кривые встречаются в защищённых интернет-соединениях, протоколах обмена ключами, цифровых сертификатах, системах электронной подписи, мессенджерах, SSH и криптовалютах. Конкретные системы используют разные кривые и схемы. Один только термин ECC поэтому обозначает не отдельный алгоритм, а целое семейство криптографических методов, построенных вокруг арифметики точек на эллиптических кривых.
Компактные ключи не означают, что ECC автоматически безопаснее любого RSA. Стойкость зависит от конкретных параметров, алгоритма и реализации. Неправильно выбранная кривая способна иметь математические свойства, которые делают задачу дискретного логарифма значительно проще. Криптографические стандарты поэтому задают конкретные проверенные кривые и требования к работе с ними.
Реализация тоже может разрушить хорошую математику. Даже если саму проблему дискретного логарифма решить невозможно, атакующий иногда получает секрет через побочные каналы. Время выполнения операций, энергопотребление устройства, поведение процессорного кэша и другие физические характеристики способны раскрывать информацию о секретном ключе.
Разработчики современных кривых и алгоритмов специально учитывают подобные угрозы. Например, RFC 7748 описывает Curve25519 и Curve448 как кривые, подходящие для реализаций с постоянным временем выполнения и устойчивостью к ряду атак по побочным каналам.
Не менее опасны ошибки с генерацией случайных чисел. Некоторые схемы цифровой подписи требуют уникального секретного значения для каждой подписи. Повтор или предсказуемость такого параметра иногда позволяет математически восстановить закрытый ключ, хотя сама эллиптическая кривая остаётся совершенно исправной.
Поэтому реальная криптография состоит не только из выбора сложной математической задачи. Безопасность требует корректных параметров, генератора случайных чисел, реализации алгоритмов, управления ключами и защиты от побочных каналов.
Сама проблема дискретного логарифма тоже не является доказанно неразрешимой. Криптографы не могут математически гарантировать, что завтра никто не найдёт радикально более быстрый классический алгоритм. Современная безопасность опирается на десятилетия исследований и отсутствие известных эффективных методов атаки на правильно выбранные кривые.
Для группы порядка приблизительно
2²⁵⁶ лучшие универсальные классические методы поиска дискретного логарифма требуют порядка 2¹²⁸ операций. Именно отсюда появляется выражение «128 бит стойкости». Речь идёт не о том, что ключ обязательно состоит из 128 бит, а об оценке вычислительной работы, необходимой для наиболее эффективной известной атаки. Подобная разница между размером параметров особенно хорошо показывает преимущество ECC перед RSA. Для примерно 128-битной классической стойкости RSA требует модуль около 3072 бит, тогда как эллиптическая криптография достигает сопоставимого уровня с группой порядка примерно 256 бит. С ростом требуемой стойкости разрыв становится ещё заметнее.
Однако у RSA и ECC есть общий противник, который не учитывается при таких классических оценках. Достаточно мощный отказоустойчивый квантовый компьютер сможет использовать алгоритм Шора.
Алгоритм Шора способен эффективно решать обе математические задачи, на которых построены популярные системы с открытым ключом. Для RSA угрозой становится быстрая факторизация больших чисел. Для ECC квантовый компьютер сможет решать дискретный логарифм на эллиптических кривых.
Следовательно, увеличение размера обычного ECC-ключа не превращает схему в постквантовую. Квантовая атака меняет сам характер задачи.
Практических квантовых компьютеров, способных взломать современные крупные ключи RSA и ECC, пока нет. Для подобной атаки потребуется гораздо более масштабная и надёжная машина с коррекцией ошибок, чем существующие квантовые системы. Но переход криптографической инфраструктуры занимает много лет, поэтому подготовка уже идёт.
В 2024 году NIST утвердил первые три основных федеральных стандарта постквантовой криптографии. FIPS 203 описывает ML-KEM для установления общего секрета, FIPS 204 задаёт ML-DSA для цифровых подписей, а FIPS 205 описывает подписи SLH-DSA. Алгоритмы построены на математических задачах, для которых пока не известно эффективных атак ни на классических, ни на квантовых компьютерах.
Поэтому история с параболой одновременно показывает эволюцию криптографии за несколько десятилетий. Сначала перед нами простая школьная кривая
y = x². Две точки и прямая неожиданно превращают геометрию в умножение. Затем тот же общий подход переносится на гораздо более сложные объекты, где точки можно складывать и умножать на числа. Наконец, трудность обращения такой операции позволяет спрятать секретный ключ. Парабола сама по себе не защищает браузеры, банковские приложения или мессенджеры. Главная ценность примера в другом. Геометрическая фигура показывает, как математики научились превращать форму кривой в систему арифметики, а свойства новой арифметики использовать для защиты информации.
Особенно хорошо параболический калькулятор разрушает привычное школьное представление о математике как о наборе отдельных тем. Квадратные функции, координатная геометрия, теория чисел, конечные поля и криптография выглядят совершенно разными дисциплинами, пока между ними не появляется прямая линия.
В случае
y = x² линия всего лишь сообщает результат умножения. В случае эллиптической кривой похожая идея помогает построить операцию, которую компьютер легко выполняет вперёд и практически не способен обратить. На такой разнице сложности десятилетиями держалась значительная часть современной криптографии.