Сложность проблем - раздел Компьютеры, Часть III Криптографические алгоритмы Теория Сложности Также Классифицирует И Сложность Самих Проблем, А Не Только ...
Теория сложности также классифицирует и сложность самих проблем, а не только сложность конкретных алгоритмов решения проблемы. (Отличным введением в эту тему являются [600, 211, 1226], см. также [1096, 27, 739].) Теория рассматривает минимальное время и объем памяти, необходимые для решения самого трудн о-го варианта проблемы на теоретическом компьютере, известном как машина Тьюринга.Машина Тьюринга представляет собой конечный автомат с бесконечной лентой памяти для чтения-записи и является реалистичной моделью вычислений.
Проблемы, которые можно решить с помощью алгоритмов с полиномиальным временем, называются р е-шаемыми, потому что для разумных входных данных обычно могут быть решены за разумное время. (Точное определение "разумности" зависит от конкретных обстоятельств.) Проблемы, которые невозможно решить за полиномиальное время, называются нерешаемыми, потому что вычисление их решений быстро становится н е-возможным. Нерешаемые проблемы иногда называют трудными.Проблемы, которые могут быть решены только с помощью суперполиномиальных алгоритмов, вычислительно нерешаемы, даже при относительно м а-лых значениях п.
Что еще хуже, Алан Тьюринг доказал, что некоторые проблемы принципиально неразрешимыДаже отвлекаясь от временной сложности алгоритма, невозможно создать алгоритм решения этих проблем.
Проблемы можно разбить на классы в соответствии со сложностью их решения. Самые важные классы и их предполагаемые соотношения показаны на 10-й. (К несчастью, лишь малая часть этих утверждений может быть доказана математически.)
PSPACE-полные
PSPACE
NP-полные NP
P
Рис. 11-1. Классы сложности
Находящийся в самом низу класс Р состоит из всех проблем, которые можно решить за полиномиальное время. Класс NP - из всех проблем, которые можно решить за полиномиальное время только на недетермин и-рованной машине Тьюринга: вариант обычной машины Тьюринга, которая может делать предположения. М а-шина предполагает решение проблемы - либо "удачно угадывая", либо перебирая все предположения пара л-лельно - и проверяет свое предположение за полиномиальное время.
Важность NP в криптографии состоит в следующем: многие симметричные алгоритмы и алгоритмы с о т-крытыми ключами могут быть взломаны за недетерминированное полиномиальное время. Для данного шифр о-текста С, криптоаналитик просто угадывает открытый текст, X, и ключ, к, и за полиномиальное время выполняет алгоритм шифрования со входами Хм км проверяет, равен ли результат С. Это имеет важное теоретическое значение, потому что устанавливает верхнюю границу сложности криптоанализа этих алгоритмов. На практике, конечно же, это выполняемый за полиномиальное время детерминированный алгоритм, который и ищет кри п-тоаналитик. Более того, этот аргумент неприменим ко всем классам шифров, конкретно, он не применим для одноразовых блокнотов - для любого С существует множество пар X, к, дающих С при выполнении алгоритма шифрования, но большинство этих X представляют собой бессмысленные, недопустимые открытые тексты.
Класс NP включает класс Р, так как любая проблема, решаемая за полиномиальное время на детерминир о-ванной машине Тьюринга, будет также решена за полиномиальное время на недетерминированной машине Тьюринга, просто пропускается этап предположения.
Если все NP проблемы решаются за полиномиальное время на детерминированной машине, то Р = NP. Хотя кажется очевидным, что некоторые NP проблемы намного сложнее других (вскрытие алгоритма шифрования грубой силой против шифрования произвольного блока шифротекста), никогда не было доказано, что Р Ф NP (или что Р = NP). Однако, большинство людей, работающих над теорией сложности, убеждены, что эти классы неравны.
Что удивительно, можно доказать, что конкретные NP-проблемы настолько же трудны, как и любая проблема этого класса. Стивен Кук (Steven Cook) доказал [365], что проблема Выполнимости (Satisfiability problem, дано правильное логическое выражение, существует ли способ присвоить правильные значения входящим в него переменным так, чтобы все выражение стало истиной?) является NP-полной. Это означает, что, если проблема Выполнимости решается за полиномиальное время, то Р = NP. Наоборот, если может быть доказано, что для любой проблемы класса NP не существует детерминированного алгоритма с полиномиальным временем решения, доказательство покажет, что и для проблемы Выполнимости не существует детерминированного алг о-ритма с полиномиальным временем решения. В NP нет проблемы труднее, чем проблема Выполнимости.
С тех пор, как основополагающая работа Кука была опубликована, было показано, что существует множес т-во проблем, эквивалентных проблеме Выполнимости, сотни их перечислены в [600], ряд примеров приведен ниже. Из-за эквивалентности я полагаю, что эти проблемы также являются NP-полными, они входят в класс NP и так же сложны, как и любая проблема класса NP. Если бы была доказана их решаемость за детерминир о-ванное полиномиальное время, вопрос Р против NP был бы решен. Вопрос, верно ли Р = NP, является центральным нерешенным вопросом теории вычислительной сложности, и не ожидается, что он будет решен в ближайшее время. Если кто-то покажет, что Р = NP, то большая часть этой книги станет ненужной: как объяснялось ранее многие классы шифров тривиально взламываются за недетерминированное полиномиальное вр е-
мя. Если Р = NP, то они вскрываются слабыми, детерминированными алгоритмами.
Следующим в иерархии сложности идет класс PSPACE.Проблемы класса PSPACEмогут быть решены в полиномиальном пространстве, но не обязательно за полиномиальное время. PSPACEвключает NP, но ряд проблем PSPACEкажутся сложнее, чем NP. Конечно, и это пока недоказуемо. Существует класс проблем, так называемых PSPACE-полных,обладающих следующим свойством: если любая из них является NP-проблемой, то PSPACE= NP,и если любая из них является Р-проблемой, то PSPACE= Р.
И наконец, существует класс проблем EXPTIME.Эти проблемы решаются за экспоненциальное время. Может быть действительно доказано, что EXPTIME-полныепроблемы не могут быть решены за детерминированное полиномиальное время. Также показано, что Р не равно EXPTIME.
NP-полные проблемы
Майкл Кэри (Michael Carey) и Дэвид Джонсон (David Johnson) составили список более чем 300 NP-полных проблем [600]. Вот некоторые:
— Проблема путешествующего коммивояжера. Путешествующему коммивояжеру нужно посетить разли ч-ные города, используя только один бак с горючим (существует максимальное расстояние, которое он м о-жет проехать). Существует ли маршрут, позволяющий ему посетить каждый голод только один раз, и с-пользуя этот единственный бак с горючим? (Это обобщение проблемы гамильтонова пути - см. раздел 5.1.)
— Проблема тройного брака. В комнате и мужчин, и женщин и и чиновников (священников, раввинов, кого угодно). Есть список разрешенных браков, записи которого состоят из одного мужчины, одной женщины и одного регистрирующего чиновника. Дан этот список троек, возможно ли построить и браков так, чтобы любой либо сочетался браком только с одним человеком или регистрировал только один брак?
— Тройная выполнимость. Есть список и логических выражений, каждое с тремя переменными. Например: если (х и у) то z, (х и w) или (не z), если ((не и и не х) или (z и (и или не х))) то (не гиа) или х), и т.д. Существует ли правильные значения всех переменных, чтобы все утверждения были истинными? (Это ч а-стный случай упомянутой выше проблемы Выполнимости.)
11.3 Теория чисел
Это не книга по теории чисел, поэтому я только набросаю ряд идей, используемых в криптографии. Если вам нужно подробное математическое изложение теории чисел, обратитесь к одной из этих книг: [1430, 72, 1171, 12, 959, 681, 742, 420]. Моими любимыми книгами по математике конечных полей являются [971, 1042]. См. также [88, 1157, 1158, 1060].
Все темы данного раздела:
Энтропия и неопределенность
Теория информации определяет количество информациив сообщении как минимальное количество бит, необходимое для кодирования всех возможных значений сообщения, считая все сообщения ра
Норма языка
Для данного языка норма языкаравна
г =H(M)/N
где N - это длина сообщения. При больших N норма обычного английского яз
Зашифрованного алгоритмами с различной длиной ключа
Длина ключа (в битах) Расстояние уникальности (в символах)
5.9
8.2
Практическое использование теории информации
Хотя эти понятия имеют большое теоретическое значение, реальный криптоанализ использует их достаточно редко. Расстояние уникальности гарантирует ненадежность системы, если оно слишком мало, но его
Путаница и диффузия
Двумя основными методами маскировки избыточности открытого текста сообщения, согласно Шеннону, служат путаница и диффузия [1432].
Путаницамаскирует связь между открытым те
Арифметика вычетов
Вы все учили математику вычетов в школе. Иногда ее называли "арифметикой часов". Если Милдред сказ а-ла, что она будет дома к 10:00, и опоздала на 13 часов, то когда она придет домой, и н
Простые числа
Простым называется целое число, большее единицы, единственными множителями которого является 1 и оно само: оно не делится ни на одно другое число. Два - это простое число. Простыми являются и 73, 2
Наибольший общий делитель
Два числа называются взаимно простыми,если у них нет общих множителей кроме 1. Иными словами, е с-ли наибольший общий делительа и п равен 1. Это записываетс
Обратные значения по модулю
Помните, что такое обратные значения? Обратное значение для 4 - 1/4, потому что 4*1/4 =1. В мире вычетов проблема усложняется:
4*х = 1 (mod 7)
Это уравнение эквивалентно об
Квадратичные вычеты
Если/; - простое число, и а больше 0, но меньше р, то а представляет собой квадратичный вычет по модулю р, если
х2 = a (mod/;), для некоторых
Символ Лежандра
Символ Лежандра, Ца,р), определен, если а - это любое целое число, а р - простое число, большее, чем 2. Он равен 0, 1 или-1.
Ца,р) = 0, если а делится на р.
Символ Якоби
Символ Якоби, ](а,п), представляет собой обобщение символа Лежандра на составные модули, он определ я-ется для любого целого а и любого нечетного целого п. Функция удобна при п
Генераторы
Если р - простое число, и g меньше, чем р, то g называется генераторомпо модулю р, если для каждого числа Ъ от 1 тр - 1 существует
Квадратные корни по модулю п
Если п - произведение двух простых чисел, то возможность вычислить квадратные корни по модулю п вычислительно эквивалентна возможности разложить число п на множители [1283, 35
Solovay-Strassen
Роберт Соловэй (Robert Solovay) и Фолькер Штрассен (Volker Strassen) разработали алгоритм вероятностной проверки простоты числа [1490]. Для проверки простоты числа р этот алгоритм использует
Lehmann
Другой, более простой тест был независимо разработан Леманном (Lehmann) [903]. Вот последовательность действий при проверке простоты числа р:
(1) Выберите случайно число а, м
Rabin-Miller
Повсеместно используемым является простой алгоритм, разработанный Майклом Рабином (Michael Rabin), частично основанным на идеях Гэри Миллера [1093, 1284]. По сути, это упрощенная версия алгоритма,
Практические соображения
В реальных приложениях генерация простых чисел происходит быстро.
(1) Сгенерируйте случайное и-битовое число/;.
(2) Установите старший и младший биты равными 1. (Старший бит гаран
Сильные простые числа
Если п - произведение двух простых чисел, р и q, то может понадобиться использовать в качестве р и q сильные простые числа.Такие простые числа об
Вычисление дискретных логарифмов в конечной группе
Криптографы интересуются дискретными логарифмами следующих трех групп:
— Мультипликативная группа полей простых чисел: G¥(p)
— Мультипликативная группа конечных полей с
Разработка стандарта
В начале 70-х годов невоенные криптографические исследования были крайне редки. В этой области почти не публиковалось исследовательских работ. Большинство людей знали, что для своих коммуникаций во
Принятие стандарта
Американский национальный институт стандартов (American National Standards Institute, ANSI) одобрил DES в качестве стандарта для частного сектора в 1981 году (ANSI X3.92.) [50], назвав его Алгоритм
Проверка и сертификация оборудования DES
Частью стандарта DES является проверка NIST реализаций DES. Эта проверка подтверждает, что реализ а-ция соответствует стандарту. До 1994 года NIST проверял только аппаратные и программно-аппаратные
Заключительная перестановка
Заключительная перестановка является обратной по отношению к начальной перестановки и описана в 4-й. Обратите внимание, что левая и правая половины не меняются местами после последнего этапа DES, в
Дешифрирование DES
После всех подстановок, перестановок, операций XOR и циклических сдвигов можно подумать, что алг о-ритм дешифрирования, резко отличаясь от алгоритма шифрования, точно также запутан. Напротив, разли
Режимы DES
FIPS PUB 81 определяет четыре режима работы: ЕСВ, СВС, OFB и CFB (см. главу 9) [1143]. Банковские стандарты ANSI определяют для шифрования ЕСВ и СВС, а для проверки подлинности - СВС и n-битовый CF
Аппаратные и программные реализации DES
Об эффективных аппаратных и программных реализациях алгоритма много писалось [997, 81, 533, 534, 437, 738, 1573, 176, 271, 1572]. Утверждается, что самой быстрой является микросхема DES, разработан
Ключи-дополнения
Выполним побитное дополнение ключа, заменяя все 0 на 1 и все 1 - на 0. Теперь, если блок открытого текста зашифрован оригинальным ключом, то дополнение ключа при шифровании превратит дополнение бло
Алгебраическая структура
Все возможные 64-битовые блоки открытого текста можно отобразить на 64-битовые блоки шифротекста
264! Различными способами. Алгоритм DES, используя 56-битовый ключ, предост
Количество этапов
Почему 16 этапов? Почему не 32? После пяти этапов каждый бит шифротекста является функцией всех б и-тов открытого текста и всех битов ключа [1078, 1080], а после восьми этапов шифротекст по сути пр
Проектирование S-блоков
Помимо уменьшения длины ключа NSA также обвиняют в изменении содержания S-блоков. Настаивая на подтверждении схемы S-блоков, NSA заявило, что детали алгоритма являются "чувствительными" и
Дополнительные результаты
Были предприняты и другие попытки криптоанализировать DES. Один из криптографов искал закономерн о-сти, используя спектральные тесты [559]. Другие анализировали последовательность линейных множител
Дифференциальный криптоанализ
В1990 году Эли Бихам и Ади Шамир ввели понятие дифференциального криптоанализа[167, 168, 171, 172]. Это был новый, ранее неизвестный метод криптоанализа. Используя
Криптоанализ со связанными ключами
В 9-й показано количество битов, на которые циклически смещается ключ DES на каждом этапе: на 2 бита на каждом этапе, кроме этапов 1, 2, 9 и 16, когда ключ сдвигается на 1 бит. Почему?
Линейный криптоанализ
Линейный криптоанализпредставляет собой другой тип криптоаналитического вскрытия, изобретенный Мицуру Мацуи (Mitsura Matsui) [1016, 1015, 1017]. Это вскрытие использует линейные пр
Дальнейшие направления
Был предпринят ряд попыток расширить концепцию дифференциального криптоанализа на дифференциалы более высоких порядков [702, 161, 927, 858, 860]. Ларе Кнудсен (Lars Knudsen) использует нечто, назыв
Многократный DES
В ряде реализаций DES используется трехкратный DES (см. 2-й) [55]. Так как DES e является группой, полученный шифротекст гораздо сложнее вскрыть, используя исчерпывающий поиск: 2 112 по
Обобщенный DES
Обобщенный DES (Generalized DES, GDES) был спроектирован для ускорения DES и повышения устойч и-вости алгоритма [1381, 1382]. Общий размер блока увеличился, а количество вычислений осталось неизме
MADRYGA
В.Е. Мадрига (W. E. Madryga) предложил этот блочный алгоритм в 1984 году [999]. Он может быть эффе к-тивно реализован как программа: в нем нет надоедливых перестановок, и все операции выполняются н
Описание Madryga
Madryga состоит из двух вложенных циклов. Внешний цикл повторяется восемь раз (но это количество м о-жет быть увеличено для повышения) и содержит применение внутреннего цикла к открытому тексту. Вн
Криптоанализ и Madryga
Исследователи из Технического университета в Квинсланде (Queensland University of Technology) [675] и с-следовали Madryga вместе с некоторыми другими блочными шифрами. Они обнаружили, что в этом ал
Описание FEAL
На 10-й представлена блок-схема одного этапа FEAL. В качестве входа процесса шифрования используется 64-битовый блок открытого текста. Сначала блок данных подвергается операции XOR с 64 битами ключ
Криптоанализ FEAL
Успешный криптоанализ FEAL-4, FEAL с четырьмя этапами, был выполнен с помощью вскрытия с выбра н-ными открытыми текстами [201], а позже слабость этого алгоритма была показана в [1132]. Последнее вс
Патенты
FEAL запатентован в Соединенных Штатах [1438], соответствующие патенты приняты к рассмотрению в Англии, Франции и Германии. Желающий лицензировать использование алгоритма должен связаться с Дера п-
REDOC III
REDOC представляет собой упрощенную версию REDOC II, также разработанную Майклом Вудом [1615]. Он работает с 80-битовым блоком. Длина ключа может меняться и достигать 2560 байтов (20480 битов). Алг
Описание LOKI91
Механизм LOKI91 похож на DES (см. Рис. 13-8). Блок данных делится на левую и правую половины и пр о-ходит через 16 этапов, что очень походе на DES. На каждом этапе правая половина сначала подвергае
Криптоанализ LOKI91
Кнудсен предпринял попытку криптоанализа LOKI91 [854, 858], но нашел, что этот алгоритм устойчив к дифференциальному криптоанализу. Однако ему удалось обнаружить, что вскрытие со связанными ключами
Патенты и лицензии
LOKI не запатентован. Кто угодно может реализовать алгоритм и использовать его. Исходный код, прив е-денный в этой книге, написан в Университете Нового Южного Уэльса. При желании использовать эту р
KHUFU и KHAFRE
В 1990 году Ральф Меркл (Ralph Merkle) предложил два алгоритма. В основе их проектирования лежали следующие принципы [1071]:
1. 56-битовый размер ключа DES слишком мал. Так как стоимость у
Патенты
И Khufu, и Khafre запатентованы [1072]. Исходный код этих алгоритмов содержится в патенте. При желании получить лицензию на любой или оба алгоритма следует обратиться к директору по лицензированию
Скорость IDEA
Современные программные реализации IDEA примерно в два раза быстрее, чем DES. На компьютере с i386/33 МГц IDEA шифрует данные со скоростью 880 Кбит/с, а на компьютере с i486/33 МГц - со скоростью 2
Криптоанализ IDEA
Длина ключа IDEA равна 128 битам - более чем в два раза длиннее ключа DES. При условии, что наиболее эффективным является вскрытие грубой силой, для вскрытия ключа потребуется 2 128 (10
Патенты и лицензии
IDEA запатентован в Европе и Соединенных Штатах [1012, 1013]. Патент принадлежит Ascom-Tech AG. Для некоммерческого использования лицензирование не нужно. При заинтересованности в лицензии для ко м
Описание ГОСТ
ГОСТ является 64-битовым алгоритмом с 256-битовым ключом. ГОСТ также использует дополнительный ключ, который рассматривается ниже. В процессе работы алгоритма на 32 этапах последовательно выполняет
Криптоанализ ГОСТ
Вот главные различия между DES и COST.
— DES использует сложную процедуру для генерации подключей из ключей. В ГОСТ эта процедура очень проста.
— В DES 56-битовый ключ, а в ГОСТ -
BLOWFISH
Blowfish - это алгоритм, разработанный лично мной для реализации на больших микропроцессорах [1388, 1389]. Алгоритм незапатентован, и его код на языке С приведен в конце этой книги для широкого пол
Безопасность Blowfish
Серж Воденэ (Serge Vaudenay) исследовал Blowfish с известными S-блоками и г этапами, дифференциал ь-ный криптоанализ может раскрыть Р-массив с помощью 2 8Ж выбранных открытых текстов [15
Описание SAFER K-64
Блок открытого текста делится на восемь байтовых подблоков: Въ В2, . . . , Въ В%. Затем подблоки обрабатываются в ходе г этапов. Наконец подблоки
SAFER K-128
Этот альтернативный способ использования ключа был разработан Министерством внутренних дел Синг а-пура, а затем был встроен Массеем в SAFER [1010]. В этом способе используются два ключа, Ка
Безопасность SAFER K-64
Массей показал, что SAFER K-64 после 6 этапов абсолютно защищен от дифференциального криптоанализа после 8 этапов и достаточно безопасен. Уже после 3 этапов против этого алгоритма становится неэффе
Описание S-Way
Этот алгоритм описать несложно. Для шифрования блока открытого текста х: For i = 0 to n - 1
х = х XOR Ki х = theta (х) х = pi - 1 (х) х = gamma (x) х = pi - 2
Сети Фейстела
Большинство блочных алгоритмов являются сетями Фейстела(Felstel networks). Эта идея датируется началом 70-х годов [552, 553]. Возьмите блок длиной п и разделите его на две
Простые соотношения
DES обладает следующим свойством: если Е^Р) = С, то ЕК{РГ) = С, где Р', С" и К' - побитовые дополнения Р,СиК. Это свойство вдвое уменьш
Групповая структура
При изучении алгоритма возникает вопрос, не образует ли он группу. Элементами группы являются блоки шифротекста для каждого возможного ключа, а групповой операцией является композиция. Изучение гру
Устойчивость к дифференциальному и линейному криптоанализу
Исследование дифференциального и линейного криптоанализа значительно прояснило теорию проектиров а-ния хорошего блочного шифра. Авторы IDEA ввели понятие дифференциалов,обобщение о
Проектирование S-блоков
Сила большинства сетей Фейстела - и особенно их устойчивость к дифференциальному и линейному кри п-тоанализу - непосредственно связана с их S-блоками. Это явилось причиной потока исследований, что
Проектирование блочного шифра
Проектировать блочный шифр нетрудно. Если вы рассматривает 64-битовый блочный шифр как перестано в-ку 64-битовых чисел, ясно, что почти все эти перестановки безопасны. Трудность состоит в проектиро
Luby-Rackoff
Майкл Любы (Michael Luby) и Чарльз Ракофф (Charles Rackoff) показали, что Каш не является безопасным [992]. Рассмотрим два одноблочных сообщения: АВ и АС. Если криптоаналитику известн
Шифр краткого содержания сообщения
Шифр краткого содержания coo6nieHM(Message Digest Cipher, M DC), изобретенный Питером Гутманном (Peter Cutmann) [676], представляет собой способ превратить однонаправленные хэш-функции в
Безопасность шифров, основанных на однонаправленных хэш-функциях
Хотя эти конструкции и могут быть безопасными, они зависят от используемой однонаправленной хэш-функции. Хорошая однонаправленная хэш-функция не обязательно дает безопасный алгоритм шифрования. Сущ
Новости и инфо для студентов