Введение в современную криптографию
Часть элементов, которые являются генераторами
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Конкретные примеры Zp*.
- Ссылки и дополнительная литература
| Часть элементов, которые являются генераторами. Как показано в теоре-
ме B.16, часть элементов группы G порядка q, которые являются генераторами, это φ(q)/q. Теорема B.15 гласит, что φ(q)/q = Ω(1/||q||). Доля элементов, которые являют- ся генераторами, таким образом, достаточно высока, чтобы обеспечить, что отбор полиномиального количества элементов из группы даст генератор с практически пренебрежимо малой вероятностью. (Анализ тот же самый, как и в разделе B.2.5). Конкретные примеры Zp*. Сопоставив все, мы видим, что существует эффектив- ный вероятностный алгоритм для нахождения генератора группы G до тех пор, пока факторизация порядка группы известна. Поэтому, при выборе группы для крипто- графических приложений важно, чтобы группа выбиралась таким образом, чтобы это было справедливым. Это опять же объясняет предпочтение, которое подробно обсуж- далось в разделе 8.3.2, для работы в соответствующей подгруппе Zp* порядка простого числа. Другая возможность заключается в том, чтобы использовать G = Zp* для p сильного p pпростого числа (т.е., p = 2q +1 при q также простом), и в этом случае про- стые множители группового порядка p − 1 известны. Одна последняя возможность за- ключается в том, чтобы генерировать простое число p таким образом, что факторизация p − 1 известна. Дальнейшие подробности выходят за пределы данной книги. Ссылки и дополнительная литература Книгу Шоупа (Shoup) настоятельно рекомендуем тем, кто стремится изучить темы этой главы более подробно. В частности, ограничения на φ(N )/N (и асим- птотическую версию теоремы B.15) можно найти в [159, глава 5]. Ханкерсон и др. (Hankerson et al.) [83] также предоставляют обширные подробности о реали- зации теоретико-числовых алгоритмов для криптографии. Упражнения Докажите корректность расширенного алгоритма Эвклида. Докажите, что расширенный алгоритм Эвклида работает в течение полино- миального времени, на длине его входных данных. Подсказка: Сначала докажем предположение, аналогичное пред- положению B.8. Покажите, как определить, что n-битная строка находится в ZN* в течение полиномиального времени. |