Обмен ключами Диффи — Хеллмана и задача дискретного логарифма

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

Работа Диффи и Хеллмана «New Directions in Cryptography» изменила это: две стороны могут выработать общий секрет, обмениваясь только открытыми значениями по прослушиваемому каналу ¹. Идея опирается на асимметрию вычислений: возведение в степень по модулю делается быстро, а обратная операция — дискретный логарифм — не имеет известного эффективного алгоритма. Тот же математический аппарат дал шифрование с открытым ключом (Эль-Гамаль, тема 12 — RSA), электронную подпись и всю современную инфраструктуру доверия.

Тема устроена как разбор протокола и его слабостей. Сначала — проблема распределения ключей и идея открытого ключа, включая малоизвестную историю GCHQ. Затем — сам протокол Диффи — Хеллмана с числовым примером, задачи CDH и DDH и их связь с дискретным логарифмом. Далее — выбор параметров: почему нужны безопасные простые, подгруппы простого порядка и стандартные группы, и какие длины рекомендуются. После — атаки: человек посередине, малые подгруппы, Logjam. Завершают тему эфемерный DH с прямой секретностью и схема Эль-Гамаля как обобщение идеи.

Главный вывод, который стоит унести: протокол Диффи — Хеллмана сам по себе не аутентифицирует стороны. Он создаёт общий секрет с тем, кто участвует в обмене, но не отвечает на вопрос «с кем именно». Без аутентификации открытыми ключами (сертификаты, тема 14) или предварительного секрета (PAKE, тема 10) протокол ломается атакой «человек посередине» — и именно эта атака, а не математика, определяет практическую стойкость.

Паспорт темы. Нужно знать: темы 4, 10. Освоите: выполнять DH и объяснять CDH и DDH; выбирать параметры и проверять открытые значения; проводить атаку малых подгрупп и MITM; объяснять прямую секретность; добавлять key confirmation. Проверяет: ЛР 11. Минимум: разделы 1–4. Углубление: разделы 5–6.

Проблема распределения ключей

Квадратичный рост числа ключей

Если n сторон обмениваются данными попарно и каждая пара использует свой ключ, нужно n(n−1)/2 ключей. Для десяти сторон это 45 ключей, для ста — 4950, для тысячи — почти полмиллиона. Каждый ключ нужно хранить, передавать и менять, и каждая сторона должна помнить n−1 ключей.

Рост квадратичный, а не линейный, и это быстро становится неразрешимой задачей: тысяча сотрудников требует полумиллиона секретов, каждый из которых где-то хранится. Отсюда естественная мысль — свести всё к меньшему числу ключей.

Схема ниже показывает рост числа ключей с числом участников.

Центры распределения ключей и их предел

Первый ответ на проблему — центр распределения ключей (англ. key distribution center, KDC). Каждая сторона имеет долговременный ключ с центром, а центр выдаёт сеансовые ключи по запросу. Так устроен Kerberos: клиент получает от центра билет, зашифрованный его долговременным ключом, и предъявляет его сервису.

Число долговременных ключей становится линейным: n вместо n²/2. Но появляется другая проблема: центр знает все ключи и является единой точкой отказа. Его компрометация означает компрометацию всех; его недоступность блокирует все соединения; его честность является предположением, а не гарантией.

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

Идея открытого ключа

Идея Диффи и Хеллмана формулируется так: существуют функции, для которых прямое вычисление легко, а обратное — трудно, причём «трудность» означает отсутствие известного эффективного алгоритма, а не доказанную невозможность.

Первое практическое применение — обмен ключами. Вторая работа — схема RSA (тема 12), опубликованная годом позже и опирающаяся на трудность факторизации. Третья — схема Эль-Гамаля, обобщающая идею на шифрование и подпись.

Почти одновременно и независимо идею обмена ключами по открытому каналу сформулировал Меркл ¹¹; его схема с «загадками» менее практична, но логически предшествует DH. Интересная историческая деталь: в GCHQ (британская служба радиотехнической разведки) та же идея была найдена раньше, в 1969–1974 годах, Джеймсом Эллисом, Клиффордом Коксом и Малькольмом Уильямсоном, но засекречена и опубликована только в 1997 году ². Это не меняет научного приоритета Диффи и Хеллмана — они опубликовали и открыли тему для всех, — но показывает, что криптография с открытым ключом была «в воздухе» и что закрытые исследования в этой области существуют.

Четыре интерфейса криптографии с открытым ключом

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

Различие между PKE и KEM не косметическое. PKE шифрует произвольное сообщение и потому требует дополнения, чтобы быть стойким; KEM порождает ключ фиксированной длины и передаёт только «инкапсуляцию», поэтому проблема дополнения исчезает по построению. Именно поэтому современные схемы — и постквантовые в особенности — формулируются как KEM, а не как PKE.

Различие между DS и AKE тоже важно: подпись аутентифицирует сообщение, но не договаривается о ключе; DH договаривается о ключе, но не аутентифицирует стороны. Протокол, которому нужно и то и другое, комбинирует их — подписанный DH, сертификат и подтверждение ключа.

Протокол Диффи — Хеллмана

Схема

Стороны договариваются об общих параметрах: простом числе p и порождающем элементе g группы (Z/pZ)*. Параметры открыты и могут быть одинаковыми для всех.

Протокол:

1. Алиса выбирает секретное a, вычисляет A = g^a mod p и отправляет A Бобу.
2. Боб выбирает секретное b, вычисляет B = g^b mod p и отправляет B Алисе.
3. Алиса вычисляет K = B^a mod p, Боб — K = A^b mod p.

Оба получают одно и то же: B^a = (g^b)^a = g^(ab) = (g^a)^b = A^b. Противник, перехвативший A и B, знает g, p, g^a и g^b, но не знает a, b и g^(ab).

Схема ниже показывает обмен.

Числовой пример с малыми числами: p = 23, g = 5, a = 6, b = 15. Тогда A = 5^6 mod 23 = 8, B = 5^15 mod 23 = 19. Алиса вычисляет 19^6 mod 23 = 2, Боб — 8^15 mod 23 = 2. Общий секрет равен 2.

def dh_public(g, secret, p):
    return pow(g, secret, p)


def dh_shared(peer_public, secret, p):
    return pow(peer_public, secret, p)

Тот же обмен можно выполнить средствами OpenSSL, не заглядывая в математику: параметры генерируются один раз, ключи создаются из параметров, общий секрет вычисляется командой pkeyutl -derive.

openssl genpkey -genparam -algorithm DH -pkeyopt group:ffdhe2048 -out dhparam.pem
openssl genpkey -paramfile dhparam.pem -out alice.pem
openssl genpkey -paramfile dhparam.pem -out bob.pem
openssl pkey -in alice.pem -pubout -out alice_pub.pem
openssl pkey -in bob.pem -pubout -out bob_pub.pem
openssl pkeyutl -derive -inkey alice.pem -peerkey bob_pub.pem -out alice_secret.bin
openssl pkeyutl -derive -inkey bob.pem -peerkey alice_pub.pem -out bob_secret.bin
cmp alice_secret.bin bob_secret.bin && echo "секреты совпали"

Разумеется, с p = 23 секрет находится перебором мгновенно: g^a mod p можно обратить, перебрав все a от 1 до 22. Реальные параметры — 2048 бит и больше.

CDH и DDH

Формально протокол опирается на две задачи.

Вычислительная задача Диффи — Хеллмана (англ. computational Diffie–Hellman, CDH): по g, g^a, g^b найти g^(ab). Именно её сложность обеспечивает стойкость протокола.

Решающая задача Диффи — Хеллмана (англ. decisional Diffie–Hellman, DDH): по g, g^a, g^b и T определить, верно ли, что T = g^(ab). Эта задача нужна для стойкости схем, где важно не отличить ключ от случайного значения — например, для некоторых AEAD-конструкций и для анализа стойкости протоколов.

Связи: CDH не сложнее DLP (если умеешь логарифмировать, умеешь и CDH), DDH не сложнее CDH (если умеешь вычислять, умеешь и различать). Обратные сведения не известны. В некоторых группах DDH лёгкая, хотя CDH считается трудной, — например, в группах с билинейными спариваниями; поэтому для схем, опирающихся на DDH, выбирают группы без спариваний.

Связь с дискретным логарифмом

Если задача дискретного логарифма решается эффективно, то и CDH, и DDH решаются: противник находит a из g^a и вычисляет g^(ab). Обратное неизвестно: возможно, CDH трудна, даже если DLP в каком-то смысле проще.

Практически это означает, что стойкость DH определяется стойкостью DLP в выбранной группе, и вся тема выбора параметров сводится к выбору группы, где DLP трудна. Тема 4 разобрала методы решения DLP: универсальные (перебор, BSGS, ро Полларда, O(√n)) и специальные для (Z/pZ)* (индексный метод, решето числового поля, субэкспоненциальные). В группе простого порядка q лучшая универсальная атака требует √q операций, поэтому порядок должен иметь большой простой множитель.

Выбор параметров

Безопасные простые и подгруппы

Наивный выбор: взять случайное большое простое p и элемент g. Проблема в том, что порядок g делит p − 1, а p − 1 всегда чётно. Если p − 1 имеет малые множители, элемент g может иметь малый порядок, и тогда секрет находится перебором в маленькой подгруппе — а при гладком p − 1 работает алгоритм Полига — Хеллмана, сводящий задачу к набору маленьких ⁷.

Решение — работать в подгруппе простого порядка q, где q — большой простой делитель p − 1. Типичный способ: безопасное простое p = 2q + 1, где q тоже простое. Тогда p − 1 = 2q, и подгруппы имеют порядки 1, 2, q и 2q. Работая в подгруппе порядка q, мы получаем стойкость √q.

Второй способ — использовать стандартную группу с опубликованными и проверенными параметрами. Это предпочтительнее: генерация безопасного простого в 2048 бит занимает минуты, а проверка чужого p на безопасность требует факторизации p − 1, что для больших чисел невозможно.

Схема ниже показывает структуру подгрупп.

Стандартные группы

Два документа определяют практические параметры. RFC 3526 задаёт модулярные группы MODP с простыми вида p = 2^ℓ − 2^(ℓ−64) − 1 + 2^64·k для длин от 1536 до 8192 бит ³; RFC 7919 задаёт группы ffdhe с безопасными простыми для длин 2048–8192 бит ⁴.

Рекомендуемые длины: 2048 бит как минимум, 3072 бита для 128-битного уровня стойкости. Для 2048-битной группы уровень стойкости около 110–112 бит: лучшая атака — решето числового поля с субэкспоненциальной сложностью, а не √n.

Отдельно стоит запомнить: для эллиптических кривых те же уровни достигаются при 224–256 битах (тема 13), и именно поэтому ECDH вытесняет классический DH в мобильных и встраиваемых применениях. Стандарт X25519 (RFC 7748) задаёт конкретную кривую и порядок работы с ней ⁹.

Проверка открытого значения

Даже при хороших параметрах нужно проверять полученное открытое значение. Атака малых подгрупп (англ. small subgroup attack): противник присылает значение, лежащее в подгруппе малого порядка, и по результату вычисления общего секрета узнаёт остаток секрета по модулю этого порядка. Повторив атаку для нескольких малых порядков и применив китайскую теорему об остатках, он восстанавливает секрет целиком.

Защита: проверять, что 1 < Y < p − 1 и что Y^q ≡ 1 (mod p) для подгруппы порядка q. Для стандартных групп с безопасным простым достаточно проверить, что Y не равно 1, p − 1 и что Y^q ≡ 1.

Стандарт NIST SP 800-56A требует таких проверок явно ⁵. Это не формальность: без проверки протокол ломается, даже если математика группы безупречна.

def check_public(Y, p, q):
    """Проверка открытого значения: 1 < Y < p-1 и Y лежит в подгруппе порядка q."""
    if not (1 < Y < p - 1):
        return False
    return pow(Y, q, p) == 1

Атаки

Человек посередине

Протокол Диффи — Хеллмана без аутентификации ломается тривиально. Противник (Мэллори) встаёт между сторонами:

1. Алиса отправляет A = g^a — Мэллори перехватывает и отправляет Бобу своё M₁ = g^m₁.
2. Боб отправляет B = g^b — Мэллори перехватывает и отправляет Алисе своё M₂ = g^m₂.
3. Алиса вычисляет K₁ = M₂^a, Мэллори знает m₂ и A, поэтому тоже вычисляет K₁.
4. Боб вычисляет K₂ = M₁^b, Мэллори знает m₁ и B, поэтому тоже вычисляет K₂.
5. Мэллори расшифровывает сообщения Алисы ключом K₁, перешифровывает ключом K₂ и передаёт Бобу, и наоборот.

Обе стороны уверены, что общаются друг с другом, хотя весь трафик проходит через противника. Схема ниже показывает атаку.

Защита — аутентификация открытых значений: подпись (темы 12–13), сертификат (тема 14), предварительный общий секрет (PAKE, тема 10). Классическая схема такой аутентификации — подписанный обмен с подтверждением (STS) ¹⁰. Без одного из этих механизмов DH не даёт защищённого канала, а даёт лишь защиту от пассивного наблюдателя.

Важно понимать, что это не «недостаток реализации», а свойство протокола: DH аутентифицирует ключ, но не участников. Формулировка «протокол Диффи — Хеллмана без аутентификации» звучит как оговорка, но на практике означает, что протокол защищает только от того, кто не может вмешаться в канал.

Атака малых подгрупп

Формально атака использует то, что порядок присланного элемента может быть мал. Если противник может подменить A на элемент порядка 2 (то есть p − 1), то общий секрет станет 1 или p − 1, и это раскроет чётность b. Повторив с элементами порядков 3, 5, 7, …, он соберёт остатки b по модулям малых простых и восстановит b по китайской теореме.

Защита — проверка, что присланное значение лежит в правильной подгруппе. Это ровно та проверка, которую требует SP 800-56A.

Logjam и предвычисление

Атака Logjam (2015) показала, что 512-битные и 1024-битные группы DH, широко распространённые в TLS и IPsec, небезопасны ⁶. Две причины.

Первая: 512-битная группа вскрывается за часы на академическом кластере; 1024-битная — за время, доступное крупному противнику. Это следствие субэкспоненциальной сложности решета числового поля: 1024 бита дают уровень около 80 бит, что уже недостаточно.

Вторая, более важная: предвычисление. Решето числового поля имеет две фазы — предвычисление, зависящее только от p, и последующую фазу, зависящую от конкретного g^a. Первая фаза для 1024-битной группы занимает недели на кластере, но выполняется один раз; после этого вскрытие каждого конкретного соединения занимает минуты. Если группа распространена (а стандартные группы используются миллионами серверов), предвычисление окупается.

Отсюда практический вывод: стандартные группы хороши только если они достаточно длинные. 1024 бита — не «слабо», а «сломано для противника с ресурсами». Именно поэтому Logjam привёл к отказу от 1024-битных групп в браузерах и к переходу на 2048 бит и ECDH.

Подтверждение ключа

Из того, что обе стороны вычислили один и тот же общий секрет, не следует, что они знают об этом. Противник может подменить сообщение так, что Алиса и Боб получат разные ключи, и тогда первое же сообщение расшифруется в мусор — но ошибка обнаружится только по содержимому, а не по протоколу. Хуже того, атаки на основе выбора открытого текста могут использовать эту задержку.

Подтверждение ключа (англ. key confirmation) — обмен доказательством, что вторая сторона действительно вывела тот же ключ. Различают явное подтверждение (отдельное сообщение с MAC от известного значения под производным ключом) и неявное (стороны сразу используют ключ, и неверный ключ приводит к провалу аутентификации первого же сообщения).

В TLS 1.3 подтверждение встроено в рукопожатие: сообщение Finished вычисляется как HMAC от транскрипта рукопожатия под ключом, выведенным из общего секрета (тема 15). Если ключи не совпали, Finished не сходится, и соединение обрывается до передачи данных. Схема STS делает то же самое отдельным сообщением.

Практическое правило: DH без подтверждения ключа — это согласование секрета, а не установление защищённого канала. Подтверждение должно покрывать стенограмму обмена, включая параметры и идентификаторы сторон, иначе возможны атаки подмены контекста.

Прямая секретность

Эфемерный DH

Если стороны используют долговременные ключи DH (одна и та же пара a, A для всех сеансов), то компрометация долговременного ключа раскрывает все прошлые сеансы: противник, записавший трафик, может вычислить все общие секреты.

Решение — эфемерный DH (англ. ephemeral Diffie–Hellman, DHE): для каждого сеанса генерируется новая пара. Тогда компрометация долговременного ключа (который теперь используется только для подписи) не раскрывает прошлые сеансы, потому что эфемерные секреты уже уничтожены.

Свойство называется прямой секретностью (англ. forward secrecy). Формально: компрометация долговременных ключей не компрометирует сеансовые ключи прошлых сеансов.

Схема ниже показывает разницу.

Что даёт и чего не даёт

Прямая секретность защищает прошлое, но не будущее: если долговременный ключ скомпрометирован, противник может выдать себя за сторону в новых сеансах (если нет других механизмов). Поэтому в TLS 1.3 используется аутентифицированный эфемерный DH: сертификат подписывает эфемерное значение, а сеансовый ключ вычисляется из эфемерного секрета.

Ограничение: DHE дороже статического DH и требует хорошего генератора случайных чисел. Эфемерные секреты должны генерироваться криптографическим генератором и уничтожаться после использования, иначе свойство теряется.

Выработка ключей из общего секрета

Общий секрет g^(ab) — это элемент группы, а не ключ. Его нельзя использовать напрямую: он может иметь структуру (например, быть квадратичным вычетом), и разные протоколы могут получить одинаковые ключи из разных сеансов.

Правильно — прогнать общий секрет через KDF (тема 10): HKDF с солью и info, задающим контекст. Именно так делают TLS 1.3 и SSH: общий секрет DH подаётся на вход HKDF, а на выходе получаются ключи для каждого направления и каждой цели.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

def derive(shared, salt, label, length=32):
    return HKDF(algorithm=hashes.SHA256(), length=length, salt=salt, info=label) \
        .derive(shared)

k_enc = derive(shared, salt, b"tls13 key")
k_mac = derive(shared, salt, b"tls13 mac")
assert k_enc != k_mac

Это ещё одно применение принципа разделения по назначению: из одного общего секрета выводятся ключи шифрования клиента, шифрования сервера, MAC и так далее.

Схема Эль-Гамаля

Шифрование

Эль-Гамаль (1985) обобщает идею DH на шифрование ⁸. Параметры те же: p, g. Закрытый ключ — x, открытый — y = g^x mod p.

Шифрование сообщения m (представленного элементом группы):

1. Выбрать случайное k.
2. Вычислить c₁ = g^k mod p.
3. Вычислить c₂ = m · y^k mod p.
4. Шифртекст — пара (c₁, c₂).

Расшифрование: m = c₂ · (c₁^x)^(−1) mod p.

Стойкость опирается на CDH: противник знает g^k и y^k = g^(xk), и ему нужно g^(xk). Схема рандомизирована — каждый раз новое k, — поэтому одинаковые сообщения дают разные шифртексты. Ключевое требование: k должен быть уникален для каждого сообщения, иначе схема ломается так же, как поточный шифр при повторе nonce.

Подпись

Та же математика даёт схему подписи (DSA, ГОСТ Р 34.10): подпись — пара чисел, проверяемая через сравнение в группе. Подробно — в теме 13, где разбирается ECDSA на эллиптических кривых; классический DSA устроен аналогично.

Современная замена классического DH на той же идее — X25519: 32-байтные ключи, уровень стойкости около 128 бит, простая и быстрая реализация.

from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey

a = X25519PrivateKey.generate()
b = X25519PrivateKey.generate()
shared_a = a.exchange(b.public_key())
shared_b = b.exchange(a.public_key())
assert shared_a == shared_b

Практическое замечание: Эль-Гамаль и его варианты требуют удвоения длины шифртекста относительно сообщения (два элемента группы вместо одного) и потому вытеснены гибридными схемами, где асимметричный примитив передаёт только ключ, а данные шифруются симметрично.

Итоги темы

Проблема распределения ключей решается криптографией с открытым ключом: обмен Диффи — Хеллмана позволяет выработать общий секрет по открытому каналу, опираясь на трудность дискретного логарифма. Число ключей падает с n²/2 до нуля долговременных секретов, а зависимость от центра распределения ключей ослабевает.

Протокол прост, но требует аккуратности в трёх местах. Параметры: безопасное простое или стандартная группа, подгруппа простого порядка, длина не меньше 2048 бит. Проверка: присланное значение должно лежать в правильной подгруппе, иначе работает атака малых подгрупп. Аутентификация: без подписи или сертификата протокол ломается «человеком посередине».

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

История Logjam показывает, что «стандартная группа» не означает «безопасная»: 1024-битные группы сломаны для противника с ресурсами, а предвычисление делает атаку на конкретное соединение дешёвой. Следующая тема переходит к RSA — второй большой задаче, на которой стоит асимметричная криптография, — и к атакам, которые возникают при неправильном применении.

Литература

1. Diffie W., Hellman M. E. New Directions in Cryptography. — IEEE Transactions on Information Theory, 1976, Т. 22, № 6, С. 644–654. DOI: 10.1109/TIT.1976.1055638
2. Ellis J. H. The Story of Non-Secret Encryption. — GCHQ, 1997 (declassified). https://www.gchq.gov.uk/
3. Koeller E., Koeller K. More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE). — RFC 3526, IETF, 2003. https://www.rfc-editor.org/rfc/rfc3526
4. Gillmor D. Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS). — RFC 7919, IETF, 2016. https://www.rfc-editor.org/rfc/rfc7919
5. NIST. Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. — SP 800-56A Rev. 3, 2018. https://doi.org/10.6028/NIST.SP.800-56Ar3
6. Adrian D., Bhargavan K., Durumeric Z., Gaudry P., Green M., Halderman J. A., Heninger N., Springall D., Thomé E., Valenta L., VanderSloot B., Wustrow E., Zanella-Béguelin S., Zimmermann P. Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. — Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS), 2015, С. 5–17. DOI: 10.1145/2810103.2813707
7. Pohlig S. C., Hellman M. E. An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance. — IEEE Transactions on Information Theory, 1978, Т. 24, № 1, С. 106–110. DOI: 10.1109/TIT.1978.1055817
8. ElGamal T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. — IEEE Transactions on Information Theory, 1985, Т. 31, № 4, С. 469–472. DOI: 10.1109/TIT.1985.1057074
9. Langley A., Hamburg M., Turner S. Elliptic Curves for Security. — RFC 7748, IETF, 2016. https://www.rfc-editor.org/rfc/rfc7748
10. Diffie W., van Oorschot P. C., Wiener M. J. Authentication and Authenticated Key Exchanges. — Designs, Codes and Cryptography, 1992, Т. 2, № 2, С. 107–125. DOI: 10.1007/BF00124891
11. Merkle R. C. Secure Communications over Insecure Channels. — Communications of the ACM, 1978, Т. 21, № 4, С. 294–299. DOI: 10.1145/359460.359473

Дополнительные материалы

Вопросы для самопроверки

1. Почему симметричная криптография не может решить задачу распределения ключей самостоятельно?
2. Как центр распределения ключей сокращает число секретов и какие новые проблемы создаёт?
3. В чём состоит идея криптографии с открытым ключом и почему она не требует защищённого канала?
4. Почему общий секрет DH нельзя использовать как ключ шифрования напрямую?
5. Чем CDH отличается от DDH и почему DDH может быть лёгкой в некоторых группах?
6. Почему стойкость DH определяется наибольшим простым множителем порядка подгруппы?
7. Что такое безопасное простое и зачем нужны стандартные группы?
8. Какие проверки открытого значения обязательны и что произойдёт без них?
9. Как атака малых подгрупп собирает показатель по китайской теореме?
10. Почему атака «человек посередине» не требует решения дискретного логарифма?
11. Что делает аутентифицированный обмен ключами и какие есть варианты аутентификации?
12. Почему предвычисление в Logjam сделало 1024-битные группы небезопасными?
13. Что такое прямая секретность и какие свойства она не даёт?
14. Почему эфемерные ключи нужно уничтожать после сеанса?
15. Чем X25519 удобнее классического DH?

Глоссарий темы

Шпаргалка по инструментам

# параметры и ключи
openssl genpkey -genparam -algorithm DH -pkeyopt group:ffdhe2048 -out dhparam.pem
openssl genpkey -paramfile dhparam.pem -out alice.pem
openssl pkey -in alice.pem -pubout -out alice_pub.pem
openssl pkey -in alice.pem -text -noout          # посмотреть параметры

# общий секрет
openssl pkeyutl -derive -inkey alice.pem -peerkey bob_pub.pem -out a.bin
openssl pkeyutl -derive -inkey bob.pem -peerkey alice_pub.pem -out b.bin
cmp a.bin b.bin && echo ok

# современная замена
openssl genpkey -algorithm X25519 -out x.pem
openssl pkey -in x.pem -pubout -out x_pub.pem

from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes

a, b = X25519PrivateKey.generate(), X25519PrivateKey.generate()
shared = a.exchange(b.public_key())
assert shared == b.exchange(a.public_key())

def derive(shared, info, length=32):
    return HKDF(algorithm=hashes.SHA256(), length=length, salt=None, info=info).derive(shared)

k_enc, k_mac = derive(shared, b"enc"), derive(shared, b"mac")

Типичные ошибки:

Что почитать и посмотреть

• Diffie W., Hellman M. New Directions in Cryptography (1976). Первоисточник. Читается удивительно современно: там есть и обмен ключами, и идея открытого ключа, и обсуждение трудных задач. https://doi.org/10.1109/TIT.1976.1055638
• RFC 7919 (ffdhe). Стандартные группы DH с безопасными простыми и рекомендации по выбору. Полезно понять, какие длины и почему. https://www.rfc-editor.org/rfc/rfc7919
• Adrian D. et al. Imperfect Forward Secrecy (CCS 2015). Logjam: как 1024-битные группы оказались слабыми, и что даёт предвычисление. Одна из самых практичных работ по теме. https://weakdh.org/
• NIST SP 800-56A Rev. 3. Формальные требования к схемам на дискретном логарифме, включая проверки открытых значений и допустимые группы. https://doi.org/10.6028/NIST.SP.800-56Ar3
• Pohlig S., Hellman M. An Improved Algorithm for Computing Logarithms over GF(p) (1978). Алгоритм, который объясняет, почему гладкий порядок опаснее малого. Читается как упражнение по теории чисел.
• RFC 7748 (X25519). Современная замена классического DH: кривая, формат ключей, тестовые векторы. https://www.rfc-editor.org/rfc/rfc7748
• ElGamal T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (1985). Обобщение идеи DH на шифрование и подпись — с кратким и ясным изложением.
• Diffie W., van Oorschot P., Wiener M. Authentication and Authenticated Key Exchanges (1992). Классический разбор того, как аутентифицировать обмен и почему без этого DH ломается. DOI: 10.1007/BF00124891
• weakdh.org. Публичный сайт с результатами исследования Logjam: какие группы были распространены и что рекомендовано делать. Хороший пример «научная работа → практические рекомендации».

Углубление (по желанию)

Почему DH пережил RSA по практичности. RSA дольше считался «главным» алгоритмом с открытым ключом, но в современных протоколах он оставлен только для подписи и шифрования ключа, а сам обмен ключами почти всегда DH или ECDH. Причина в прямой секретности: RSA-шифрование ключа при утечке долговременного ключа раскрывает все записанные сеансы, а эфемерный DH — нет. TLS 1.3 закрепил это на уровне спецификации: в нём нет режимов, где сеансовый ключ передаётся зашифрованным долговременным ключом, — только (EC)DHE.

Стандартные группы и политика. История Logjam показывает, что стандартизация параметров имеет обратную сторону: если все используют одну группу, предвычисление для неё становится выгодным вложением. Поэтому современные подходы (RFC 7919, X25519) сочетают фиксированные, но достаточно длинные группы с возможностью договориться о них в рукопожатии. Для X25519 проблема предвычисления снята иначе: кривая выбрана так, чтобы атаки были только универсальными, а значит предвычисление не даёт выигрыша.

PAKE как ответ на «нет доверия». Если аутентифицировать открытые значения нечем — нет сертификатов, нет предварительного секрета, но есть пароль, — используют PAKE-протоколы. Они одновременно аутентифицируют стороны по паролю и вырабатывают ключ, причём перехваченное рукопожатие не позволяет проверить пароль офлайн. Это закрывает и «человека посередине», и слабость пароля: атакующий вынужден взаимодействовать с сервером, где работает ограничение попыток. Тема 10 упоминает SCRAM и OPAQUE; в контексте DH важно понять, что PAKE — это не «DH с паролем», а другая конструкция с другими гарантиями.

Лабораторная работа 11. Диффи — Хеллман и его атаки

• Раздел курса: тема 11 «Обмен ключами Диффи — Хеллмана и задача дискретного логарифма»

Введение

Тема 11 показала, как две стороны вырабатывают общий секрет по открытому каналу, и почему без аутентификации этот секрет ничего не стоит. Лабораторная работа проходит путь от «DH на бумаге» до атак. Сначала — реализация протокола с проверкой открытых значений и сверка с OpenSSL. Затем — атака «человек посередине» на учебный чат: две стороны обмениваются сообщениями, не подозревая, что между ними стоит противник. Далее — атака малых подгрупп через алгоритм Полига — Хеллмана: восстановление секретного показателя в группе с гладким p − 1. Завершает работу опыт с прямой секретностью: записанный трафик двух сеансов и «утёкший» долговременный ключ.

Работа опирается на темы 4 (теоретико-числовые алгоритмы) и 10 (выработка ключей). Она готовит тему 14: там сертификаты и удостоверяющие центры закроют ровно ту дыру, которую здесь эксплуатирует Мэллори.

Все сетевые опыты выполняются только на 127.0.0.1 (порты 8111 и 8112). Учебные ключи и данные сгенерированы для этой работы; применять эти приёмы против чужих систем запрещено законом.

Цель работы

Реализовать обмен ключами Диффи — Хеллмана с корректной проверкой значений, провести атаку «человек посередине», восстановить секрет алгоритмом Полига — Хеллмана и измерить эффект прямой секретности.

После выполнения работы можно будет:

• реализовать DH в подгруппе простого порядка и сверить общий секрет с OpenSSL;
• объяснить, почему без проверки открытого значения протокол уязвим к атаке малых подгрупп;
• провести атаку «человек посередине» на неаутентифицированный обмен и показать, что обе стороны этого не замечают;
• восстановить секретный показатель алгоритмом Полига — Хеллмана при гладком p − 1;
• вывести ключи из общего секрета через HKDF с разделением по назначению;
• показать на записанном трафике, что эфемерный DH защищает прошлые сеансы при утечке долговременного ключа.

Уровни работы

• Минимум (обязательно): части 1–3. Выполняется без внешней сети, только с пакетами из перечня оснащения.
• Практический уровень: 4–5.
• Углубление (по желанию): нет.

Теоретический минимум

Нужны разделы «Протокол Диффи — Хеллмана», «Выбор параметров», «Атаки» и «Прямая секретность».

DH          A = g^a, B = g^b, K = B^a = A^b = g^(ab)
CDH         по g, g^a, g^b найти g^(ab)
DDH         отличить g^(ab) от случайного элемента
проверка    1 < Y < p−1 и Y^q ≡ 1 (mod p)
стойкость   √q для подгруппы простого порядка q

Команды OpenSSL, которые понадобятся:

openssl genpkey -genparam -algorithm DH -pkeyopt group:ffdhe2048 -out dhparam.pem
openssl genpkey -paramfile dhparam.pem -out alice.pem
openssl genpkey -paramfile dhparam.pem -out bob.pem
openssl pkey -in alice.pem -pubout -out alice_pub.pem
openssl pkey -in bob.pem -pubout -out bob_pub.pem
openssl pkeyutl -derive -inkey alice.pem -peerkey bob_pub.pem -out alice_secret.bin
openssl pkeyutl -derive -inkey bob.pem -peerkey alice_pub.pem -out bob_secret.bin
cmp alice_secret.bin bob_secret.bin && echo "секреты совпали"

Перечень оснащения

• Ubuntu 24.04 (или WSL2), Python 3.10+, cryptography 3.4 или новее, OpenSSL 3.0 или новее. Права root не нужны.
• Архив окружения: lr-env.zip.

Ограничения ресурсов

Стандартная группа RFC 3526 — 2048 бит; атака Полига — Хеллмана выполняется на группе с гладким p − 1 порядка 2^40, где восстановление занимает секунды. Время выполнения не нормируется: проверяются свойства и совпадение с тестовыми векторами, а не абсолютные секунды. Если на конкретной машине шаг занимает заметно больше ожидаемого, это фиксируется в журнале вместе с параметрами оборудования.

Безопасная область эксперимента

Работа выполняется в отдельном каталоге ~/crypto-lab-11; всё необходимое лежит в архиве окружения. Учебные серверы и оракулы слушают только 127.0.0.1. Внешняя сеть не используется.

Порядок выполнения работы

mkdir -p ~/lab11 && cd ~/lab11
unzip /path/to/lr-env.zip
cd lr-env
python3 check_dh.py
python3 check_mitm.py
python3 check_ph.py
python3 check_fs.py

Все проверки запускаются из каталога окружения: сетевая часть открывает порты на 127.0.0.1 и ожидает, что chatlib.py находится рядом.

Часть 1. DH на Python и сверка с OpenSSL

Задание

1. Заполните dh_keypair(p, g, q), dh_shared(peer_y, x, p, q) и validate_public(y, p, q) в заготовке.
2. Проверьте на малых параметрах: p = 23, g = 5, a = 6, b = 15 должны дать A = 8, B = 19, общий секрет 2.
3. Повторите на группе ffdhe2048 из dhlib. Убедитесь, что validate_public отвергает значения 1, p − 1 и элементы вне подгруппы.
4. Сверьте результат с OpenSSL: сгенерируйте параметры и ключи командами из справки, вычислите общий секрет и сравните с Python-результатом.
5. Заполните derive_key(z, p, info): общий секрет должен проходить через HKDF, а не использоваться напрямую.

Что должно получиться

Работающий DH, совпадающий с OpenSSL, и проверка значений, отвергающая опасные элементы. В журнале — ответ на вопрос, почему 1 и p − 1 нельзя принимать как открытые значения.

Часть 2. Атака малых подгрупп

Задание

1. Сгенерируйте (или возьмите готовую) группу с гладким p − 1: например, p = 101, p − 1 = 2²·5².
2. Покажите, что элемент порядка 2 (p − 1) позволяет узнать чётность секрета: если общий секрет равен 1, показатель чётный.
3. Соберите остатки секрета по модулям 2 и 5, применив китайскую теорему об остатках, и восстановите показатель.
4. Сравните с прямым перебором: сколько операций потребовал каждый подход.
5. Объясните, как validate_public блокирует эту атаку.

Что должно получиться

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

Часть 3. Человек посередине

Задание

1. Изучите chatlib.py: протокол обмена сообщениями, сервер Боба и клиент Алисы.
2. Заполните mallory_handshake и relay в mallory_template.py: противник встаёт между сторонами, договаривается об отдельных ключах и перешифровывает трафик.
3. Запустите check_mitm.py: он поднимает Боба, Мэллори и Алису и проверяет, что сообщения доходят в обе стороны.
4. Убедитесь, что ни Алиса, ни Боб не замечают подмены: протокол не аутентифицирует открытые значения.
5. Добавьте в конец обмена сверку «отпечатка» ключа по независимому каналу и покажите, что атака обнаруживается.

Что должно получиться

Работающий противник посередине, через которого проходит весь трафик, и понимание, что защита — аутентификация, а не «более сложный DH». Пункт 5 показывает, как выглядит правильное решение в миниатюре.

Часть 4. Полига — Хеллман

Задание

1. Загрузите ph_data.json: в нём параметры группы с гладким порядком и открытое значение.
2. Заполните crt, dlog_small и pohlig_hellman: решение дискретного логарифма по каждому простому множителю и сборка по китайской теореме.
3. Восстановите секретный показатель и проверьте подстановкой g^x = y.
4. Измерьте время работы и сравните с оценкой Σ √qᵢ — суммой корней из простых множителей.
5. Объясните, почему для группы с порядком 2^40 атака занимает секунды, а для группы с большим простым множителем — нет.

Что должно получиться

Восстановленный показатель, совпадающий с данными варианта, и таблица «множитель — время». Вывод: гладкость порядка опаснее его размера.

Часть 5. Прямая секретность

Задание

1. Изучите traffic.json: записаны два сеанса, в каждом — открытые значения и шифртекст.
2. Изучите bob_longterm_leak.json: «утёкший» долговременный ключ Боба.
3. Заполните attack_session1 и attack_session2 в fs_template.py.
4. Убедитесь, что при статическом DH утечка ключа раскрывает оба сеанса, а при эфемерном — только тот, где использован утёкший ключ (и то не всегда).
5. Сформулируйте, что именно защищает прямая секретность и чего она не защищает.

Что должно получиться

Расшифрованные сообщения (или доказательство, что расшифровать нельзя) и вывод: эфемерные ключи разрывают связь между долговременным ключом и сеансовыми секретами.

Журнал работы

По каждой части: предсказание, команда, результат, объяснение. Для части 3 предсказание — что именно увидит каждая сторона; для части 4 — время работы по оценке Σ √qᵢ; для части 5 — какие сеансы удастся раскрыть. В конце полезно свести таблицу «атака — условие — защита» и проверить, что каждая строка подтверждена опытом.

Критерии проверки

Работа считается выполненной, если:

• проверки check_dh.py, check_mitm.py, check_ph.py и check_fs.py завершаются без ошибок;
• общий секрет совпал у обеих сторон, MITM показан, секретный показатель восстановлен по КТО, утечка долговременного ключа не раскрыла прошлый сеанс;
• измерения и наблюдения записаны в журнал вместе с объяснением расхождений с предсказанием;
• на контрольные вопросы даны ответы своими словами, а не пересказ команд.

Контрольные вопросы

1. Почему число попарных ключей растёт как n(n−1)/2 и как это обходится в DH?
2. Какие задачи CDH и DDH и как они связаны с дискретным логарифмом?
3. Почему для DH нужна подгруппа простого порядка, а не вся группа (Z/pZ)*?
4. Что даёт безопасное простое p = 2q + 1 и какие подгруппы при этом возникают?
5. Как работает атака малых подгрупп и какая проверка её блокирует?
6. Почему аутентификация открытых значений обязательна и какие механизмы её дают?
7. Чем атака Logjam отличается от «просто перебора» и почему предвычисление меняет экономику?
8. Почему 1024-битная группа DH недостаточна, хотя её размер впечатляет?
9. Что такое прямая секретность и в каком сценарии она спасает?
10. Почему общий секрет DH нельзя использовать как ключ напрямую?
11. Как схема Эль-Гамаля обобщает DH и почему она требует уникального k?
12. Почему X25519 предпочтительнее классического DH при том же уровне стойкости?