Уравнение, которое тихо управляет миром. Два математика придумали его в 1976 — вы пользуетесь им каждый день

В октябре 1942 года британские эсминцы загнали немецкую подлодку у дельты Нила и начали забрасывать глубинными бомбами. Повреждённая лодка всплыла и стала быстро тонуть. В этот момент трое британцев перепрыгнули с корабля на вражеское судно и спустились внутрь, хотя экипаж уже покидал отсек за отсеком. Лейтенант Энтони Фассон, матрос Колин Грейзер и шестнадцатилетний помощник буфетчика Томми Браун искали не оружие и не пленных. А их целью были книги с кодами настройки немецкой шифровальной машины.

Речь о документах для системы «Энигма». В них содержались параметры, по которым немецкие военные настраивали шифрование сообщений. Чернила в этих книгах растворялись в воде, поэтому счёт шёл на минуты. Двое из трёх участников операции погибли, выбраться удалось только подростку. Уже через несколько недель британские криптоаналитики, включая команду Алан Тьюринг, использовали добытые материалы, чтобы читать немецкие сообщения. Историки оценивают вклад расшифровки как фактор, который сократил войну примерно на два года.

История с подлодкой показывает, насколько сложной задачей оставалась криптография. Чтобы передать секретное сообщение, стороны должны заранее договориться о способе шифрования. Без этого даже зашифрованный текст окажется бесполезным для получателя. Возникает замкнутый круг. Если отправитель передаст ключ тем же каналом, что и сообщение, перехватчик получит всё сразу. Эта проблема получила название задачи распределения ключей. По сути, для безопасной связи сначала нужна уже существующая безопасная связь.

Долгое время задачу решали не математикой, а организацией. Использовали личные встречи, курьеров, тайники и операции вроде захвата документов с тонущих кораблей. Ситуация изменилась в 1976 году, когда исследователи Стэнфордского университета Уитфилд Диффи и Мартин Хеллман предложили способ договориться о секрете по открытому каналу. Их метод позволил двум незнакомым участникам получить общий ключ, даже если весь обмен данными проходит под наблюдением.

Идея Диффи-Хеллмана легла в основу протокола обмена ключами, который сегодня используют повсеместно. Проверка банковского счёта, покупки в интернете, защищённые сайты с адресом https, сообщения в мессенджерах — все эти действия опираются на варианты того же принципа. Задача осталась прежней: обе стороны должны получить одно и то же большое случайное число, которое станет секретным ключом.

Чтобы понять логику метода, удобно представить бытовую аналогию. Две стороны заранее договариваются о какой-то базовой единице — например (если рассуждать образно), о рецепте химической смеси, известном всем, включая наблюдателя. Затем каждая сторона добавляет в эту основу свой секретный ингредиент и отправляет результат собеседнику. Получатель снова добавляет свой скрытый компонент к уже полученной формуле. В итоге обе стороны получают одинаковый состав, хотя ни разу не передавали секретные ингредиенты напрямую. Перехватчик видит только промежуточные смеси, но не может точно восстановить рецепт.

Конечно, компьютеры вместо жидкостей используют числа и операции над ними. Участники выбирают общее базовое число и большое простое число. Затем каждый берёт собственное секретное значение и выполняет возведение в степень с последующим вычислением остатка от деления. Результаты передаются по открытому каналу. После этого каждая сторона повторяет операцию, используя полученное число и свой секрет. В обоих случаях получается одинаковый итог — общее число, известное только участникам.

Ключевая деталь здесь — так называемая односторонняя функция. Вычислить результат просто, а восстановить исходные данные по этому результату крайне сложно. В обычной арифметике возведение в степень легко обратить через логарифм. Но в арифметике по модулю, где результат постоянно «заворачивается» по кругу, ситуация меняется. Значения начинают вести себя непредсказуемо. Например, при обычном возведении в степень результат растёт по понятному правилу. В арифметике по модулю те же операции дают последовательность, которая выглядит почти случайной.

Попытка восстановить секретное число по известным параметрам приводит к задаче дискретного логарифма. Для больших чисел, которые используют на практике, задача становится неподъёмной с точки зрения вычислений. Секретные значения могут содержать десятки цифр, а используемые простые числа — сотни. Даже самые быстрые известные алгоритмы потребуют астрономического времени на подбор решения.

При этом строгого доказательства сложности такой задачи до сих пор нет. Современная безопасность интернета держится на предположении, что быстрого способа решения попросту не существует. За десятилетия ни одна спецслужба и ни одна хакерская группа не продемонстрировали рабочий обход, хотя через такие схемы проходят банковские операции и государственные данные на триллионы долларов.

Слабое место у системы всё же есть. В 1994 году математик Питер Шор показал, что квантовый компьютер может решить задачу дискретного логарифма за часы. Алгоритм Шора использует свойства квантовой механики и в теории ломает существующие схемы шифрования. Но проблема упирается в железо: подходящего квантового компьютера пока не существует. Инженеры работают над такими системами, а криптографы параллельно разрабатывают постквантовые алгоритмы. До их массового внедрения обмен ключами по Диффи – Хеллману продолжает защищать большую часть цифровых коммуникаций.