В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 12. Алгоритм Диффи–Хеллмана Идея протокола DH поистине остроумна. Оказывается, что два человека, взаимодействующие друг с другом по небезопасному каналу общения, могут договориться об использовании секретного ключа таким образом, что оба получат один и тот же ключ, не раскрывая его злоумышленнику, который прослушивает канал общения. 12.1 Группы Если вы читали предыдущую главу, то не удивитесь, узнав, что в алго- ритме Диффи–Хеллмана задействованы простые числа. В этой главе буквой p будет обозначаться большое простое число. Длина p составляет примерно 2000-4000 бит. Большинство вычислений в этой главе выполнены по модулю p , что не всегда будет указано явно. Протокол DH использует Z ∗ p — мульти- пликативную группу по модулю p , которая описана в разделе 11.3.3. Выберем любой элемент группы g и рассмотрим числа 1 , g, g 2 , g 3 , . . . (ра- зумеется, взятые по модулю p ). Это бесконечная последовательность чисел. С другой стороны, количество элементов группы Z ∗ p конечно. (Напомним, что группа Z ∗ p состоит из чисел 1 , . . . , p − 1 , для которых определена опера- ция умножения по модулю p .) По этой причине на каком-то этапе элементы последовательности должны начать повторяться. Предположим, что g i = g j , где i < j . Поскольку мы можем выполнять деление по модулю p , значит, можем поделить каждую сторону этого равенства на g i , в результате чего получим: 1 = g j − i . Другими словами, существует число q := j − i , такое, что g q = 1(mod p ) . Назовем наименьшее положительное число q , для кото- рого выполняется равенство g q = 1(mod p ) , порядком (order) числа g . (К со- жалению, данная тема включает в себя большое количество терминов. Мы предпочитаем использовать стандартную терминологию, а не изобретать соб- ственные слова. В противном случае читатели нашей книги могут запутаться, обратившись к другой литературе.) Последовательно возводя g в степень, мы можем получить числа 1 , g, g 2 , . . . , g q − 1 . После этого элементы последовательности начнут повторяться, так как g q = 1 . Число g называют образующим элементом (generator) и гово- рят, что оно порождает множество 1 , g, g 2 , . . . , g q − 1 . Количество элементов, которое может быть представлено в виде степеней g , в точности равно q , т.е. порядку числа g . Одно из свойств умножения по модулю p таково: существует по крайней мере одно число g , которое может породить все элементы группы Z ∗ p . Другими словами, существует по крайней мере одно g , для которого q = p − 1 . Таким образом, вместо того чтобы рассматривать группу Z ∗ p как множество чисел 1 , . . . , p − 1 , мы можем представить ее и как множество 1 , g, g 2 , . . . , g p − 2 . Число 12.2. Базовый алгоритм Диффи–Хеллмана 231 g , порождающее все элементы группы, называется примитивным элементом (primitive element) группы. Другие значения g могут порождать множества меньших размеров. Об- ратите внимание: если мы перемножим два числа из множества, порожден- ного элементом g , то получим еще одну степень g , а следовательно, еще один элемент этого же множества. Проверив все остальные признаки группы, мы получим, что множество, порожденное элементом g , тоже является группой. Таким образом, мы можем выполнять умножение и деление в этой группе точно так же, как и в большой группе по модулю p . Такие группы, входящие в состав других групп, называются подгруппами (см. раздел 11.3.3). Понятие подгруппы очень важно для осуществления атак на криптосистемы. Осталось рассмотреть еще одно важное утверждение. Для любого элемен- та g порядок g является делителем числа p − 1 . Это легко показать. Пусть g — это примитивный элемент группы, а h — какой-нибудь другой элемент. По- скольку g порождает всю группу, существует такое x , что h = g x . Теперь рас- смотрим элементы множества, порожденного h . Это элементы 1 , h, h 2 , h 3 , . . . , которые равны элементам 1 , g x , g 2 x , g 3 x , . . . соответственно. (Напомним, что все наши вычисления проводятся по модулю p .) Порядок h — это наимень- шее число q , для которого h q = 1 . Другими словами, это наименьшее чис- ло q , для которого g xq = 1 . Для любого t значение g t = 1 тогда и только тогда, когда t = 0(mod p − 1) . Таким образом, порядок h — это наимень- шее число q , для которого xq = 0(mod p − 1) . Это выполняется тогда, когда q = ( p − 1) / НОД ( x, p − 1) . Отсюда очевидно, что q является делителем p − 1 . Вот небольшой пример. Пусть p = 7 . Число g = 3 является примитивным элементом, потому что 1 , g, g 2 , . . . , g 5 = 1 , 3 , 2 , 6 , 4 , 5 . (Напомним, что все вы- числения выполняются по модулю p .) Элемент h = 2 порождает подгруппу 1 , h, h 2 = 1 , 2 , 4 , так как h 3 = 2 3 mod 7 = 1 . Элемент h = 6 порождает под- группу 1 , 6 . Размеры этих подгрупп равны 3 и 2 соответственно. Очевидно, оба этих числа являются делителями p − 1 . Приведенное утверждение частично объясняет тест Ферма, который упо- минался в разделе 11.4.1. Тест Ферма основан на том, что для любого a справедливо отношение a p − 1 = 1 . Это легко проверить. Пусть g — это при- митивный элемент группы Z ∗ p . Возьмем x , такое, что g x = a . Поскольку g порождает всю группу, такое x будет существовать для любого a . Но тогда a p − 1 = g x ( p − 1) = ( g p − 1 ) x = 1 x = 1 . 12.2 Базовый алгоритм Диффи–Хеллмана Первоначальная версия протокола DH выглядела следующим образом. Мы выбираем большое простое число p и примитивный элемент g , который |