ния D;- таковы, что для любого открытого текста т =•

Рассмотрим теперь гипотетическую атаку злоумышленника на эту систему. Противнику известен открытый ключ к\, но неизвестен соответствуюш,ий секретный ключ кг. Противник перехватил криптограмму d и пытается найти сообш,ение т, где d = Е (т). Поскольку алгоритм шифрования открыт, противник может просто последовательно перебрать все возможные сообш,ения длины п, вычислить для каждого такого сообш,ения nii криптограмму dj = Ej (nij) и сравнить с d. То сообш,ение,

для которого di = d и будет искомым открытым текстом. Если повезет, то открытый текст будет найден достаточно быстро. В худшем же случае перебор будет выполнен за время порядка 2"Т{п), где Т{п) - время, требуемое для шифрования сообш,ения длины п. Если сообш,ения имеют длину порядка 1 ООО битов, то такой перебор неосуш,ествим на практике ни на каких самых мош,ных компьютерах.

Мы рассмотрели лишь один из возможных способов атаки на криптосистему и простейший алгоритм поиска открытого текста, называемый обычно алгоритмом полного перебора Используется также и другое название: «метод грубой силы». Другой простейший алгоритм поиска открытого текста - угадывание. Этот очевидный алгоритм требует небольших вычислений, но срабатывает с пренебрежимо малой вероятностью (при больших длинах текстов). На самом деле противник может пытаться атаковать криптосистему различными способами и использовать различные, более изош,ренные алгоритмы поиска открытого текста.

Кроме того, злоумышленник может попытаться восстановить секретный ключ, используя знания (в обш,ем случае несекретные) о математической зависимости между открытым и секретным ключами. Естественно считать криптосистему стойкой, если любой такой алгоритм требует практически неосуш,естви-мого объема вычислений или срабатывает с пренебрежимо малой вероятностью. (При этом противник может использовать не только детерминированные, но и вероятностные алгоритмы.) Это и есть теоретико-сложностный подход к определению стой-

кости. Для его реализации в отношении того или иного типа криптографических систем необходимо выполнить следуюш,ее:

1) дать формальное определение системы данного типа;

2) дать формальное определение стойкости системы;

3) доказать стойкость конкретной конструкции системы данного типа.

Здесь сразу же возникает ряд проблем.

Во-первых, для применения теоретико-сложностного подхода необходимо, построить математическую модель криптографической системы, зависяш,ую от некоторого параметра, называемого параметром безопасности, который может принимать сколь угодно большие значения (обычно для простоты предполагается, что параметр безопасности может пробегать весь натуральный ряд).

Во-вторых, определение стойкости криптографической системы зависит от той задачи, которая стоит перед противником, и от того, какая информация о схеме ему доступна Поэтому стойкость систем приходится определять и исследовать отдельно для каждого предположения о противнике.

В-третьих, необходимо уточнить, какой объем вычислений можно считать «практически неосуш,ествимым». Из сказанного выше следует, что эта величина не может быть просто константой, она должна быть представлена функцией от растуш,его параметра безопасности. В соответствии с тезисом Эдмондса алгоритм считается эффективным, если время его выполнения ограничено некоторым полиномом от длины входного слова (в нашем случае - от параметра безопасности). В противном случае говорят, что вычисления по данному алгоритму практически неосуш,ествимы. Заметим также, что сами криптографические системы должны быть эффективными, т. е. все вычисления, предписанные той или иной схемой, должны выполняться за полиномиальное время.

В-четвертых, необходимо определить, какую вероятность можно считать пренебрежимо малой. В криптографии принято считать таковой любую вероятность, которая для любого полинома р и для всех достаточно больших п не превосходит \1р{п), где п - параметр безопасности.

Итак, при наличии всех указанных выше определений, проблема обоснования стойкости криптографической системы све-

лась к доказательству отсутствия полиномиального алгоритма, который решает задачу, стояш,ую перед противником. Но здесь возникает еш,е одно и весьма серьезное препятствие: современное состояние теории сложности вычислений не позволяет доказывать сверхполиномиальные нижние оценки сложности для конкретных задач рассматриваемого класса. Из этого следует, что на данный момент стойкость криптографических систем может быть установлена лишь с привлечением каких-либо недоказанных предположений. Поэтому основное направление исследований состоит в поиске наиболее слабых достаточных условий (в идеале - необходимых и достаточных) для суш,ествова-ния стойких систем каждого из типов.

В основном, рассматриваются предположения двух типов -обш,ие (или теоретико-сложностные) и теоретико-числовые, т. е. предположения о сложности конкретных теоретико-числовых задач. Все эти предположения в литературе обычно называются криптографическими.

Рассмотрим одно из таких предположений.

Обозначим через Е множество всех конечных двоичных слов, а через Е" - множество всех двоичных слов длины п. Подмножества Z g Е в теории сложности принято называть языками. Говорят, что машина Тьюринга М работает за полиномиальное время (или просто, что она полиномиальна), если суш,е-ствует полином р такой, что на любом входном слове длины п машинам останавливается после выполнения не более, чем р{п) операций. Машина Тьюринга М распознает (другой термин -принимает) язык L, если на всяком входном слове х & L машина М останавливается в принимаюш,ем состоянии, а на всяком слове х € Z - в отвергаюш,ем. Класс Р - это класс всех языков, распознаваемых машинами Тьюринга, работаюш,ими за полиномиальное время. Функция / Е Е вычислима за полиномиальное время, если суш,ествует полиномиальная машина Тьюринга такая, что если на вход ей подано слово х g Е, то в момент останова на ленте будет записано значениеХ). Язык L принадлежит классу NP, если суш,ествуют предикат Р(х,>): ЕхЕ {0,1}, вычислимый за полиномиальное время, и полином р такие, что L = {х 3 у Р{х,у)8с \у\ < р(х)}. То есть язык L принадлежит NP, если для всякого слова из L длины п можно угадать некоторую стро-

ку полиномиальной от п длины и затем с помош,ью предиката Р убедиться в правильности догадки. Ясно, что Р с NP. Является ли это включение строгим - одна из самых известных нерешенных задач математики. Большинство специалистов считают, что оно строгое (так называемая гипотеза Р Ф NP). В классе NP выделен подкласс максимально сложных языков, называемых NP-полными: любой NP-полный язык распознаваем за полиномиальное время тогда и только тогда, когда Р = NP.

Нам еш,е потребуется понятие вероятностной машины Тьюринга. В обычных машинах Тьюринга (их называют детерминированными) новое состояние, в которое машина переходит на очередном шаге, полностью определяется текуш,им состоянием и тем символом, который обозревает головка на ленте. В вероятностных машинах новое состояние может зависеть еш,е и от случайной величины, которая принимает значения О и 1 с вероятностью 1/2 каждое. Можно считать, что вероятностная машина Тьюринга имеет дополнительную случайную ленту, на которой записана бесконечная двоичная случайная строка Случайная лента может читаться только в одном направлении и переход в новое состояние может зависеть от символа, обозреваемого на этой ленте.

Рассмотрим теперь следуюш,ий естественный вопрос: не является ли гипотеза Р Ф NP необходимым и достаточным условием для суш,ествования стойких криптографических схем?

В самом деле, необходимость во многих случаях почти очевидна. Вернемся к рассмотренному выше примеру. Определим следуюш,ий язык:

L = {{k\,d,i)\ 3 сообш,ение т: d = Е (т) nmil}.

Ясно, что L g NP: можно просто угадать открытый текст т и проверить за полиномиальное время, что d = Е (т) и г-й бит т

равен 1. Если да, то входное слово {k\,d,i) принимается, в противном случае - отвергается.

В предположении Р = NP суш,ествует детерминированный полиномиальный алгоритм, распознаюш,ий язык L. Зная k\iid,c помош,ью этого алгоритма можно последовательно, по биту, вычислить открытый текст т. Тем самым доказано, что криптосистема нестойкая.

Что же касается вопроса о достаточности предположения Р Ф NP, то здесь напрашивается следуюш,ий подход: выбрать какую-либо NP-полную задачу и построить на ее основе криптографическую схему, задача взлома которой (т. е. задача, стоя-ш,ая перед противником) была бы NP-полной. Такие попытки предпринимались в начале 80-х годов, в особенности в отношении криптосистем с открытым ключом, но к успеху не привели. Результатом всех этих попыток стало осознание следуюш,его факта: даже если Р Ф NP, то любая NP-полная задача может оказаться трудной лишь на некоторой бесконечной последовательности входных слов. Иными словами, в определение класса NP заложена мера сложности «в худшем случае». Для стойкости же криптографической схемы необходимо, чтобы задача противника была сложной «почти всюду». Таким образом, стало ясно, что для криптографической стойкости необходимо су-ш,ественно более сильное предположение, чем Р Ф NP. А именно, предположение о суш,ествовании односторонних функций.

3.2. Односторонние функции и функции-ловушки

Центральным понятием в теории асимметричных криптографических систем является понятие односторонней функции.

Неформально под односторонней функцией понимается эффективно вычислимая функция, для обраш,ения которой (т.е. для поиска хотя бы одного значения аргумента по заданному значению функции) не суш,ествует эффективных алгоритмов. Заметим, что обратная функция может и не суш,ествовать.

Под функцией мы будем понимать семейство отображений {}, где/,: Е" Е", т = т{п). Для простоты предположим, что п пробегает натуральный ряд, а отображения/, определены всюду. Функция / называется честной, если 3 полином q{x), такой что V п q{m{n)) > п.

Формально понятие односторонней функции описывается следуюш,им образом:

Определение 3.1. Честная функция / называется односторонней, если

1. Суш,ествует полиномиальный алгоритм, который для всякого X вычисляетХх);

2. Для любой полиномиальной вероятностной машины Тьюринга J выполнено следуюш,ее. Пусть строках

выбрана случайным образом из множества Е". Тогда для любого полинома р и всех достаточно больших п

Р{Д(Дх))) =Хх)} < \lpin).

Второе условие качественно означает следуюш,ее. Любая полиномиальная вероятностная машина Тьюринга А может по данному у найти х из уравнения fix) = у лишь с пренебрежимо малой вероятностью.

Заметим, что требование честности опустить нельзя. Поскольку длина входного словаХ) машины А равна т, ей может не хватить полиномиального от т времени просто на выписывание строки X.

Суш,ествование односторонних функций является необходимым условием стойкости многих криптосистем. Вернемся к примеру, приведенному в п. 3.1. Рассмотрим функцию/ такую, чтоХ") k\. Она вычислима с помош,ью алгоритма G за полиномиальное время. Покажем, что если / - не односторонняя функция, то криптосистема нестойкая. Предположим, что суш,е-ствует полиномиальный вероятностный алгоритм А, обраш,аю-ш,ий / с вероятностью по крайней мере \1р{п) для некоторого полинома р. Злоумышленник может подать на вход алгоритма значение ключа к\ и получить с указанной вероятностью некоторое значение г из прообраза. Далее злоумышленник подает г на вход алгоритма G и получает пару ключей {к\, кг). Хотя кг не обязательно совпадает с кг, по определению криптосистемы £), {Еь (т)) = т для любого открытого текста т. Поскольку кг

«2 1

найден с вероятностью по крайней мере \1р{п), схема нестойкая.

Функцией-ловушкой называется односторонняя функция, для которой обратную функцию вычислить просто, если имеется некоторая дополнительная информация, и сложно, если такая информация отсутствует.

В качестве задач, приводяш,их к односторонним функциям, можно привести следуюш,ие.

1. Разложение числа на простые сомножители.

Вычислить произведение двух простых чисел очень просто. Однако, для решения обратной задачи - разложения заданного числа на простые сомножители, эффективного алгоритма в на-стояш,ее время не суш,ествует.