Математические основы криптологии и криптографические методы и средс

2.2.2. Класс NP

Говорят, что недетерминированный алгоритм, решающий зада­ чу распознавания П, работает в течение «полиномиального времени», если найдется полином р такой, что для любого / е Уп найдется не­ которая догадка S, приводящая на стадии детерминированной про­ верки на входе (/,$) к ответу «да» за время />(Length[/]). Отсюда сле­ дует, что «размер» угадываемой структуры S будет обязательно ог­ раничен полиномом от Length [/], так как на проверку догадки S мо­ жет быть затрачено не более чем полиномиальное время.

Класс NP - это класс всех задач распознавания П, которые при разумном кодировании могут быть решены недетерминированными алгоритмами за полиномиальное время. Формальным эквивалентом недетерминированного алгоритма является программа для недетер­ минированной одноленточной машины Тьюринга (НДМТ). Модель НДМТ имеет такую же структуру, как ДМТ; отличие состоит лишь в том, что НДМТ дополнена угадывающим модулем со своей голов­ кой, которая может только записывать на ленту (рис. 55).

Рис. 55. Схематическое представление НДМТ

Угадывающий модуль дает информацию для записывания «до­ гадки» и применяется исключительно с этой целью.

Программа НДМТ определяется точно так же, как ДМТ-прог- рамма, при этом используются:

♦ленточный алфавит Г;

♦входной алфавит 2;

♦пустой символ b;

♦множество состояний

♦начальное состояние </0;

♦заключительные состояния qy,qn;

♦функция перехода 5: (Q\{qy,qn}) * Г—+Q * Г * {-1,1}. Вычисление НДМТ-программы при входе лге Е* в отличие от

ДМТ-программы имеет две различные стадии.

На первой стадии происходит «угадывание». В начальный мо­ мент времени входное слово х записывается в ячейках с номерами 1, 2, |дс| (остальные ячейки пусты), читающая/пишущая головка «смотрит» на ячейку с номером 1, пишущая головка угадывающего модуля смотрит на ячейку - 1, а устройство управления «пассивно». Затем угадывающий модуль начинает управлять угадывающей го­ ловкой, которая делает один шаг в каждый момент времени и либо пишет в находящейся под ней ячейке одну из букв алфавита Г

исдвигается при этом на одну ячейку влево, либо останавливается.

Впоследнем случае угадывающий модуль переходит в пассивное состояние, а управляющее устройство начинает работу в состоянии qd. Угадывающий модуль решает, продолжить ли работу (перейти ли в пассивное состояние, какую букву из Г написать на ленте), причем делает это совершенно произвольно. Таким образом, угадывающий модуль до момента окончания своей работы может написать любое слово из Г* и в действительности может никогда не остановиться.

Стадия проверки начинается в тот момент, когда управляющее устройство переходит в состояние qO. Начиная с этого момента вы­ числение НДМТ-программы осуществляется в точности по тем же правилам, что и ДМТ-программы. Угадывающий модуль и его го­ ловка в вычислении более не участвуют, выполнив свою роль, т.е. записав на ленте слово-догадку. Конечно, слово-догадка может про­ сматриваться читающей\пишущей головкой в процессе проверки. Вычисление заканчивается тогда, когда управляющее устройство

перейдет в одно из двух заключительных состояний {qy или qn); оно называется принимающим вычислением, если остановка происходит в состоянии «да». Все остальные вычисления, заканчивающиеся или нет, называются непринимающими.

Отметим, что любая НДМТ-программа М может иметь беско­ нечное число возможных вычислений при данном входе х, по одному для каждого слова-догадки из Г*. Будем говорить, что НДМТпрограмма принимает х, если, по крайней мере, одно из этих вычис­ лений на входе х является принимающим. Язык, распознаваемый программой М, —это язык

LM = {х е £*: М принимает х}.

Время, требующееся недетерминированной программе М для того, чтобы принять слово х е LM, - это минимальное число шагов, выполняемых на стадиях угадывания и проверки до момента дости­ жения заключительного состояния qy, где минимум берется по всем принимающим вычислениям программы М на входе дг. Временная сложность НДМТ-программы-это функция Тм: Z + —>Z+ , опреде­ ляемая следующим образом:

Заметим, что временная сложность программы М зависит толь­ ко от числа шагов, выполняемых в принимающих вычислениях, а также, что мы полагаем М(п) равным 1, если нет ни одного входа длины и, принимаемого программой М.

НДМТ-программа называется НДМТ-программой с полиноми­ альным временем работы, если найдет полином р такой, что Тм(п) ^р(п) для всех и ^ 1. Класс NP формально определяется так:

Будем говорить, что задача распознавания принадлежит классу NP при схеме кодирования е, если L[П, е\ е NP.

Иными словами, в классе NP существует предикат, вычислимый за полиномиальное время.

В этом случае язык L принадлежит NP, если для всякого слова из L длины п можно угадать некоторую строку полиномиальной от пдлины и затем с помощью предиката убедиться в правильности до­ гадки. Ясно, что Р Q NP. Является ли это включение строгим - одна из самых известных нерешенных задач математики. В классе NP выделен подкласс максимально сложных языков, называемых TVP-полными: любой NP полный язык распознаваем за полиномиаль­ ное время тогда и только тогда, когда Р = NP. Рассмотрим подробнее взаимоотношения этих классов.

2.2.3. Взаимоотношения между классами Р и N P

Итак, как мы выяснили выше, Р Q NP. Иными словами, всякая

задача распознавания, разрешимая за полиномиальное время детер­ минированным алгоритмом, разрешима также за полиномиальное время недетерминированным алгоритмом. Чтобы убедиться в этом, достаточно заметить, что любой детерминированный алгоритм мо­ жет быть использован в качестве стадии проверки недетерминиро­ ванного алгоритма. Если П е Р и А - произвольный детерминиро­ ванный полиномиальный алгоритм решения П, то полиномиальный недетерминированный алгоритм для П можно получить, воспользо­ вавшись А в качестве стадии проверки и игнорируя стадию угадыва­ ния. Таким образом, из П е Р следует, что ПеТУР. Полиномиальные недетерминированные алгоритмы определенно оказываются более мощными, чем полиномиальные детерминированные алгоритмы, и не известны общие методы их превращения в детерминированные. Самый сильный из известных в настоящее время результатов состоит в следующем:

Теорема 23. Если П е NP, то существует такой полином р , что П может быть решена детерминированным алгоритмом с временной сложностью 0(2/,(")).

Для многих частных задач класса NP не найдено полиномиаль­ ного детерминированного алгоритма, несмотря на упорные усилия

многих известных исследователей. Поэтому широко распространено мнение, что P ^N P , хотя доказательство этой гипотезы отсутст­ вует. Поэтому мы будем представлять себе класс NP так, как он изображен на рис. 56 гипотетической картины класса NP. Затем­ ненная область NP\P ожидаемо не пуста.

2.2.4. Полиномиальная сводимость и WP-полные задачи. Теорема Кука

Если Р не совпадает с NP, то различие между классами Р и NP\P очень существенно.

Все задачи из Р могут быть решены полиномиальными алгоритмами, а все задачи из NP\P труднорешаемы. Поэтому если P ^N P , то для каждой конкретной задачи П еМР важно знать, какая из этих двух возможностей реализуется.

Рассмотрим понятие полиномиальной сводимости. Будем гово­ рить, что имеет место полиномиальная сводимость языка L l^ £ l* к языку Z,2^:£2*, если существует функция /: £1*—> £2*, удовле­ творяющая двум условиям:

1. Существует ДМТ-программа, вычисляющая / с временной сложностью, ограниченной полиномом.

2. Для любого Jte £ 1 *, x e L l в том и только том случае, если

Ax)^L2.

Если L1 полиномиально сводится к L2, то будем писать Ы О С £2 и говорить «Ь\ сводится к L2».

Существует лемма, утверждающая, что если LI CXZL2, то из L2 е Р следует, что L2 G Р.

Теперь дадим понятие NP-полного языка. Язык L называется NP-полным, если L e N P и любой другой язык V е NP сводится к L, т.е. задача распознавания П называется NP-полной, если П е € NP и любая другая задача распознавания IF e NP сводится к П. Таким образом, лемма, указанная выше, позволяет отождествить NP-полные задачи с «самыми трудными задачами из NP». Если хотя бы одна

NP-полная задача может быть решена за полиномиальное время, то все задачи из NP также могут быть решены за полиномиальное время. Если хотя бы одна задача труднорешаема, то все задачи трудноре­ шаемы (рис. 57). Следовательно, любая NP - полная задача П обла­ дает свойством: если P ^N P , то П е NP\P. Или П е Р тогда и только тогда, когда Р = NP. Можно дать более полную картину класса NP.

Одним из важнейших результа­ тов теории NP-задач стало доказа­

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

2.2.5. Гипотеза Р Ф N P

Определим, является ли гипотеза Р ф NP необходимым и доста­ точным условием для существования стойких криптографических схем.

Вернемся к примеру, рассмотренному выше. Определим сле­ дующий язык.

L = {(/ftД*)|существует сообщение т такое, что E(Kl)[tn] = d и его l-й бит равен 1.

Ясно, что L е NP: вместо полного перебора можно просто уга­ дать открытый текст т и проверить за полиномиальное время, что

E{K\)[m\=du i-й бит m равен 1. Если да, то входное слово (А1Д|) Принимается, в противном случае - отвергается.

Если предположить, что Р = А/Р, то существует детерминиро­ ванный полиномиальный алгоритм, распознающий язык L. Зная К\ и d, с помощью этого алгоритма можно последовательно, по биту, вы­ числить открытый текст т. В этом случае криптосистема нестойкая.

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

2.2.6. Односторонние функции

Считать криптосистему стойкой можно в том случае, если лю­ бой такой алгоритм требует практически неосуществимого объема вычислений или срабатывает с пренебрежимо малой вероятностью. Это теоретико-сложностной подход к определению стойкости. Для его реализации необходимо выполнить следующее:

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

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

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

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

Во-первых, в криптографических системах всегда используются фиксированные значения параметров. Например, системы разраба­ тываются для ключей длины в 256 или 512 байтов. Для применения Ж е теоретико-сложностного подхода необходимо, чтобы задача, вы­

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

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

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

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

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

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

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

Пусть Ел = {0,1 }л - множество всех двоичных строк длины п. Под функцией / мы будем понимать семейство отображений

{/л}, где fit: Ел —►Е/л, т = т(п). Для простоты предположим, что л пробегает натуральный ряд, а отображения fn определены всюду. Функция / называется честной, если полином q(x), такой что

п < q(m(n)) для всех л.

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

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

♦существует полиномиальный алгоритм, который для всякого

хвычисляет/*);

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

ивсех достаточно больших и Р{ДА(/(х))) =/.*)} < 1/р(л). Ве­ роятность здесь определяется случайным выбором строки х

ислучайными величинами, которые А использует в своей работе.

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

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

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

Существование односторонних функций является необходимым условием для стойкости многих типов криптографических схем. Вернемся к примеру, приведенному выше. Рассмотрим функцию / такую, что fir) = ATI. Она вычислима с помощью алгоритма G за по­ линомиальное время. Покажем, что если / - н е односторонняя функ­ ция, то криптосистема нестойкая. Предположим, что существует по­ линомиальный вероятностный алгоритм А, который инвертирует / с вероятностью, по крайней мере, 1/р(п) для некоторого полинома р. Здесь «-длина ключа К\. Злоумышленник может подать на вход алгоритма значение ключа К\ и получить с указанной вероятностью некоторое значение г ’из прообраза. Далее злоумышленник подает г ’ на вход алгоритма G и получает пару ключей (/Л, К ’2). Хотя К ’2 не обязательно совпадает с К2, тем не менее по определению криптоси­ стемы D(K2){E(KX)[ni\} - т для любого открытого текста т. По­ скольку К2 найден с вероятностью, по крайней мере, 1/р(п), схема нестойкая.

Из всего сказанного следует, что предположение о существова­ нии односторонних функций является самым слабым криптографи­ ческим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем раз­ личных типов.

2.2.7. Примеры однонаправленных функций

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