Двое незнакомцев договариваются о тайном ключе, а их разговор слышит каждый. Как это возможно и где здесь подвох?
Алиса и Боб никогда не встречались. Говорить они могут только так, что каждое их слово слышит Ева. Могут ли они прямо сейчас, при ней, договориться о пароле, который Ева не узнает?
Интуиция отвечает твёрдым «нет». Всё, что знает Боб, пришло к нему по общему каналу, а значит, это знает и Ева. Откуда у Боба возьмётся то, чего нет у неё?
Тысячи лет так и было. Любой шифр, от Цезаря до DES, требовал заранее доставить ключ обеим сторонам надёжным путём: курьером, дипломатической почтой, из рук в руки. Даже горячая линия Москва — Вашингтон, открытая в 1963 году, работала на одноразовых лентах с ключами, которые стороны передавали друг другу через посольства. Чем больше людей хотели говорить тайно, тем тяжелее становилась эта логистика.
Сначала уточним, что это такое. Диффи — Хеллман — не шифр, а протокол выработки общего ключа. Он ничего не шифрует, а только даёт Алисе и Бобу одинаковый секретный ключ. Переписку этим ключом потом шифрует обычный шифр, например AES.
Весь протокол держится на одной вещи: нужна операция, которую легко сделать и трудно отменить. Проще всего сначала представить её на красках.
Есть общая краска, её знают все. Алиса и Боб подмешивают к ней каждый свою тайную краску и открыто обмениваются смесями. Потом каждый добавляет свою тайную краску к чужой смеси. В банках у обоих оказывается одно и то же, а Ева, видя обе смеси, тайные краски из них не вытащит.
Упрощение: настоящую смесь красок в лаборатории разделить всё-таки можно. Поэтому в протоколе вместо красок числа.
В настоящем протоколе «смешать» значит возвести в степень по модулю: возвести число в степень, разделить результат на модуль p и оставить только остаток. Например, 30 mod 23 = 7, потому что 30 = 1 · 23 + 7. Ниже каждый шаг сначала в общем виде, а потом на маленьком примере, который считается в уме. Такие же числа стоят в игре по умолчанию, и там их можно менять.
Алиса и Боб открыто договариваются о двух числах. p — модуль, большое простое число: в реальных системах его длина 2048 бит и больше, то есть в нём не меньше 617 десятичных цифр. g — основание, которое будут возводить в степень. Его выбирают так, чтобы степени g давали как можно больше разных остатков (подробнее — в разделе «Для любознательных»). Готовые пары p и g обычно берут из стандартов. Их знают все, включая Еву: это не утечка, так и задумано.
Пример: p = 23, g = 5.
Каждый выбирает случайное тайное число: Алиса — a, Боб — b. В реальном протоколе это числа длиной в сотни бит, и для каждого нового соединения их выбирают заново. Тайные числа никуда не отправляются: это и есть «тайные краски».
Пример: a = 2, b = 3.
Алиса вычисляет A = ga mod p, Боб — B = gb mod p. Это и есть «смешать свою краску с общей». A и B уходят по каналу открыто, и Ева их видит.
Пример: A = 5² mod 23: 5² = 25 = 1 · 23 + 2, значит A = 2. B = 5³ mod 23: сначала степень целиком, 5³ = 125, потом деление с остатком, 125 = 5 · 23 + 10, значит B = 10.
Алиса возводит полученное B в свою тайную степень: s = Ba mod p. Боб делает то же с A: s = Ab mod p. Числа выходят одинаковые, хотя сам ключ по каналу не проходил ни разу. В реальных системах s такой же длины, как p, и из него потом выводят ключ для симметричного шифра.
Пример: у Алисы 10² = 100 = 4 · 23 + 8, у Боба 2³ = 8 (это меньше 23, делить нечего). У обоих s = 8.
B — это gb, поэтому у Алисы Ba = gb·a, а у Боба Ab = ga·b. От перестановки множителей произведение не меняется, как смесь красок не зависит от порядка смешивания. А остаток от деления на p можно брать на любом этапе, итог от этого не меняется. Общая формула: s = Ba = Ab = gab mod p.
В ноябре 1976 года Уитфилд Диффи и Мартин Хеллман из Стэнфорда опубликовали статью «New Directions in Cryptography». Она начиналась словами «Мы стоим на пороге революции в криптографии». Время было подходящее: компьютеры начали соединять в сети, и развозить ключи курьерами каждому, кто хочет поговорить с каждым, стало невозможно. На идею повлияла работа Ральфа Меркла, который независимо искал способ договориться о ключе открыто. Позже Хеллман предлагал называть протокол обменом Диффи — Хеллмана — Меркла.
Идея носилась в воздухе. В британской спецслужбе связи GCHQ Джеймс Эллис ещё в 1970 году описал «несекретное шифрование», а Малкольм Уильямсон в 1974 году нашёл по сути тот же протокол. Эти работы были засекречены и вышли на свет только в 1997 году. Поэтому протокол носит имена тех, кто опубликовал его открыто, а в 2015 году Диффи и Хеллман получили премию Тьюринга за криптографию с открытым ключом.
Сегодня этот обмен незаметно работает почти в каждом защищённом соединении:
Каждое соединение по TLS 1.3 начинается с обмена Диффи — Хеллмана, обычно на эллиптической кривой X25519. Тайные числа выбирают заново для каждого соединения и стирают после него: даже если сервер потом взломают, старые разговоры не расшифровать. Это свойство называют прямой секретностью.
Signal и WhatsApp договариваются о ключах переписки несколькими обменами Диффи — Хеллмана. Протокол MTProto в Telegram тоже построен на этом обмене.
Удалённый вход на сервер и защищённые туннели получают сеансовый ключ тем же способом. Дальше этот ключ шифрует данные симметричным шифром, например AES.
Рядом с Диффи — Хеллманом всегда называют RSA. Оба придуманы в 1970-х, оба работают с открытыми и тайными числами и оба считают степени по модулю, поэтому их легко спутать. Но задачи у них разные. Диффи — Хеллман ничего не шифрует: он нужен, чтобы двое вместе получили общий ключ. RSA — это замок: Боб раздаёт его заранее, и любой может запереть письмо так, что открыть его сможет только Боб.
| Вопрос | Диффи — Хеллман | RSA |
|---|---|---|
| Что делает | Двое вырабатывают общий секретный ключ | Запирает письмо для одного адресата; тем же способом подписывают |
| Кто должен участвовать | Оба сразу: каждый вносит своё тайное число | Только отправитель: замок Боба уже у всех, сам Боб может быть не в сети |
| Что идёт по каналу | Открытые числа A и B; самого ключа в канале нет | Запертое письмо c |
| Сколько живут ключи | Тайные числа новые в каждом разговоре | Один замок на годы |
| На чём держится | Трудно найти тайное число по открытому (дискретный логарифм) | Трудно разложить n на два простых числа |
| Аналогия | Краски, которые смешивают вдвоём | Открытый навесной замок |
В российских средствах криптографической защиты общий ключ вырабатывают по алгоритму VKO. Он описан в рекомендациях по стандартизации Р 50.1.113-2016 и работает на эллиптических кривых из стандарта подписи ГОСТ Р 34.10-2012 длиной 256 или 512 бит. Идея та же, что в игре: у каждого есть тайное число и вычисленное из него открытое; каждый соединяет своё тайное с чужим открытым, и у обоих получается одно и то же.
Отличий от учебной схемы два. К вычислению подмешивают случайное число UKM, которое передаётся открыто: так из одних и тех же долговременных ключей каждый раз получается новый общий ключ. А сам результат не используют напрямую, а пропускают через хэш-функцию «Стрибог» (ГОСТ Р 34.11-2012). Готовый ключ дальше шифрует данные «Кузнечиком» или «Магмой». VKO работает и в российских наборах шифров для TLS.
В интерактивной демонстрации Ludus Lab весь протокол проходится руками на маленьких числах. Ева видит всё то же, что и вы, и можно проверить, где ей не хватает данных, а где она побеждает. Вот что стоит попробовать:
Все три работают по одной схеме: тайное число, открытое число, общий секрет. Различаются они тем, в каком мире ведутся вычисления:
| Параметр | Классический DH | ECDH (X25519) | VKO (ГОСТ) |
|---|---|---|---|
| Где считают | Остатки по модулю простого p | Точки кривой Curve25519 | Точки кривых ГОСТ Р 34.10-2012 |
| Размер чисел | 2048–4096 бит | 255 бит | 256 или 512 бит |
| Стойкость, примерно | ≈ 112 бит при 2048 | ≈ 128 бит | ≈ 128 или ≈ 256 бит |
| Что делают с общим секретом | Функция выработки ключей (в TLS — HKDF) | Функция выработки ключей (в TLS — HKDF) | Хэш «Стрибог» с открытым числом UKM |
| Год | 1976 | 2006 (Д. Бернштейн) | 2016 |
| Стандарт | RFC 3526, RFC 7919 | RFC 7748 | Р 50.1.113-2016 (RFC 7836) |
| Кто выпускает | IETF | IETF | ТК 26, Росстандарт |
Ева умнее простого перебора. Для дискретного логарифма по модулю p есть хитрый метод — решето числового поля. Из-за него 2048-битное p даёт стойкость примерно как 112-битный ключ симметричного шифра, а вовсе не как 2048-битный. На эллиптических кривых таких хитростей не знают: лучшие методы требуют порядка квадратного корня из полного перебора, поэтому кривой в 256 бит хватает для стойкости около 128 бит. Отсюда и переход на кривые: ключи короче, вычисления быстрее.
В 2015 году исследователи показали атаку Logjam. Многие серверы использовали одни и те же стандартные p длиной 512 и 1024 бита, а часть из них по старым «экспортным» правилам соглашалась на 512 бит. Для фиксированного p самую тяжёлую часть вычислений можно проделать один раз заранее, а потом быстро находить ключи всех соединений с этим p. Для 512 бит такая подготовка заняла около недели, для 1024 бит её оценили как посильную для государства. После этого 1024-битные группы списали: сейчас берут p от 2048 бит или переходят на кривые.
Квантовый компьютер с алгоритмом Шора решил бы задачу дискретного логарифма быстро, причём и по модулю p, и на эллиптических кривых. Таких машин пока нет, но записанный сегодня трафик можно будет расшифровать потом. Поэтому с 2024 года браузеры добавляют к X25519 постквантовый механизм ML-KEM (стандарт FIPS 203): ключ складывают из двух частей, и чтобы его узнать, придётся взломать обе.
Степени g по модулю p должны пробегать как можно больше разных остатков. В примере из статьи (g = 5, p = 23) они дают все 22 числа от 1 до 22: такое g называют первообразным корнем. А если взять g = 22, степени будут чередоваться: 22, 1, 22, 1… Тогда A может быть только одним из двух чисел, и Еве хватит двух попыток. Поэтому игра даёт выбирать только «хорошие» пары p и g.
Упрощение: в настоящих системах g часто берут не первообразным корнем, а элементом огромной подгруппы простого порядка (например, при p = 2q + 1, где q тоже простое). Важно не то, чтобы степени g покрыли всё, а то, чтобы их было астрономически много и не нашлось маленьких подгрупп, через которые Ева могла бы зайти.
Теперь вы знаете, как двое договариваются о секрете при всех и почему этого мало, если кто-то может вмешаться
В демонстрации вы смешаете краски, пересчитаете степени на табло фонарей, сыграете за Еву и увидите, где её атака проваливается, а где удаётся