Алгоритм Диффи-Хеллмана: обмен ключами без передачи ключа

Алгоритм Диффи-Хеллмана - это протокол обмена ключами, который позволяет двум сторонам выработать общий секретный ключ через полностью открытый канал, не передавая сам ключ. Схему в 1976 году опубликовали Уитфилд Диффи и Мартин Хеллман (с заметным вкладом Ральфа Меркла), и она стала первой практической реализацией асимметричной криптографии. Идея проста на поверхности и глубока внутри: безопасность держится на вычислительной сложности задачи дискретного логарифма. В этой статье разбираем математику протокола, пошаговый обмен, выбор параметров $p$ и $g$, атаку «человек посередине» и характерные ошибки, которые студенты допускают на экзамене по защите информации.

Что решает обмен ключами Диффи-Хеллмана

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

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

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

Математическая основа: дискретный логарифм

Протокол работает в мультипликативной группе вычетов по модулю простого числа $p$. Выбирается образующая (генератор) $g$ - элемент, степени которого пробегают по всем ненулевым вычетам по модулю $p$. Публичными параметрами становятся пара $(p, g)$ - их знают все, в том числе перехватчик.

Каждая сторона генерирует приватный показатель: Алиса выбирает случайное $a$, Боб - случайное $b$. По ним считаются публичные значения: $A = g^a \bmod p, \qquad B = g^b \bmod p.$

Возвести $g$ в степень по модулю легко, а вот обратная задача - по известным $g$, $p$ и $A = g^a \bmod p$ найти показатель $a$ - это и есть задача дискретного логарифма. Для больших $p$ (тысячи бит) эффективного алгоритма решения не известно, что и обеспечивает стойкость. Именно асимметрия «легко вперёд, трудно назад» делает алгоритм Диффи-Хеллмана работоспособным.

Пошаговый протокол обмена ключами

Классический сеанс обмена ключами по Диффи-Хеллману укладывается в пять шагов.

1. Стороны согласуют публичные параметры - простое $p$ и генератор $g$. Их можно жёстко зашить в стандарт или передать открыто.
2. Алиса выбирает секрет $a$, вычисляет $A = g^a \bmod p$ и отправляет $A$ Бобу.
3. Боб выбирает секрет $b$, вычисляет $B = g^b \bmod p$ и отправляет $B$ Алисе.
4. Алиса считает $K = B^a \bmod p$; Боб считает $K = A^b \bmod p$.
5. Оба получают одно и то же значение - общий секретный ключ.

Совпадение объясняется свойством степеней: $B^a = (g^b)^a = g^{ab} = (g^a)^b = A^b \pmod p.$

Общий секрет $K = g^{ab} \bmod p$ никогда не передаётся по каналу - его вычисляют независимо обе стороны. Ева видит только $p$, $g$, $A$ и $B$; чтобы получить $K$, ей пришлось бы решить дискретный логарифм и найти $a$ или $b$.

Числовой пример на маленьких параметрах

Возьмём учебные значения $p = 23$, $g = 5$. Пусть Алиса выбрала $a = 6$, Боб - $b = 15$.

Публичные значения: $A = 5^6 \bmod 23 = 15625 \bmod 23 = 8,$ $B = 5^{15} \bmod 23 = 19.$

Общий секрет: $K_{\text{Алиса}} = 19^6 \bmod 23 = 2, \qquad K_{\text{Боб}} = 8^{15} \bmod 23 = 2.$

Значения совпали: $K = 2$. На таких крошечных числах дискретный логарифм Ева подберёт перебором мгновенно, поэтому реальные параметры берут из стандартизованных групп с $p$ длиной не менее 2048 бит.

Выбор параметров p и g

От параметров напрямую зависит стойкость. Несколько правил.

• Модуль $p$ должен быть большим простым. Современная рекомендация - не менее 2048 бит, для долгосрочной защиты 3072 бита и выше.
• Особенно удобны безопасные простые: $p = 2q + 1$, где $q$ тоже простое. В такой группе порядок подгруппы делится только на 2 и $q$, что закрывает целый класс атак с малыми подгруппами.
• Генератор $g$ должен порождать подгруппу большого простого порядка. Часто берут $g = 2$ для подходящего безопасного простого.
• Приватные показатели $a$, $b$ - криптографически случайные, свежие для каждого сеанса (это даёт прямую секретность, forward secrecy).

Самостоятельно «придумывать» $p$ и $g$ не нужно: используют проверенные группы из RFC 3526 (MODP-группы) или переходят на эллиптические кривые (ECDH), где те же идеи работают на меньших ключах.

Атака «человек посередине»

Сам по себе алгоритм Диффи-Хеллмана защищает только от пассивного прослушивания. Против активного злоумышленника он беззащитен. В атаке «человек посередине» (man-in-the-middle) Меллори встаёт между сторонами и подменяет публичные значения: Алисе он шлёт своё $M = g^m \bmod p$ вместо $B$, а Бобу - вместо $A$. В итоге Меллори делит один секрет с Алисой и другой с Бобом, прозрачно расшифровывая и пересылая трафик.

Корень проблемы - отсутствие аутентификации: стороны не знают, чьё именно публичное значение получили. Лечится это привязкой публичных значений к подлинности: подписью (authenticated DH), сертификатами или общим паролем (PAKE). Именно в таком, аутентифицированном, виде Диффи-Хеллман живёт внутри TLS, IPsec и Signal. К слою аутентификации тесно примыкают и другие криптопротоколы - например, доказательство с нулевым разглашением, позволяющее подтвердить владение секретом, не раскрывая его.

Частые ошибки

• Путают приватный и публичный ключ. Передавать по каналу можно только $A$ и $B$; показатели $a$ и $b$ остаются у владельцев и наружу не выходят.
• Считают, что DH сам по себе аутентифицирует стороны. Без подписи или сертификата протокол уязвим к атаке «человек посередине» - это не опция, а обязательное дополнение.
• Берут маленькое или составное $p$. Учебные $p = 23$ годятся только для иллюстрации; в реальной системе нужен большой простой модуль из стандартизованной группы.
• Используют общий секрет как ключ напрямую. $g^{ab} \bmod p$ - это число с неравномерным распределением; перед использованием его прогоняют через KDF.
• Переиспользуют приватный показатель между сеансами. Свежие $a$, $b$ на каждый сеанс дают прямую секретность: компрометация одного ключа не раскрывает прошлые сессии.

FAQ

Чем алгоритм Диффи-Хеллмана отличается от RSA? RSA - это полноценная асимметричная схема шифрования и подписи: им можно зашифровать сообщение или подписать его. Диффи-Хеллман решает более узкую задачу - согласование общего секретного ключа; шифровать им напрямую нельзя. На практике их часто комбинируют: DH вырабатывает сеансовый ключ, а подпись (RSA или ECDSA) аутентифицирует обмен.

Что такое ECDH и зачем он нужен? ECDH - это тот же протокол Диффи-Хеллмана, перенесённый из группы вычетов по модулю $p$ в группу точек эллиптической кривой. Задача дискретного логарифма на кривых сложнее, поэтому сравнимая стойкость достигается на гораздо более коротких ключах (256 бит ECDH ≈ 3072 бита классического DH), что экономит память и время.

Можно ли восстановить общий секрет, перехватив весь трафик? Только решив задачу дискретного логарифма - найти $a$ по $A = g^a \bmod p$. Для корректно выбранных больших параметров эффективного алгоритма не существует, поэтому пассивный перехват $p$, $g$, $A$ и $B$ не раскрывает $K = g^{ab} \bmod p$.

Коротко

Алгоритм Диффи-Хеллмана позволяет двум сторонам выработать общий секрет $K = g^{ab} \bmod p$ по открытому каналу, обмениваясь лишь публичными значениями $A = g^a \bmod p$ и $B = g^b \bmod p$. Стойкость держится на сложности дискретного логарифма, безопасность параметров - на большом простом $p$ и правильном генераторе $g$, а защита от активного злоумышленника - на обязательной аутентификации поверх протокола.