Общий секрет по открытому каналу: обмен ключами Диффи-Хеллмана

Если ты проведёшь обмен ключами на маленьких числах, объяснишь, почему обе стороны получают одно число и что должен вычислить подслушивающий, и знаешь, от какой атаки протокол не защищает, - листай до «Теперь сам».

Как думаешь, можно ли договориться о секрете вслух

Двое хотят переписываться так, чтобы третий не прочёл. Способ известен тысячи лет: общий секретный ключ. Самый простой шифр с ключом - прибавить к каждой букве сообщения свою букву ключа по модулю размера алфавита, а при расшифровке вычесть. Если ключ случаен, не короче сообщения и используется один раз, такой шифр - его называют одноразовым блокнотом - не вскрывается в принципе: любой текст той же длины одинаково возможен.

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

На что это похоже

Представь, что двое смешивают краски на виду у всех. Сначала открыто выбирают общий цвет - жёлтый. Каждый втайне добавляет в свою банку жёлтой краски свой секретный цвет и передаёт смесь другому. Все видят две смеси. Теперь каждый добавляет свой секретный цвет в полученную банку - и у обоих выходит один и тот же итог: жёлтый плюс оба секретных цвета.

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

Механизм: степень вместо краски

В роли смешивания - возведение в степень по модулю простого числа. Открыто выбираются простое p и основание g. Первая сторона - по традиции Алиса - выбирает секретное число a, вторая - Боб - секретное b. Секретные числа берут случайными от 2 до p − 2, а основание - такое, чтобы его степени пробегали много разных остатков: у двойки по модулю 101 круг степеней полный, все сто значений.

            Алиса               канал (слышат все)      Боб
секрет      a = 37              p = 101,  g = 2         b = 58

отправляет  A = gᵃ mod p = 55   ─────  55  ─────►
                                ◄────  47  ──────       B = gᵇ mod p = 47

вычисляет   Bᵃ mod p = 82                               Aᵇ mod p = 82
            (47³⁷ mod 101)                              (55⁵⁸ mod 101)

Почему числа совпали: Bᵃ = (gᵇ)ᵃ = g^(ab), и Aᵇ = (gᵃ)ᵇ = g^(ab). Порядок, в котором возводят в степень, не важен. Общий секрет - g^(ab) mod p, здесь 82. По каналу прошли p, g, 55 и 47; числа 37, 58 и 82 канала не касались.

Подслушавший знает g, p и gᵃ mod p. Чтобы получить секрет, ему достаточно найти a. Эта задача называется дискретным логарифмом: по числам g, p и A найти показатель x, для которого gˣ ≡ A (mod p). Слово «логарифм» здесь в прямом смысле - показатель степени; «дискретный» - потому что всё происходит в остатках, где нет ни «больше», ни «ближе». У обычного логарифма можно сужать отрезок: 2ˣ растёт вместе с x. Остатки степеней прыгают по кругу без порядка, и сужать нечего.

Правило

Обмен ключами Диффи-Хеллмана: открыты простое p и основание g; стороны выбирают секретные a и b, обмениваются A = gᵃ mod p и B = gᵇ mod p и вычисляют общий секрет Bᵃ mod p = Aᵇ mod p. Каждая сторона делает две степени по модулю. Стойкость опирается на трудность дискретного логарифма: лучшие общие методы находят показатель за порядка √p действий. Протокол не удостоверяет собеседника: тот, кто может подменять сообщения, проводит обмен с каждой стороной отдельно.

Разбор: обмен на числах побольше

p = 9007199254740881
g = 3
a = 1234567890123457
A = pow(g, a, p)

p - самое большое простое число, которое помещается в точное целое тренажёра, шестнадцать цифр. Боб делает то же со своим b = 8765432109876543.

A = 3ᵃ mod p        7 652 280 012 307 744        уходит в канал
B = 3ᵇ mod p        1 275 498 894 168 787        уходит в канал
Bᵃ mod p            7 645 290 973 245 443        у Алисы
Aᵇ mod p            7 645 290 973 245 443        у Боба

Весь обмен - четыре степени, 215 шагов тренажёра. В настоящем протоколе p - число из 2048 бит или больше, и арифметика та же, только разрядов больше.

Разбор: во что обходится подслушивание

Возьмём модуль поменьше, p = 1 000 003, g = 2, и пусть в канале видно A = 770 825. Найдём показатель двумя способами.

Перебор: умножать на g, пока не получится A.

x = 0
t = 1
while t != A:
    t = t * g % p
    x = x + 1

Находит x = 777 777 за 2 333 358 шагов. Работа пропорциональна самому показателю, то есть до p.

Второй способ - встреча посередине из раздела про перебор. Запишем показатель как x = i · m + j, где m около √p. Тогда gˣ = A - то же, что gʲ = A · (g⁻ᵐ)ⁱ. Слева - m значений, их кладём в словарь. Справа - начинаем с A и умножаем на g⁻ᵐ, пока не попадём в словарь. Два цикла по тысяче витков вместо одного на миллион - программа повторяет встречу посередине из раздела про перебор, со словарём на m = 1001 значение:

p = 1 000 003                   шагов
степень по модулю (честный путь)     22
перебор показателя            2 333 358
встреча посередине               10 973

Тысяча витков - это √p. Подслушивающему стало легче в двести раз, но порядок его работы - √p, то есть 10 в степени «половина числа цифр». Для 2048-битного p существуют методы ещё быстрее - родня решета числового поля из урока про разложение, - поэтому модуль и берут таким длинным. А в группах точек эллиптических кривых ничего лучше √p не известно, и там хватает чисел из 256 бит. На этом стоит обмен ключами X25519, которым сегодня защищено большинство соединений.

Теперь граница. Пусть посторонний не только слушает, но и стоит между сторонами. Он перехватывает A, отправляет Бобу своё gᶜ, перехватывает B, отправляет Алисе то же gᶜ. У него два общих секрета - с каждой стороной свой, - и он перешифровывает переписку, читая её. Ни одна сторона ничего не замечает: числа в канале выглядят как случайные в обоих случаях. Математика протокола тут цела - сломано допущение, что в канале то число, которое отправил собеседник.

Что ломается без этого

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

Второе: один и тот же показатель на годы. Если секретное a постоянное и однажды утечёт, читается вся записанная прошлая переписка. Показатели выбирают заново на каждое соединение и стирают: утечка сегодня не раскрывает вчера. Это свойство называют прямой секретностью.

Третье: маленький или «удобный» модуль. При p из 512 бит дискретный логарифм вычисляли на практике ещё в 2015 году. Если у p − 1 все простые делители маленькие, логарифм распадается на лёгкие части по китайской теореме. Параметры берут из стандартов, а не изобретают.

Четвёртое: предсказуемый секрет. Показатель из генератора, начальное значение которого - время запуска, перебирается за секунды. Для ключей нужен криптографический источник случайности - в Python это модуль secrets, а не random.

Зачем это в работе

Каждое соединение HTTPS начинается с обмена ключами. В TLS 1.3 других вариантов нет: старый способ - зашифровать ключ сеанса открытым ключом сервера - убран именно из-за отсутствия прямой секретности. SSH, WireGuard, мессенджеры со сквозным шифрованием делают то же самое.

С 2024 года к обмену на эллиптических кривых добавляют второй, построенный на другой задаче, - ML-KEM, и секреты смешивают. Причина - квантовый алгоритм ШораРазбирается в разделе 21, глава «Квантовая модель - кубит, интерференция, алгоритм Шора»: Алгоритм Шора и границы: что квантовый компьютер ускоряет, а что нет: он решает и разложение, и дискретный логарифм за полиномиальное время, а записать чужую переписку сегодня и расшифровать через десять лет можно уже сейчас. К 2026 году такой двойной обмен включён по умолчанию в браузерах и в OpenSSL 3.5.

Сам приём - действие, лёгкое в одну сторону и трудное в обратную, - шире криптографии. На нём же стоят хранение паролей в виде хешей и проверка целостности файлов.

Теперь сам

1. p = 23, g = 5. Секрет Алисы a = 4, секрет Боба b = 3. Найди A, B и общий секрет.
2. Что из чисел p, g, a, b, A, B, g^(ab) видит подслушивающий?
3. Перебор показателя по модулю p из 7 цифр занял около двух миллионов шагов. Сколько примерно витков сделает встреча посередине по модулю из 15 цифр?
4. Сервер годами использовал одно и то же секретное a. Сегодня оно утекло. Что с перепиской за прошлый год, если её записывали?