Обмен ключами Диффи — Хеллмана
Как двум людям, которые никогда не встречались, договориться о секретном ключе, если кто-то слышит каждое их слово? В 1976 году Уитфилд Диффи и Мартин Хеллман нашли ответ, который сегодня защищает почти каждое безопасное соединение в интернете. Пройдите вместе с Алисой и Бобом пять шагов — один раз как смешивание красок, другой раз с настоящими числами, — а затем позвольте подслушивающей Еве атаковать: с малыми числами она побеждает в мгновение ока, а с размерами, применяемыми на практике, ей понадобилось бы больше времени, чем возраст Вселенной. Нажимайте «Следующий шаг», чтобы проследить, как Алиса и Боб договариваются о секрете, пока Ева читает всё, что они отправляют; «Назад» возвращает на шаг назад. Каждое значение показано и как краска, и как число. Заблокированные значения никогда не покидают владельца. Выберите справа простое число побольше или другие секреты либо нажмите «Новые секреты». На последнем шаге кнопка «Пусть Ева атакует» заставляет её перебирать все показатели, пока один не подойдёт: для малых простых чисел это легко, для настоящих — безнадёжно.
Как это работает
- Нажимайте «Следующий шаг», чтобы проследить обмен: открытое соглашение, секреты, сообщения и общий результат.
- Следите за каждым значением как за краской и как за числом и смотрите, какие из них остаются секретными, а какие Ева может прочитать.
- На последнем шаге нажмите «Пусть Ева атакует», затем выберите простое число побольше и посмотрите, как быстро её шансы исчезают.
Как работает обмен
Сначала Алиса и Боб открыто договариваются о простом числе p и числе g. Затем каждый выбирает секретное число — Алиса a, Боб b — и держит его при себе. Алиса отправляет Бобу A = gᵃ mod p, а Боб отправляет Алисе B = gᵇ mod p. Наконец Алиса вычисляет Bᵃ mod p, а Боб — Aᵇ mod p. Оба результата равны g в степени a·b mod p, так что теперь у них есть общее число, которое ни разу не передавалось по линии. У Евы, которая видела p, g, A и B, такого короткого пути нет.
Почему Ева в тупике
Вычислить gᵃ mod p быстро даже для чисел из сотен цифр благодаря повторному возведению в квадрат. Обратный путь — найти показатель a по результату — это задача дискретного логарифмирования, и для удачно выбранных простых чисел быстрый метод неизвестен. Для малых простых чисел в этой демонстрации Ева может просто перебрать все показатели; приложение считает её попытки и оценивает, сколько времени занял бы полный перебор. Каждый дополнительный бит простого числа удваивает работу, поэтому 2048-битные простые числа, используемые в интернете, делают полный перебор совершенно недостижимым. Версия с красками передаёт ту же идею: смешать цвета легко, а разделить смесь обратно на цвета практически невозможно.
Часто задаваемые вопросы
Почему работает аналогия с красками?
Смешать краски легко, а отменить смешивание нельзя — точно так же, как возвести g в степень по модулю p легко, а обратить это трудно. Алиса и Боб каждый добавляют свой секретный цвет к общему и обмениваются смесями; затем каждый добавляет свой секретный цвет к полученной смеси. У обоих в итоге общий цвет плюс оба секрета, а Ева видит только две двухцветные смеси и не может их разделить. Здесь краски смешиваются в равных долях, поэтому порядок не важен — точно так же, как (gᵃ)ᵇ = (gᵇ)ᵃ.
Что такое g и почему это должен быть первообразный корень?
g — это генератор: его степени g¹, g², …, g^(p−1) mod p пробегают все числа от 1 до p − 1. Благодаря этому открытые значения распределены по всем возможностям, и Ева узнаёт из них как можно меньше. Приложение выбирает для каждого простого числа наименьшее такое число, например g = 5 для p = 23.
Шифрует ли Диффи — Хеллман мои сообщения?
Нет. Он лишь позволяет договориться об общем секрете. Затем этот секрет используется как ключ для быстрого симметричного шифра, например AES, который и шифрует сами данные. Так работает каждое HTTPS-соединение: обмен ключами, обычно на эллиптических кривых, а затем симметричное шифрование.
Может ли Ева выдать себя за Боба?
Если использовать обмен сам по себе — да. «Человек посередине» может провести один обмен с Алисой, другой с Бобом и передавать всё дальше. Реальные протоколы предотвращают это: сервер доказывает свою подлинность цифровой подписью и сертификатом, так что обмен проходит с аутентификацией.
Отправляется ли что-нибудь на сервер?
Нет. Все числа, смешивание красок и атака Евы вычисляются в вашем браузере, а ваши настройки остаются в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор