Обмен ключами Диффи — Хеллмана простыми словами

Тысячи лет отправить секретное сообщение означало сначала передать секретный ключ лично или через курьера. В 1976 году два исследователя из Стэнфорда показали, что две стороны могут создать общий ключ буквально из воздуха, обмениваясь сообщениями на виду у кого угодно. Эта идея открыла эпоху криптографии с открытым ключом и до сих пор работает каждый раз, когда браузер показывает замочек.

Алиса и Боб по обе стороны открытого канала, каждый смешивает общую жёлтую краску с секретным цветом, и у обоих получается одна и та же смесь, пока Ева наблюдает
Алиса и Боб по обе стороны открытого канала, каждый смешивает общую жёлтую краску с секретным цветом, и у обоих получается одна и та же смесь, пока Ева наблюдает

Проблема распределения ключей

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

Арифметика на циферблате

Обмен использует модульную арифметику: вычисления на циферблате с p часами, где p — большое простое число. Степени на таком циферблате ведут себя удивительно. Если g — первообразный корень, то числа g, g², g³, … mod p скачут туда-сюда и обходят все часы от 1 до p − 1, прежде чем начать повторяться, в порядке, который выглядит случайным. Вычислить gᵃ mod p быстро: нужно примерно столько умножений, сколько у a двоичных цифр. Обратить это — нет.

Обмен шаг за шагом

Алиса и Боб открыто договариваются о p и g. Алиса выбирает секрет a и отправляет A = gᵃ mod p; Боб выбирает секрет b и отправляет B = gᵇ mod p. Алиса вычисляет Bᵃ = (gᵇ)ᵃ, а Боб — Aᵇ = (gᵃ)ᵇ, оба по модулю p. Поскольку порядок показателей не важен, оба получают g^(ab) mod p. В классическом маленьком примере с p = 23, g = 5, a = 6 и b = 15 Алиса отправляет 8, Боб отправляет 19, и оба приходят к общему секрету 2.

Задача дискретного логарифмирования

Ева видит p, g, A и B. Если бы она могла найти a по A = gᵃ mod p, она вычислила бы секрет так же, как Алиса. Это и есть задача дискретного логарифмирования. Лучшие известные классические алгоритмы, например решето числового поля, гораздо быстрее перебора всех показателей, но всё равно требуют времени, растущего быстрее любой степени числа цифр. С простыми числами длиной 2048 бит задача недоступна ни одному существующему компьютеру. Возможно ли что-то быстрее, неизвестно, и стойкость обмена держится на этом убеждении.

Человек посередине

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

Кто его изобрёл?

Диффи и Хеллман опубликовали метод в 1976 году, опираясь на идеи Ральфа Меркла, которого Хеллман позже попросил тоже указывать в числе авторов. В 1997 году британская спецслужба GCHQ раскрыла, что её математики пришли к этому раньше: у Джеймса Эллиса идея криптографии с открытым ключом появилась в 1970 году, Клиффорд Кокс нашёл систему, похожую на RSA, в 1973 году, а Малкольм Уильямсон открыл тот же обмен ключами в 1974 году; всё это держалось в секрете больше двадцати лет.

Мартин Хеллман (слева) и Уитфилд Диффи (справа), 1977
Мартин Хеллман (слева) и Уитфилд Диффи (справа), 1977
Ральф Меркл на Singularity Summit в 2007 году. Цепочечная конструкция, которую использует SHA-256, названа в честь него и Ивана Дамгора.
Ральф Меркл на Singularity Summit в 2007 году. Цепочечная конструкция, которую использует SHA-256, названа в честь него и Ивана Дамгора.

Диффи — Хеллман сегодня

Современные соединения в основном используют протокол Диффи — Хеллмана на эллиптических кривых, который даёт ту же стойкость при гораздо более коротких числах, например кривую X25519 в TLS 1.3, Signal и WhatsApp. Новая пара секретов для каждого соединения обеспечивает прямую секретность: даже если долговременный ключ сервера позже украдут, прошлые разговоры останутся в безопасности. Слабые параметры по-прежнему опасны, как показала атака Logjam 2015 года для старых 512-битных простых чисел, а большой квантовый компьютер с алгоритмом Шора взломал бы и классический, и эллиптический Диффи — Хеллман, поэтому сейчас рядом с ними внедряются постквантовые методы обмена ключами.

Попробуйте сами

Откройте визуализацию Диффи — Хеллмана, чтобы пройти пять шагов на доске, показывающей, что знают Алиса, открытый канал и Боб, — в красках и в числах. Выбирайте простые числа от 23 до 2 147 483 647, задавайте секреты сами и позвольте Еве атаковать перебором всех показателей: смотрите, как она мгновенно добивается успеха на малых простых числах и как растёт оценка времени поиска по мере удлинения простого числа.

Часто задаваемые вопросы

Диффи — Хеллман — это то же самое, что RSA?

Нет, хотя оба — методы с открытым ключом из 1970-х годов. RSA, опубликованный в 1977 году, умеет шифровать и подписывать с помощью открытого и закрытого ключей и опирается на сложность разложения больших чисел на множители. Диффи — Хеллман лишь позволяет договориться об общем секрете и опирается на задачу дискретного логарифмирования.

Насколько велики числа на практике?

Классический Диффи — Хеллман использует простые числа длиной не менее 2048 бит, это около 617 десятичных цифр, а часто 3072 или 4096 бит. Варианты на эллиптических кривых используют ключи примерно в 256 бит при сопоставимой стойкости.

Почему каждый дополнительный бит удваивает работу Евы?

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

Зачем Алисе и Бобу простое число?

При простом модуле у каждого числа от 1 до p − 1 есть обратное и существуют первообразные корни, поэтому степени g охватывают все возможности. Часто выбирают безопасные простые числа, у которых (p − 1)/2 тоже простое, чтобы исключить короткие пути, использующие малые делители p − 1.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть визуализацию Диффи — Хеллмана