В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 12. Алгоритм Диффи–Хеллмана размера d . Если мы хотим, чтобы в группе не было подгрупп малых размеров, следует избегать чисел p − 1 , имеющих малые делители. Проблема заключается вот в чем. Если p — это большое простое число, тогда p − 1 всегда будет четным, а значит, будет делиться на 2. Таким образом, у нас всегда будет присутствовать подгруппа, состоящая из двух элементов: 1 и p − 1 . Тем не менее, за исключением этой подгруппы, можно избежать наличия других подгрупп малых размеров, требуя, чтобы число p − 1 не имело других малых делителей. 12.5 Надежные простые числа Наше решение состоит в том, чтобы использовать в качестве p надежное простое число (safe prime) . Это достаточно большое простое число вида 2 q +1 , где q — также простое число. В этом случае мультипликативная группа Z ∗ p будет иметь следующие подгруппы: • тривиальная подгруппа, состоящая только из числа 1; • подгруппа размером 2, состоящая из элементов 1 и p − 1 ; • подгруппа размером q ; • подгруппа размером 2 q . Первые две подгруппы тривиальны, и справиться с ними совсем неслож- но. Третья — это и есть та группа, которую мы хотим использовать в схеме Диффи–Хеллмана. Последняя подгруппа, которая и является полной груп- пой Z ∗ p , обладает одним существенным недостатком. Рассмотрим множество всех чисел по модулю p , которые являются квадратом какого-нибудь друго- го числа (разумеется, по модулю p ). Оказывается, что половина всех чисел 1 , . . . , p − 1 являются квадратами, а половина — не являются. Любой прими- тивный элемент, порождающий всю группу, не может быть квадратом. (Если бы он был квадратом, тогда возведение этого числа в степень всегда давало бы квадрат, а значит, мы бы никогда не смогли породить элементы группы, которые не являются квадратами.) В математике существует функция, называемая символом Лежандра (Legendre symbol). Она позволяет определить, является ли число по моду- лю p квадратом, не находя самого квадратного корня. Существуют эффек- тивные алгоритмы для вычисления символа Лежандра. Таким образом, ес- ли образующий элемент g не является квадратом и мы посылаем g x , тогда любой наблюдатель (например, злоумышленник Е) сразу же сможет опреде- лить, что за число x — четное или нечетное. Если x четное, тогда g x являет- ся квадратом. Если x нечетное, тогда g x не является квадратом. Поскольку злоумышленник Е может использовать символ Лежандра, чтобы определить, 12.6. Использование подгрупп меньшего размера 237 является ли число квадратом, он может узнать, что за число x — четное или нечетное. Перед нами случай исключительного поведения: злоумышленник Е не может узнать значение x , за исключением наименее значимого бита. Что- бы избежать этой проблемы, необходимо использовать только квадраты по модулю p . Последние и образуют ту самую подгруппу порядка q . Еще од- но замечательное свойство состоит в том, что q — простое число, а значит, вложенных подгрупп у нас не будет. Вот как использовать надежное простое число. Выберите пару ( p, q ) , та- кую, что p = 2 q + 1 и оба числа p и q являются простыми. (Для этого можно воспользоваться функцией isPrime и методом проб и ошибок.) Выберите случайное число α в диапазоне 2 , . . . , p − 2 и установите g = α 2 (mod p ) . Убе- дитесь, что g 6 = 1 и g 6 = p − 1 . (Если g будет равно одному из этих запрещен- ных значений, выберите другое α и повторите попытку.) Полученный набор параметров ( p, q, g ) вполне годится для использования в протоколе Диффи– Хеллмана. Каждый раз, когда пользователь А (или Б) получает значение, которое, как предполагается, является степенью g , он должен проверить, действитель- но ли полученное значение попадает в подгруппу, порожденную числом g . Ес- ли вы используете надежное простое число так, как было описано выше, для проверки членства в подгруппе можно воспользоваться символом Лежанд- ра. Существует также более простой, хотя и более медленный метод. Число r является квадратом тогда и только тогда, когда r q = 1(mod p ) . Мы также рекомендуем запретить использование числа 1, потому что оно всегда при- водит к проблемам. Тогда окончательный вариант условия будет выглядеть следующим образом: r 6 = 1 ∧ r q mod p = 1 . 12.6 Использование подгрупп меньшего размера Недостаток использования метода надежных простых чисел — низкая эф- фективность. Если длина простого числа p равна n бит, тогда длина q равна n − 1 бит, а значит, все показатели степеней будут иметь длину n − 1 бит. Сред- няя операция возведения в степень будет включать в себя около 3 n/ 2 умно- жений по модулю p . Для больших чисел p такой объем работы выглядит достаточно громоздким. Стандартным решением этой проблемы является использование подгрупп меньшего размера. Вот как это делается. Вначале в качестве q выбирается 256-битовое простое число. (Другими словами, 2 255 < q < 2 256 .) Затем необ- ходимо найти намного большее простое число p , такое, что p = N q + 1 для некоторого произвольного N . Для этого выберем случайное число N из под- ходящего диапазона, вычислим значение p как N q + 1 и проверим, является |