В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 12. Алгоритм Диффи–Хеллмана g x g y x R p * Пользователь А y R p * Пользователь Б g y x ( ) k g x y ( ) k Рис. 12.1. Первоначальная версия протокола Диффи–Хеллмана порождает всю группу Z ∗ p . И p и g являются открытыми константами этого протокола, поэтому предполагается, что они известны всем участникам об- щения, включая и злоумышленников. Схема обмена ключами приведена на рис. 12.1. Это один из общепринятых способов схематического изображения криптографических протоколов. У нас есть два участника: пользователь А и пользователь Б. Шкала времени направлена сверху вниз. Вначале поль- зователь А выбирает случайное число x из множества Z ∗ p , что эквивалентно выбору случайного числа из диапазона 1 , . . . , p − 1 . Пользователь А вычисля- ет g x mod p и отсылает результат пользователю Б, который, в свою очередь, выбирает из множества Z ∗ p случайное число y . Он вычисляет g y mod p и отсы- лает результат пользователю А. Окончательное значение секретного ключа выглядит как g xy . Пользователь А может вычислить это значение, возведя число g y , полученное от пользователя Б, в известную ему степень x . (Еще раз вспомним школьный курс математики: ( g y ) x = g xy .) Аналогичным образом пользователь Б может вычислить значение ключа k как ( g x ) y . Оба пользова- теля получат одно и то же значение k , которое может применяться в качестве секретного ключа. А что же наш злоумышленник? Он может перехватить значения g x и g y , но не знает x или y . Задача вычисления g xy по заданным g x и g y известна как проблема Диффи–Хеллмана (сокращенно DH). Если числа p и g вы- браны должным образом, тогда эффективного алгоритма вычисления g xy не существует, по крайней мере нам таковой не известен. Наилучший из суще- ствующих методов состоит в том, чтобы вначале вычислить x по известному g x , после чего подсчитать значение k как ( g y ) x — именно так, как это делает пользователь А. На множестве действительных чисел вычисление x по задан- ному g x называется функцией логарифма. Ее можно найти на любом инже- нерном калькуляторе. В конечном поле Z ∗ p эта функция называется дискрет- ным логарифмом (discrete logarithm) . В общем случае задача вычисления x по заданному g x над конечной группой известна как проблема дискретного логарифма, или DL. 12.3. Атака посредника 233 Первоначальная версия протокола DH имеет множество способов приме- нения. Мы рассмотрели ее на примере обмена сообщениями между двумя участниками. Еще один возможный вариант — обратиться к каждому по- тенциальному участнику общения с просьбой выбрать случайное x и опуб- ликовать свое значение g x mod p в цифровом эквиваленте телефонной кни- ги. Теперь, если пользователь А захочет пообщаться с пользователем Б, он находит в телефонной книге значение g y и подсчитывает g xy для своего x . Пользователь Б может точно так же подсчитать значение g xy без какого-ли- бо предварительного взаимодействия с пользователем А. Такую схему удоб- но использовать в окружениях наподобие системы электронной почты, где участники общения не взаимодействуют напрямую. 12.3 Атака посредника К сожалению, базовый протокол Диффи–Хеллмана не защищен от так называемой атаки посредника (man-in-the-middle attack) . Давайте еще раз взглянем на протокол. Пользователь А знает, что он с кем-то общается, но не знает, с кем именно. Злоумышленник Е может вклиниться в протокол, имитируя пользователя Б при общении с пользователем А, а также имити- руя пользователя А при общении с пользователем Б. Схема этого процес- са приведена на рис. 12.2. Для пользователя А данный протокол выглядит точно так же, как настоящий протокол Диффи–Хеллмана. Пользователь А никак не сможет определить, что он общается со злоумышленником Е, а не с пользователем Б. Это же справедливо и по отношению к пользователю Б. Злоумышленник Е сможет поддерживать видимость такого общения столько, сколько захочет. Представим себе, что пользователи А и Б начали общаться друг с другом, используя секретный ключ, который, как им кажется, они выбрали вдвоем. Все, что требуется от злоумышленника Е, — это послушно пересылать сообщения, отправленные пользователем А пользователю Б и на- оборот. Разумеется, злоумышленник Е должен расшифровывать сообщения, полученные от пользователя А, который зашифровал их с помощью ключа k , а затем заново зашифровывать эти сообщения с помощью ключа k 0 , чтобы отослать пользователю Б. Аналогичные операции нужно проделывать и над трафиком, идущим в другом направлении, однако больших усилий это не потребует. Осуществить атаку посредника на цифровую телефонную книгу гораздо сложнее. Если лицо, опубликовавшее телефонную книгу, проверяет личность каждого человека, который присылает свое значение g x , пользователь А мо- жет быть уверен в том, что он использует значение g x пользователя Б. Позд- |