Секрет на виду у всех
Алиса хочет передать Бобу секрет. Между ними только открытый канал: всё, что по нему идёт, видит Ева. Встретиться и заранее договориться о пароле нельзя.
Кажется, выхода нет: любой ключ, который Алиса отправит Бобу, получит и Ева. В 1976 году Уитфилд Диффи и Мартин Хеллман показали, что выход есть. Ему не нужна ни одна тайная встреча — только немного математики, которую проще всего понять на красках.
Смешать легко, разделить нельзя
Пусть секреты — это краски. Смешать две краски легко, а разделить смесь обратно практически невозможно. Оказывается, этого свойства хватает, чтобы договориться о секрете прилюдно.
Итоговая краска у Алисы и Боба одна и та же: в ней ровно по одной части общей, алисиной и бобовой краски. У Евы есть обе смеси, но если слить их вместе, общей краски окажется вдвое больше — и цвет выйдет другим.
Часы вместо красок
Компьютер не смешивает краски, он считает. Ему нужна операция, которую легко выполнить и трудно отменить. Возьмём циферблат с 23 делениями и будем много раз умножать на 5, каждый раз отсчитывая по кругу. Это возведение в степень по модулю.
Стрелка остановилась на 19. Сколько раз умножали на 5?
Вперёд — мгновенно: даже для чисел в сотни цифр компьютер возводит в степень за доли миллисекунды, повторно возводя в квадрат. Назад — это задача дискретного логарифма, и для больших простых чисел её не умеют решать быстро. Здесь 23 деления, и вы угадали перебором. При 600-значном модуле перебор не закончится до конца Вселенной.
Краски, ставшие числами
Общие числа p и g знают все — это «общая краска». Алиса берёт тайное число a и публикует A = ga mod p. Боб берёт b и публикует B = gb mod p. Дальше каждый возводит чужое число в свою тайную степень.
У обоих получилось одно и то же число gab mod p: неважно, в каком порядке «подмешивать» степени. Еве известны p, g, A и B, но чтобы узнать секрет, ей нужно вытащить a из A — решить ту самую обратную задачу с часов.
Замок, который защёлкнет каждый
Через год, в 1977-м, Рон Ривест, Ади Шамир и Леонард Адлеман придумали другой трюк. Боб раздаёт всем открытый замок — пару чисел (n, e). Защёлкнуть его может любой, а открыть — только тот, кто знает, из каких двух простых чисел собрано n.
Еве нужно разложить n на множители. Для n = 3233 это делается в уме: 61 × 53. Рекорд для «честного» ключа — RSA-250, число из 829 бит: его разложили в 2020 году, потратив около 2700 ядро-лет вычислений. До 2048 бит ещё очень далеко.
Сложение на кривой
Сегодня чаще всего используют эллиптические кривые y² = x³ + ax + b. На них есть своё сложение точек. Проведите прямую через P и Q: она пересечёт кривую в третьей точке. Отразите её относительно оси — это и есть P + Q.
Теперь та же кривая, но все вычисления — по модулю 97. Гладкая линия рассыпается на точки, прямая «заворачивается» на краях квадрата, и всё же сложение по-прежнему работает: прямая через P и Q проходит ровно через третью точку.
Узнать k по точкам P и kP — снова трудная обратная задача, только на кривой она ещё труднее. Поэтому ключ на кривой в 256 бит защищает не хуже ключа RSA примерно в 3000 бит.
Что держит этот замок
Все три идеи держатся на одном: есть действие, которое легко выполнить и трудно отменить. Смешать краски. Возвести в степень по модулю. Перемножить два простых числа. Сложить точку на кривой саму с собой k раз.
Квантовый компьютер с алгоритмом Шора умел бы быстро решать и разложение на множители, и дискретный логарифм — это сломало бы и RSA, и кривые. Поэтому в 2024 году американский институт стандартов NIST утвердил первые постквантовые стандарты. Например, ML-KEM основан на задачах о решётках, против которых алгоритм Шора бессилен.
А пока каждый раз, когда в адресной строке горит замок, браузер и сервер проделывают тот самый трюк с красками — на эллиптической кривой, за миллисекунды, на глазах у всех Ев интернета.