В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 12. Алгоритм Диффи–Хеллмана Пользователь А Пользователь Б Злоумышленник Е g x g v x R p * y R p * v R p * w R p * g y g w k ( ) g w x k ( ) g x y ( ) g y v k' ( ) g v y k' Рис. 12.2. Атака посредника на протокол Диффи–Хеллмана нее, когда речь пойдет о цифровых подписях и инфраструктуре открытого ключа, будут описаны и другие способы защиты от атаки посредника. Существует одно окружение, которое позволяет противостоять атаке по- средника без внедрения какой-либо дополнительной инфраструктуры. Если ключ k применяется для шифрования телефонных разговоров или видео- связи, пользователь А может поговорить с пользователем Б и узнать его по голосу. Пусть h — это некоторая функция хэширования. Если пользова- тель Б прочитает пользователю А несколько первых разрядов значения h ( k ) , пользователь А сможет проверить, действительно ли он использует тот же секретный ключ, что и пользователь Б. Данное решение приносит хорошие результаты, однако только в тех ситуациях, когда знание ключа k можно связать с реальным человеком, находящимся “по ту сторону общения”. Одна- ко большинство компьютерных коммуникаций не предоставляют такой воз- можности. Кроме того, злоумышленник Е может создать синтезатор речи, имитирующий голос пользователя Б. И наконец, самый большой недостаток этого решения — необходимость соблюдения пользователями строгой дисци- плины. Но, как известно, пользователи сплошь и рядом игнорируют правила безопасности. 12.4. “Подводные камни” реализации 235 12.4 “Подводные камни” реализации Реализация протокола DH может таить в себе массу подвохов. Например, если злоумышленник Е вмешивается в общение и заменяет оба числа g x и g y единицей, у пользователей А и Б оказывается ключ k = 1 . В результате мы получаем протокол согласования ключей, который безупречен во всем, кроме одного: злоумышленник Е знает секретный ключ. Это, конечно же, очень плохо, а значит, нам нужно каким-либо образом предотвратить подобную атаку. Еще одна распространенная проблема возникает тогда, когда образую- щий элемент g не является примитивным элементом группы Z ∗ p , а порож- дает лишь небольшую подгруппу. Пусть порядок g равен одному миллиону. В этом случае множество © 1 , g, g 2 , . . . , g q − 1 ª содержит лишь миллион элемен- тов. Поскольку в этом множестве оказывается и ключ k , злоумышленник Е сможет легко перебрать все варианты в поисках подходящего ключа. Оче- видно, одно из требований состоит в том, чтобы у числа g был более высокий порядок. Но кто выбирает p и g ? Все пользователи работают с одними и теми же значениями p и g , поэтому большинство из них получают эти значения от кого-нибудь другого. Для обеспечения безопасности общения они должны убедиться в том, что значения p и g выбраны правильно. Каждый из пользо- вателей А и Б должен проверить, что p является простым числом и что g — это примитивный элемент группы по модулю p . Отдельную проблему образуют подгруппы по модулю p . Пользователь Б может легко распознать атаку злоумышленника Е, заменившего g x на 1; для этого достаточно лишь проверить соответствующее число. Но злоумышлен- ник Е может заменить g x числом h , имеющим низкий порядок. В этом случае ключ, сгенерированный пользователем Б, будет принадлежать множеству, порожденному элементом h . Поскольку количество элементов этого множе- ства невелико, злоумышленник Е сможет легко перебрать все значения, что- бы найти k . (Разумеется, эта же атака может быть осуществлена и по отно- шению к пользователю А.) По этой причине пользователям А и Б необходимо проверять, не порождают ли полученные ими числа подгрупп с малым коли- чеством элементов. Давайте еще раз взглянем на подгруппы. При работе по модулю просто- го числа все (мультипликативные) подгруппы могут быть порождены одним элементом. Вся группа Z ∗ p состоит из элементов 1 , . . . , p − 1 . Каждая подгруп- па может быть представлена в виде 1 , h, h 2 , h 3 , . . . , h q − 1 , где h — некоторый элемент группы Z ∗ p , а q — порядок h . Как уже отмечалось, оказывается, что q должно быть делителем p − 1 . Другими словами, размер любой подгруп- пы должен быть делителем p − 1 . Справедливо и обратное утверждение: для любого числа d , являющегося делителем p − 1 , существует одна подгруппа |