Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 114

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 108 109 110 111 112 113 < 114 > 115 116 117 118 119 120 .. 311 >> Следующая

300
Часть III. Основные методы криптографии
полиномиальных, или эффективных, алгоритмов входят и рандомизированные алгоритмы (см. определение 4.6 в разделе 4.4.6).
2. Число к в обоих формулировках называется параметром безопасности (security parameter), a XG(lk) — случайный вариант конечного поля и элементов. Изучая вероятностное генерирование простых чисел (раздел 4.4.6.1) и конструкцию поля (раздел 5.4), мы убедились, что вариант XQ(lk) дей-, ствительно можно решить за время, полиномиально зависящее от числа к. Считается общепризнанным, что число к = 1024 является нижней гра-нщей параметра безопасности для задачи дискретного логарифмирования в конечных полях. Эта нижняя граница установлена, исходя из существо-\ вания субэкспоненциального алгоритма решения этой задачи (индексное^ исчисление). Определением субэкспоненциальной сложности является вы-* ражение (8.4.2). Для числа \q\ = 1024 это выражение равно 280. По этой причине в качестве нижней границы используется число к = 1024. Текил! образом, выражение "для всех достаточно больших чисел к " означает, что\ числа к больше 1024.
3. Предположение о невозможности дискретного логарифмирования означает, что функция
<f:Z9~F* (8.4.1)
является однонаправленной. Считается, что это условие действительно* выполняется (описание гипотезы V ф NV см. в разделе 4.5), т.е. однона-\ правленная функция существует.
4. В настоящее время неизвестно, является ли функция (8.4.1) функцией с сек-* ретом (см. свойство 8.1 в разделе 8.1). Иначе говоря, никому не удалось внедрить в эту функцию секретную информацию, позволяющую эффективно вычислить обратную функцию (т.е. разработать эффективный методе позволяющий по числу 0х найти число х, используя секретную информаА цию). Однако, если эта функция использует составные модули (оставался однонаправленной), она становится функцией с секретом, в которой ролл секрета играет разложение модуля на простые множители. Технически! детали читатели найдут в книгах [224, 228, 229]. ?
Сформулированные выше предположения, по сути, означают, что "не существует полиномиальных по параметру к алгоритмов решения этих задач". Однако! к этому утверждению следует относиться с большой осторожностью. Если поли^ номиальный алгоритм poly(fc) существует, его время работы не превышает кп, гда п — некоторое целое число. С другой стороны, известно, что существует субэкс-1 поненциальный алгоритм дискретного логарифмирования, время работы которого^ определяется выражением
sub_exp(g) = exp(c(log9)1/3(log log qf'\ (8.4.2)
Глава 8. Шифрование — асимметричные методы
301
где с — небольшая константа (например, с < 2). Сравнивая выражения "не существует полиномиального алгоритма дискретного логарифмирования poly(fc)" и "существует субэкспоненциальный алгоритм дискретного логарфми-рования subexp(g)", приходим к выводу, что число кп чрезвычайно мало по сравнению с числом sub_exp(fc log 2) (если к = \q\ = log2g, то q = к log 2). Однако выражение "чрезвычайно мало" оказывается истинным, только если число тг фиксировано, а число к (будучи функцией числа п) — достаточно велико. Разберемся в этом подробнее.
Допустим, что число к не является достаточно большим. Возьмем натуральный логарифм от выражений poly (А;) и sub_exp(fc log 2) и сравним полученные результаты:
n(logfc)1/3 нс'к1'3,
где d = c(log2)1/3 < с. Теперь ясно, что, если число п сравнимо с числом dk1!3, субэкспоненциальный алгоритм дискретного логарифмирования работает быстрее, чем гипотетически "несуществующий полиномиальный алгоритм". Выражение "не существует полиномиального алгоритма дискретного логарифмирования poly(fc)" приобретает реальный смысл, только если число к не ограничено (и, следовательно, может быть "достаточно большим", если число п фиксировано). В действительности число к не может быть неограниченным. В частности, при к = 1024 (общепринятая нижняя граница параметра безопасности) и с < 2 существует полиномиальный алгоритм дискретного логарифмирования poly(fc), время работы которого является полиномом 9-й степени от параметра к (см. пример 8.4).
До сих пор мы использовали асимптотическую интерпретацию выражения "не существует полиномиального алгоритма дискретного логарифмирования poly(fc)": число к считалось неограниченным и достаточно большим. В действительности число к должно быть ограничено, а значит, алгоритм poly(fc) существует. Несмотря на это, можно установить настолько большую границу для числа к, что полиномиальный алгоритм будет работать немыслимо долго. Считается, что число к = 1024 вполне удовлетворяет этому условию.
В остальной части книги будет использоваться именно асимптотическое толкование выражения "не существует полиномиального алгоритма решения poly(fc)".
В заключение рассмотрим взаимосвязь между вычислительной проблемой Диффи-Хеллмана и задачей дискретного логарифмирования.
Заметим, что доступность чисел а = log5 g\ или b = logfl g2 позволяет найти числа
аЬ Ь „Ь
9 =9i= 92-
Иначе говоря, если существует эффективный алгоритм, решающий вычислительную проблему Диффи-Хеллмана, значит, существует эффективный алгоритм дискретного логарифмирования. Следовательно, если не выполняются условия невоз-
Предыдущая << 1 .. 108 109 110 111 112 113 < 114 > 115 116 117 118 119 120 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed