Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Определение 8.1 (Вычислительная проблема Диффи-Хеллмана) (в конечном поле).
ИСХОДНЫЕ ДАННЫЕ:
Злоумышленник ("Алиса") — Бобу: д.,
771
8.4 Задача Диффи-Хеллмана и задача дискретного логарифмирования
desc(?q): описание конечного поля ?q;
д ? ?* — порождающий элемент группы ?*;
9a,9b€?q, гдеО<а,Ь<д.
РЕЗУЛЬТАТ:
298
Часть III. Основные методы криптографии
Эта формулировка представляет собой общую постановку задачи в конечном поле ?q. В протоколе обмена ключами Диффи-Хеллмана используется более* специальный случай. Общая постановка приводится только для формализации задачи, хотя для большей ясности мы будем изучать лишь частный случай.
Если бы проблему Диффи-Хеллмана было легко решить, то значение <7ob(modp) можно было бы найти, зная числа р,д,да и дь, которые являются частью протокола. Предполагая, что противник обладает возможностями перехвата информации (раздел 2.3), следует предположить, что эти числа не являются для него секретом.
Проблема Диффи-Хеллмана опирается на сложность вычисления дискретного логарифма (discrete logarithm problem).
Определение 8.2 (Задача дискретного логарифмирования) (в конечном поле).
Дискретное логарифмирование аналогично обычному логарифмированию I в поле действительных чисел. Однако в отличие от последней задачи, в которой решение является приближенным, задача о вычислении дискретного логарифма имеет точное решение.
Как указывалось в главе 4, в основе современной криптографии лежит теория I вычислительной сложности. Это значит, что стойкость криптосистем с открытым ключом является условной и зависит от сложности решения некоторых задач. Проблема Диффи-Хеллмана и задача дискретного логарифмирования считаются трудноразрешимыми. Интуитивно ясно, что сложность решения этих задач зави- I сит как от размера поля ?q, так и от выбора параметров (открытого параметра д и секретных чисел а и Ь). Очевидно, что небольшие варианты этих задач явля- , ются разрешимыми. В свое время мы покажем, что существуют другие варианты этих задач, которые относительно легко решить. Таким образом, точное описание понятия сложности решения задачи должно учитывать как размер задачи, так и выбор ее варианта. Сведения из теории сложности, приведенные в главе 4, позволяют сформулировать точные предположения о неразрешимости проблемы Диффи-Хеллмана и задачи дискретного логарифмирования. Рекомендуем читателям вспомнить некоторые понятия и обозначения, используемые в теории вычислительной сложности (в частности, "вероятностный полиномиальный алгоритм" и "пренебрежимо малая величина").
Целое число а обозначается как logg h.
ИСХОДНЫЕ ДАННЫЕ:
РЕЗУЛЬТАТ:
desc(?q): описание конечного поля ?q;
д € F* — порождающий элемент группы ?*;
h € r/F*.
Уникальное число а < q, удовлетворяющее условию h = ga.
Глава 8. Шифрование — асимметричные методы
299
Предположение 8.1 (Условия неразрешимости проблемы Диффи-Хеллмана).
Алгоритмом решения проблемы Диффи-Хеллмана называется вероятностный полиномиальный алгоритм Л с преимуществом е > 0:
е = Prob [даЬ - Л (desc (Fg), д, <Д дь)] ,
где входные данные алгоритма Л указаны в определении 8.1.
Пусть XQ — генератор вариантов, получающий на вход число lfc, время работы которого является полиномом от параметра к, а результатом — 1) desc(F9), где \q\ = к, и 2) порождающий элемент g 6 F*.
Будем говорить, что генератор XQ удовлетворяет условиям неразреишмости проблемы Диффи-Хеллмана, если для вариантов TQ(lk) не существует алгоритма решения с преимуществом е > 0, которое не является пренебрежимо малым по сравнению со всеми достаточно большими числами к.
Предположение 8.2 (Условия неразрешимости задачи дискретного логарифмирования). Алгоритмом решения задачи дискретного логарифмирования называется вероятностный полиномиальный алгоритм Л с преимуществом е > 0:
е = Prob [logg h <— Л (desc (F9) , g, h)] ,
где входные данные алгоритма Л указаны в определении 8.2.
Пусть TQ — генератор вариантов, получающий на вход число lk, время работы которого является полиномом от параметра к, а результатом — 1) desc(Fg), где \q\ — к, 2) порождающий элемент g Е?*и 3) элемент h G ?*.
Будем говорить, что генератор XQ удовлетворяет условиям неразрешимости задачи дискретного логарифмирования, если для вариантов TQ{lk) не существует алгоритма решения с преимуществом е > 0, которое не является пренебрежимо малым по отношению ко всем достаточно большим числам к.
Иначе говоря, здесь предполагается, что почти все достаточно большие варианты указанных задач в конечных полях не имеют эффективного алгоритма решения. Доля слабых вариантов этих задач, поддающихся решению, пренебрежимо мала.
И все же эти два предположения требуют уточнения. Для начала сделаем несколько формальных утверждений.
Примечание 8.1.
Л В предположениях 8.1 и 8.2 соответствующие вероятностные пространства должны учитывать 1) пространство вариантов, из которых извлекаются произвольные конечные поля и элементы (важность этого условия обсуждается в разделе 8.4.1) и 2) пространство случайных операций в эффективном алгоритме. Второе условие необходимо, поскольку в множество
