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

11.2 Теория сложности

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

Сложность алгоритмов

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

Обычно вычислительная сложность алгоритма выражается с помощью нотации "О большого", т.е описыв а-ется порядком величины вычислительной сложности. Это просто член разложения функции сложности, быстрее всего растущий с ростом n, все члены низшего порядка игнорируются. Например, если временная сложность данного алгоритма равна 4 n2+7n+12, то вычислительная сложность порядка n2, записываемая как O( n2).

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

Эта нотация позволяет увидеть, как объем входных данных влияет на требования к времени и объему пам яти. Например, если 7= O(n), то удвоение входных данных удвоит и время выполнения алгоритма. Если 7=О(2п), то добавление одного бита к входным данным удвоит время выполнения алгоритма.

Обычно алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит от n: 0(1). Алгоритм является линейным, если его временная сложность 0( n). Алгоритмы могут быть квадратичными, кубическими и т.д. Все эти алгоритмы - полиномиальны, их сложность - 0(nm), где m - константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем.

Алгоритмы, сложность которых равна О( tf(n), где t - константа, большая, чем 1, а J(n) - некоторая полиномиальная функция от n, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сло ж-ность которых равна О(cf(n)), где где c - константа, а f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиномиальным.

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

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

Табл. 11-2

Время выполнения для различных классов алпоритмов

Класс Сложность Количество операций для n=106 Время при 106 операций в секунду

Постоянные

Линейные

Квадратичные

Кубические

Экспоненциальные

О(1)

0(n) 0(n2) 0(n3) 0(2n)

106 101

1 мкс

11.6 дня

32000 лет

В 10301006 раз больше, чем время существования вселенной

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

Взглянем на проблему вскрытия алгоритма шифрования грубой силой. Временная сложность такого вскр ы-тия пропорциональна количеству возможных ключей, которое экспоненциально зависит от длины ключа. Если n - длина ключа, то сложность вскрытия грубой силой равна 0(2 n). В разделе 12.3 рассматривается дискуссия об использовании для DES 56-битового ключа вместо 112-битового. Сложность вскрытия грубой силой при 56-битовом ключе составляет 256, а при 112-битовом ключе - 2112. В первом случае вскрытие возможно, а во втором - нет.

Сложность проблем

Теория сложности также классифицирует и сложность самих проблем, а не только сложность конкретных алгоритмов решения проблемы. (0тличным введением в эту тему являются [600, 211, 1226], см. также [1096, 27, 739].) Теория рассматривает минимальное время и объем памяти, необходимые для решения самого трудн ого варианта проблемы на теоретическом компьютере, известном как машина Тьюринга. Машина Тьюринга представляет собой конечный автомат с бесконечной лентой памяти для чтения-записи и является реалистичной моделью вычислений.

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

Что еще хуже, Алан Тьюринг доказал, что некоторые проблемы принципиально неразрешимы. Даже отвлекаясь от временной сложности алгоритма, нево зможно создать алгоритм решения этих проблем.

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

Рис. 11-1. Классы сложности

Находящийся в самом низу класс P состоит из всех проблем, которые можно решить за полиномиальное время. Класс NP - из всех проблем, которые можно решить за полиномиальное время только на недетермин и-рованной машине Тьюринга: вариант обычной машины Тьюринга, которая может делать предположения. М а-шина предполагает решение проблемы - либо "удачно угадывая", либо перебирая все предположения пара л-лельно - и проверяет свое предположение за полиномиальное время.

Важность NP в криптографии состоит в следующем: многие симметричные алгоритмы и алгоритмы с о т-крытыми ключами могут быть взломаны за недетерминированное полиномиальное время. Для данного шифр о-текста C, криптоаналитик просто угадывает открытый текст, X, и ключ, к, и за полиномиальное время выполняет алгоритм шифрования со входами X и к и проверяет, равен ли результат C. Это имеет важное теоретическое значение, потому что устанавливает верхнюю границу сложности криптоанализа этих алгоритмов. На практике, конечно же, это выполняемый за полиномиальное время детерминированный алгоритм, который и ищет кри п-тоаналитик. Более того, этот аргумент неприменим ко всем классам шифров, конкретно, он не применим для одноразовых блокнотов - для любого C существует множество пар X, к, дающих C при выполнении алгоритма шифрования, но большинство этих X представляют собой бессмысленные, недопустимые открытые тексты.

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

Если все NP проблемы решаются за полиномиальное время на детерминированной машине, то P = NP. Хотя кажется очевидным, что некоторые NP проблемы намного сложнее других (вскрытие алгоритма шифрования грубой силой против шифрования произвольного блока шифротекста), никогда не б1ло доказано, что P NP (или что P = NP). Однако, большинство людей, работающих над теорией сложности, убеждены, что эти классы неравны.

Что удивительно, можно доказать, что конкретные NP-проблемы настолько же трудны, как и любая пробл е-ма этого класса. Стивен Кук (Steven Cook) доказал [365], что проблема Выполнимости (Satisfiability problem, дано правильное логическое выражение, существует ли способ присвоить правильные значения входящим в него переменным так, чтобы все выражение стало истиной?) является NP-полной. Это означает, что, если проблема Выполнимости решается за полиномиальное время, то P = NP. Наоборот, если может быть доказано, что для любой проблемы класса NP не существует детерминированного алгоритма с полиномиальным временем решения, доказательство покажет, что и для проблемы Выполнимости не существует детерминированного алг о-ритма с полиномиальным временем решения. В NP нет проблемы труднее, чем проблема Выполнимости.

С тех пор, как основополагающая работа Кука была опубликована, было показано, что существует множес т-во проблем, эквивалентных проблеме Выполнимости, сотни их перечислены в [600], ряд примеров приведен ниже. Из-за эквивалентности я полагаю, что эти проблемы также являются NP-полными, они входят в класс NP и так же сложны, как и любая проблема класса NP. Если бы была доказана их решаемость за детерминир о-ванное полиномиальное время, вопрос P против NP б1л бы решен. Вопрос, верно ли P = NP, является центральным нерешенным вопросом теории вычислительной сложности, и не ожидается, что он будет решен в ближайшее время. Если кто-то покажет, что P = NP, то большая часть этой книги станет ненужной: как объя снялось ранее многие классы шифров тривиально взламываются за недетерминированное полиномиальное вр е-