Как двое договариваются о секрете, крича на всю площадь: алгоритм Диффи-Хеллмана без формул

Представьте себе площадь: людную, шумную, и на ней стоят двое, назовем их Алиса и Коля. Им нужно договориться о пароле, но шептаться друг с другом нельзя. А еще вокруг толпа, и в толпе стоит Ева, которая записывает каждое слово. Никаких записок, никаких встреч за кулисами, только крик через всю площадь.

Звучит как безнадежная задача. Все, что Алиса крикнет Коле, услышит и Ева. Любая информация, которая дойдет до Коли, дойдет и до нее. Кажется, что общий секрет в таких условиях невозможен в принципе.

А теперь плохая новость для нашей интуиции: именно это сейчас происходит на вашем устройстве. Когда ваш браузер открывал эту страницу, он буквально прокричал несколько чисел через весь интернет, провайдер их видел, любой узел по дороге их видел, и тем не менее у вас с сервером Хабра появился такой общий секретный ключ, который не знает никто из них. Это и есть протокол Диффи-Хеллмана, придуманный в 1976 году, и он до сих пор в той или иной форме сидит почти в каждом TLS-соединении

Я несколько раз пробовал объяснять его своим знакомым и каждый раз натыкался на одно и то же: классическая картинка с красками, которую я гуглил и показывал им, вроде бы работает, но оставляет ощущение недосказанности. Понятно, что происходит, но непонятно, почему это вообще работает. 

Так что сегодня план такой: сначала объяснение на красках, потом разбор, где эта аналогия недоговаривает, а потом главное — о чем картинка с красками вообще молчит. 

Security Center

Рассказываем о лучших практиках и средствах ИБ, требованиях и изменениях в законодательстве.

Исследовать →

Краски по шагам

Сама аналогия гениальная, ее придумали не вчера и уж тем более не я. Если вы ее уже видели, все равно пробегитесь глазами, дальше я буду на нее ссылаться.

Алиса и Коля публично договариваются об общей краске. Пусть будет желтая. Это не секрет, Ева тоже записала себе «желтая».

Дальше каждый у себя дома выбирает секретный цвет. Алиса взяла красный, а Коля синий. Эти баночки никто никому не показывает, они вообще не покидают дом.

Теперь каждый смешивает общую желтую со своим секретом. У Алисы получается оранжевая смесь, у Коли зеленая. И вот этими смесями они обмениваются прямо через площадь, в открытую. Ева видит оранжевую и зеленую банки, может их сфотографировать, может даже отлить себе немного.

Последний ход. Алиса берет зеленую смесь Коли и доливает туда свой секретный красный. Коля берет оранжевую смесь Алисы и доливает свой синий. У обоих в стакане теперь желтый + красный + синий, просто в разном порядке. А краскам на порядок плевать, цвет получается одинаковый. Какой-то бурый, неважно какой именно, важно, что один и тот же.

Ева тем временем сидит со своими записями: желтая, оранжевая, зеленая. Чтобы получить бурый, ей нужен хотя бы один секретный цвет в чистом виде. А вытащить красный из оранжевой смеси она не может, краски обратно не разделяются.

Все, общий секрет есть, ни один секретный цвет площадь не пересекал. Красиво.

Где краски врут

Скорее недоговаривают. Но недоговаривают в местах, из-за которых вся конструкция и кажется чем-то непонятным.

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

В настоящем Диффи-Хеллмане «неразделимость» вычислительная: операция обратима в принципе, но обратный ход требует столько вычислений, что Ева состарится, состарится Солнце, и только потом появится ответ. Это принципиально другой тип «нельзя», и (к сожалению для этой красивой аналогии) краски его не передают.

Второе. Аналогия не объясняет, почему итоговый цвет совпал. Вернее будет сказать, что объясняет слишком легко: ну краски перемешались, и порядок неважен, вот и все дела. Но это как раз самое сильное требование ко всей конструкции. Нужна операция, у которой результат не зависит от порядка применения секретов, и при этом она необратима для постороннего. Найти такую операцию и было главным достижением 1976 года. 

Третье, и самое, на мой взгляд, интересное. В аналогии Ева только слушает. А что если она не слушает, а перехватывает банки по дороге и подменяет их? Про это в конце (и это, к слову, не теоретическая придирка).

Часы вместо красок

Теперь соберем настоящий механизм, и обойдемся почти без формул, как и обещал. Понадобится одна школьная операция: остаток от деления, и циферблат.

Обычные часы — это арифметика с остатком от деления на 12. Сейчас 10 утра, прибавили 5 часов, стало 3, потому что 15 при делении на 12 дает остаток 3. Стрелка дошла до конца и пошла по новому кругу.

В Диффи-Хеллмане циферблат не на 12 делений, а на огромное простое число, но для интуиции возьмем игрушечный, на 23 деления. И вместо «прибавления часов» будем делать другое действие: умножать на 5 и смотреть, куда упала стрелка. Встали на 5. Умножили на 5, получили 25, на циферблате из 23 делений это деление номер 2. Еще раз умножили на 5: 10. Еще раз, 4. Потом 20, потом 8, потом 17…

Посмотрите на гифку, стрелка скачет по циферблату. Нет никакого видимого порядка, точка мечется туда-сюда, и в этом весь смысл. Сделать N шагов вперед элементарно, школьник справится с калькулятором, а компьютер с числами в сотни цифр справляется за микросекунды. 

А вот обратная задача: я говорю вам «стрелка стоит на 19», скажите, сколько шагов я сделал. На циферблате из 23 делений вы переберете варианты за несколько минут. На циферблате из числа в 600 десятичных цифр перебор не светит никому, а ничего радикально лучше перебора человечество за полвека так и не придумало. Эта обратная задача называется дискретным логарифмом, и вся стойкость протокола висит на том, что она тяжелая.

Вот она, наша «краска, которую нельзя разделить». Номер шага, по сути, и есть наш секретный цвет. 

Теперь сам протокол, на игрушечных числах. Циферблат на 23, шагаем умножением на 5, эти два числа публичные, Ева их знает.

Алиса загадывает секрет: 6 шагов. Прошагала, стрелка встала на 8. Кричит через площадь: «восемь»!

Коля загадывает 15 шагов. У него стрелка встала на 19. Кричит: «девятнадцать»!

Дальше тот же ход, что с красками. Алиса берет позицию Коли, 19, и шагает от нее свои секретные 6 шагов. Получает 2. Коля берет восьмерку Алисы и шагает свои 15. Тоже получает 2. Совпало не случайно: оба в итоге сделали 6 на 15 шагов от стартовой позиции, просто в разном порядке, сначала 6, потом 15 или наоборот. А умножению на порядок плевать ровно так же, как краскам. Вот и вся коммутативность.

Ева видела: циферблат 23, шаг 5, числа 8 и 19. Чтобы получить двойку, ей нужен чей-нибудь секретный счетчик шагов. То есть нужно решить тот самый дискретный логарифм. 

На циферблате из 23 она его решит, поэтому реальные циферблаты выглядят так:

import secrets

p = int(
    "FFFFFFFFFFFFFFFFADF85458A2BB4A9AAFDC5620273D3CF1"
    "D8B9C583CE2D3695A9E13641146433FBCC939DCE249B3EF9"
    "7D2FE363630C75D8F681B202AEC4617AD3DF1ED5D5FD6561"
    "2433F51F5F066ED0856365553DED1AF3B557135E7F57C935"
    "984F0C70E0E68B77E2A689DAF3EFE8721DF158A136ADE735"
    "30ACCA4F483A797ABC0AB182B324FB61D108A94BB2C8E3FB"
    "B96ADAB760D7F4681D4F42A3DE394DF4AE56EDE76372BB19"
    "0B07A7C8EE0A6D709E02FCE1CDF7E2ECC03404CD28342F61"
    "9172FE9CE98583FF8E4F1232EEF28183C3FE3B1B4C6FAD73"
    "3BB5FCBC2EC22005C58EF1837D1683B2C6F34A26C1B2EFFA"
    "886B423861285C97FFFFFFFFFFFFFFFF", 16
)
g = 2

a = secrets.randbelow(p - 2) + 1  # секрет Алисы
b = secrets.randbelow(p - 2) + 1  # секрет Коли

A = pow(g, a, p)  # Алиса отправляет это
B = pow(g, b, p)  # Коля отправляет это

print(pow(B, a, p) == pow(A, b, p))  # True, общий ключ совпал

Число «p» здесь занимает 2048 бит, примерно 617 десятичных цифр. «Шаги вперед» через pow с тремя аргументами Phyton делает мгновенно, а лучшая известная атака на дискретный логарифм для такого размера оценивается в число операций, рядом с которым возраст Вселенной выглядит несерьезно.

Кстати, маленькая деталь: общий ключ при этом никто никуда не передавал. Он не существовал до последнего шага и родился одновременно в двух головах. По проводу летали только позиции стрелки.

Дыра, про которую молчит картинка с красками

А теперь обещанное. Перечитайте протокол глазами параноика. Алиса получила с площади число 19 и поверила, что оно от Коли. С чего вдруг?

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

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

И, кстати, ровно так работают корпоративные прокси, которые «инспектируют» HTTPS-трафик сотрудников, и так же работали известные атаки на публичный Wi-Fi. Поэтому в реальном TLS поверх Диффи-Хеллмана обязательно стоит второй слой: сертификаты и подписи. Сервер подписывает свою часть обмена ключом, подпись проверяется по цепочке доверия, и условная Маша отваливается, потому что подделать подпись не может. Диффи-Хеллман отвечает на вопрос «как получить общий секрет», и только сертификаты отвечают на вопрос «а с тем ли я его получил». По отдельности обе части бесполезны.

И раз уж пошла речь про реальный мир, еще одни грабли, уже исторические. В 2015 году исследователи показали атаку Logjam: оказалось, что огромная часть серверов использовала один и тот же стандартный циферблат, причем местами еще и короткий, 512-битный. А у дискретного логарифма есть неприятное свойство: самая дорогая часть атаки зависит только от циферблата. Один раз вложился в предвычисление для популярного «p», дальше щелкаешь отдельные соединения за минуты. Мораль вышла простая и общеприменимая: общий для всех параметр — это общая для всех точка отказа.

Что вместо этого крутится у вас в браузере

Классический Диффи-Хеллман на циферблате из простого числа в TLS 1.3 формально остался, однако на практике почти весь трафик ходит через его близкого родственника на эллиптических кривых, чаще всего это X25519. Идея ровно та же: легко вперед, безнадежно назад, секреты коммутируют. Просто вместо прыжков стрелки по циферблату там прыжки точки по кривой, и та же стойкость достигается ключами в разы короче, 256 бит вместо 2048+, что быстрее и дешевле.

И еще одна вещь, которую дает современный вариант и которую я считаю самой недооцененной: секреты там одноразовые. На каждое соединение генерируется свежая пара, после рукопожатия секрет выбрасывается. Следствие неочевидное и красивое: даже если завтра у сервера украдут вообще все долговременные ключи, расшифровать записанный вчера трафик не получится, одноразовые секреты уже не существуют нигде. Свойство называется forward secrecy, и именно ради него некоторые мессенджеры пересогласовывают ключи чуть ли не на каждое сообщение.

Тучи на горизонте тоже есть, честности ради. Алгоритм Шора на достаточно большом квантовом компьютере решает дискретный логарифм быстро, причем и на циферблате, и на кривых. Достаточно большого пока не существует, но трафик можно записывать уже сейчас и расшифровать потом, поэтому переход начался заранее: в TLS уже живут гибридные рукопожатия, где рядом с X25519 работает постквантовый ML-KEM, он же бывший Kyber. Сама задача там другая, решетки вместо логарифмов, но роль в протоколе ровно та же: двое кричат через площадь и получают общий секрет.

Так что сцена с площадью никуда от нас не денется, поменяется только то, что именно кричат. Полвека идея держится в неизменном виде: не передавай секрет, передай половинки, из которых секрет соберется только у вас двоих. По-моему, это одна из самых красивых идей, до которых люди вообще додумались. И уж точно самая красивая из тех, что срабатывают у вас за спиной по сто раз на дню.