Калькулятор алгоритма Диффи — Хеллмана
Выберите простой модуль p, генератор g и закрытые числа Алисы и Боба. Калькулятор покажет открытые значения, которыми они обмениваются, общий секрет, который каждый вычисляет сам, и то, порождает ли g все остатки по модулю p, — удобно для проверки задач.
Работает в браузере: всё, что вы вводите, никуда не отправляется.
Как пользоваться
- Введите простое p и основание g от 2 до p − 2. Это открытые параметры.
- Введите закрытый ключ Алисы a и закрытый ключ Боба b, каждый от 1 до p − 2.
- Смотрите открытые значения A и B, два вычисления, дающие одинаковый секрет, и порядок g.
Формулы
- Алиса: A = gᵃ mod p, Боб: B = gᵇ mod p.
- Алиса вычисляет s = Bᵃ mod p, Боб — s = Aᵇ mod p; оба равны gᵃᵇ mod p.
- Порядок g — наименьшее k > 0, при котором gᵏ ≡ 1 (mod p). Он всегда делит p − 1 и находится по простым множителям p − 1.
Пример
p = 23, g = 5, a = 6, b = 15.
- A = 5⁶ mod 23 = 15 625 mod 23 = 8.
- B = 5¹⁵ mod 23 = 19.
- Алиса: 19^6 mod 23 = 2. Боб: 8^15 mod 23 = 2. Общий секрет — 2.
- Порядок 5 по модулю 23 — 22 = p − 1, значит, 5 — первообразный корень.
Если взять a = 4 и b = 3, получится A = 4, B = 10 и секрет 18 — пример, который часто приводят в учебниках.
Советы
- Берите g первообразным корнем, чтобы секрет мог быть любым из p − 1 значений. Поменяйте g и посмотрите на строку порядка.
- Закрытые ключи не передаются. По сети идут только p, g, A и B; утечка a или b раскрывает секрет.
- Быстрая проверка задачи: при правильных данных строки Алисы и Боба всегда совпадают.
Частые вопросы
Как работает протокол Диффи — Хеллмана?
Стороны открыто договариваются о простом p и основании g. Алиса выбирает секрет a и отправляет A = gᵃ mod p, Боб выбирает b и отправляет B = gᵇ mod p. Алиса вычисляет Bᵃ mod p, Боб — Aᵇ mod p, и оба числа равны gᵃᵇ mod p — общему секрету, который по сети не передавался.
Почему перехватчик не узнает секрет?
Он видит p, g, A и B, но не a и b. Найти a по A = gᵃ mod p — задача дискретного логарифмирования, быстрого решения которой для больших правильно выбранных простых не известно. С малыми числами этого калькулятора её можно решить простым перебором.
Что такое первообразный корень и зачем он нужен?
g — первообразный корень по модулю p, если его степени дают все значения от 1 до p − 1, то есть порядок g равен p − 1. Для p = 23 число 5 — первообразный корень (порядок 22), а у 2 порядок 11: оно даёт только половину значений, и вариантов секрета меньше.
Проверяет ли Диффи — Хеллман, с кем идёт обмен?
Нет, сам по себе он только вырабатывает общий ключ. Злоумышленник посередине может провести отдельный обмен с каждой стороной. Поэтому в TLS и подобных протоколах открытые значения подписываются сертификатами.