Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
РЕЗУЛЬТАТ:
Элемент группы F*, разделенный между Алисой и Бобом.
1. Алиса генерирует элемент а € f/[l,p — 1), вычисляет число да <— Q°(modp)| и посылает его Бобу.
2. Боб генерирует элемент b е i/[l,p — 1)> вычисляет число дь <— gb(modpJ и посылает его Алисе.
3. Алиса вычисляет значение к <— g^(modp).
4. Боб вычисляет число к <— g„(modp).
Глава 8. Шифрование — асимметричные методы
295
Из протокола 8.1 легко видеть, что значение, вычисляемое Алисой, равно
к = дЬа(то&Р), а значение, вычисляемое Бобом, —
fc = gab(modp).
Заметим, что, поскольку ab = ba(modp — 1), обе стороны вычисляют одно и то же значение. Это обеспечивает разделение ключа между двумя сторонами. Таким образом, числа р и д можно разослать всем участникам системы.
Пример 8.1. Допустим, что р = 43. Применяя алгоритм 5.1, находим, что число 3 является первообразным корнем по модулю 43. Распределим между Алисой и Бобом открытую пару (р, д) = (43,3). Для того чтобы обменяться секретными ключами, Алиса генерирует случайную секретную степень, равную 8, и посылает Бобу число 38=25(mod43). Боб генерирует секретное число 37 и посылает Алисе число З37 = 20(mod43). Секретный ключ, согласованный Алисой и Бобом, равен
9 = 208 = 2537(mod43). п
Описание протокола Диффи-Хеллмана следует дополнить следующими замечаниями.
• Простое число р следует выбирать так, чтобы число р — 1 имело достаточно большой простой множитель р'. Слова "достаточно большой" означают, что pi > 2160 Необходимость этого условия обсуждается в разделе 8.4.
• Число д не обязано быть порождающим элементом группы F*. Необходимо лишь, чтобы оно было порождающим элементом ее подгруппы, имеющей достаточно большой порядок, например, подгруппы порядка р'. В этом случае Алиса и Боб должны проверить условия д ф 1 и др = l(raodp). По этой причине число р' должно быть частью общих исходных данных.
• Алиса (соответственно Боб) должна проверить условие ф 1 (соответственно да ф 1). Это условие гарантирует, что для выбранной ею степени, принадлежащей интервалу (1,р'), разделенный ключ gab будет элементом подгруппы порядка р' группы ?р, т.е. элементом достаточно большой подгруппы.
• По окончании протокола Алиса (соответственно Боб) должна стереть свою степень а (соответственно степень о). Этим они обеспечивают заблаговременную секретность (forward secrecy) ключа даЬ. Это свойство обсуждается в разделах 8.15 и 11.6.1.
296
Часть III. Основные методы криптографии
8.3.1 Атака "человек посередине"
Следует иметь в виду, что протокол обмена ключами Диффи-Хеллмана не обеспечивает аутентичности согласованного ключа. Активный противник, внед-
Атака 8.1. Атака "человек посередине" на протокол обмена ключами Диффи-Хеллмана
ОБЩИЕ ИСХОДНЫЕ ДАННЫЕ: Как в протоколе 8.1.
1. Алиса генерирует элемент а€ гу [1,р—1), вычисляет значение ga <— <r°(modp)i и посылает его Злоумышленнику ("Бобу").
Г. Злоумышленник ("Боб") вычисляет значение дт <— gm(modp), где т € € [1,р — 1) и посылает его Бобу
2. Боб генерирует элемент Ь € г/[1,р — 1), вычисляет значение дь <— <7b(modp)< и посылает его Злоумышленнику ("Алисе").
2'. Злоумышленник ("Алиса") посылает Алисе число дт.
3. Алиса вычисляет значение fci <— g^(modp). (* Этот ключ распределен между Алисой и Злоумышленником, поскольку Злоумышленник может вы-1 числить значение ki <— g™(modp). *)
4. Боб вычисляет значение к2 *— g^(modp). (* Этот ключ распределен между! Бобом и Злоумышленником, поскольку Злоумышленник может вычислить! значение к2 <— gj^(modp). *)
Глава 8. Шифрование — асимметричные методы
297
ренный в канал связи между Алисой и Бобом, может манипулировать сообщениями протокола и начать атаку "человек посередине" (man-in-the-middle attack).
В ходе этой атаки Злоумышленник перехватывает и блокирует первое сообщение Алисы Бобу, т.е. число да, маскируется под Алису и посылает Бобу следующее сообщение.
(Напоминаем соглашения, принятые в разделе 2.6.2.) Боб, следуя инструкциям протокола, возвращает Злоумышленнику ("Алисе") число дь- Это число снова перехватывается и блокируется Злоумышленником. Теперь Злоумышленник и Боб согласовали между собой ключ g6m(modp), хотя Боб считает, что он разделил этот ключ с Алисой.
Аналогично Злоумышленник, имитируя Боба, может согласовать другой ключ с Алисой (т.е. число gam(modp)). Впоследствии Злоумышленник может использовать оба ключа для чтения и подмены "секретных" сообщений, которыми обмениваются Алиса и Боб, или поочередно имитировать этих пользователей.
Атака на протокол обмена ключами Диффи-Хеллмана вполне реальна, поскольку этот протокол не предусматривает проверки аутентичности источника сообщений. Для того чтобы ключи были согласованы только между Алисой и Бобом, обе стороны должны быть уверены друг в друге. Способы аутентификации рассматриваются в главе 11. В этой же главе (раздел 11.6) описан метод безопасного применения протокола обмена ключами Диффи-Хеллмана.
Стойкость разделенного ключа в протоколе Диффи-Хеллмана обеспечивается вычислением значенияе ga6(modp) по заданным числам да и дь. Эта задача называется вычислительной проблемой Диффи-Хеллмана (CDH problem — Diffie-Hellman problem).