Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
302
Часть III. Основные методы криптографии
можности дискретного логарифмирования, то не выполняются и условия неразрешимости вычислительной проблемы Диффи-Хеллмана. Таким образом, вычис-1 лительная проблема Диффи-Хеллмана проще задачи дискретного логарифмиро-| вания, т.е. условия неразрешимости вычислительной проблемы Диффи-Хеллмана^ строже, чем условия неразрешимости задачи дискретного логарифмирования. Об4 ратное утверждение еще не доказано.
Могут ли выполняться условия невозможности дискретного логарифмирования, если условия о неразрешимости вычислительной проблемы Диффи-Хеллмана не выполняются?
Маурер (Maurer) и Вольф (Wolf) привели убедительные эвристические аргументы, обосновывающие взаимозависимость этих задач. Они считают весьма вероятным, что эти две задачи эквивалентны [190].
8.4.1 Произвольность вариантов и условия неразрешимости
Следует подчеркнуть, что в условиях невозможности дискретного логарифмирования варианты должны быть произвольными. Рассмотрим группу F*, где р —4 простое число, состоящее из к бит, и попробуем найти число а, удовлетворяющее условию h -= ga(modp).
Известно, что число а является элементом поля Zp_i. Если р — 1 = q\q2 ...<#, где каждый множитель мал (т.е. не превосходит полином от параметра к при г = 1,2, ...,?), то задача дискретного логарифмирования сводится к вычисленики значений щ = a(raodqi) по числам /i(p-1^ei(modp), только теперь числа сц ый-i лы и могут быть найдены за полиномиальное время, зависящее от параметра к. После определения чисел а\, а2,..., ае число а находится по китайской теореме об остатках (теорема 6.7). Эта идея лежит в основе полиномиального алгоритм ма Полига (Pohlig) и Хеллмана [231], позволяющего решить задачу дискретного! логарифмирования при условии, что число р — 1 не имеет большого простого^ множителя. Очевидно, что если каждый простой множитель числа р — 1 огран ничен полиномом, зависящим от параметра к, то время выполнения алгоритма Полига-Хеллмана полиномиально зависит от параметра к.
Простое число р, такое что число р — 1 не имеет большого простого множителя, называется гладким (smooth prime). Правда, иногда в этом же смысле употребляется выражение "число р — 1 является гладким". Стандартный способ избежать гладких простых чисел заключается в конструировании такого простого числа р, чтобы р — 1 делилось на другое большое простое число р'. По теореме 5.2.2 циклическая группа W* содержит единственную подгруппу, имеющую порядок р'. Если число р' сделать открытым, пользователи протокола обмена ключами Диффи-Хеллмана могут быть уверенными в том, что этот протокол ра-
Глава 8. Шифрование — асимметричные методы
303
ботает в этой большой подгруппе. Все что нужно для этого — найти элемент д&?*, удовлетворяющий условию
gte-V/p'?Цтоо\р).
Элемент д порождает группу, имеющую простой порядок р'. В качестве общих исходных данных протокол обмена ключами Диффи-Хеллмана должен использовать числа (р,р',д), удовлетворяющие указанным выше свойствам. Считается, что размер простого числа р' должен быть не меньше 160 бит, т.е. р' > 2160 (см. раздел 10.4.8.1).
Проблема Диффи-Хеллмана и задача дискретного логарифмирования считаются неразрешимыми в конечной абелевой группе большого порядка, например, в подгруппе конечного поля, имеющей большой простой порядок, или в группе точек эллиптической кривой, определенной над конечным полем (конструкция групп рассматривается в разделе 5.5, а задача дискретного логарифмирования на эллиптических кривых — в разделе 5.5.3). Таким образом, протокол обмена ключами Диффи-Хеллмана правильно работает в этих группах.
Существует несколько эффективных субэкспоненциальных алгоритмов дискретного логарифмирования при условии, что вычисляемое значение невелико — например, А-метод Полларда, описанный в разделе 3.6.1. Вычисление небольших дискретных логарифмов применяется во многих криптографических протоколах.
Проблема Диффи-Хеллмана исследуется весьма активно. Большой список литературы, посвященной этой теме, содержится в обзоре Одлыжко (Odlyzko) [221].
8.5 Криптосистема RSA (учебный вариант)
Наиболее известной криптосистемой с открытым ключом является алгоритм RSA, названный по первым буквам фамилий своих изобретателей — Ривеста (Rivest), Шамира (Samir) и Адлемана (Adleman) [246]. Криптосистема RSA — первая практическая реализация криптографии с открытым ключом на основе понятия однонаправленной функции с секретом, предложенного Диффи и Хелл-маном [97, 98].
Криптосистема RSA описывается алгоритмом 8.1. Отметим, что этот алгоритм носит учебный характер.
Покажем, что система, описанная алгоритмом 8.1, действительно является криптографической, т.е. процедура расшифровки, выполненная Алисой, действительно восстанавливает исходный текст, зашифрованный Бобом.
Из определения операций модулярной арифметики (определение 4.4 из раздела 4.3.2.5) следует, что сравнение ed= l(mod<^(Ar)) в алгоритме 8.1 эквивалентно уравнению
ed=l + k<t>(N),
304
Часть ill. Основные методы криптографии
Алгоритм 8.1. Криптосистема RSA Ключ
Для того чтобы установить ключ, Алисе необходимо выполнить следующие операции.
