Основы теории принятая статистических решений 1051 79 страница

14.3.2. Подстановка

Технология шифрования с помощью подстановки, например использование шиф­ра Цезаря и прогрессивного ключа шифрования Тритемиуса, широко использует­ся в головоломках. Такие простые подстановочные шифры дают малую защищен­ность. Чтобы к подстановочной технологии можно было применить концепцию смешения, требуется более сложное соотношение. На рис. 14.6 изображен пример создания большей подстановочной сложности с помощью использования нели­нейного преобразования. В общем случае п входных битов сначала представляют­ся как один из 2" различных символов (на приведенном рисунке п = 2). Затем множество из 2"символов перемешивается так, чтобы каждый символ заменялся другим символом множества. После этого символ снова превращается в п- битовый.

Можно легко показать, что существует (2^я)! различные подстановки или свя­занные с ними возможные модели. Задача криптоаналитика становится вычисли­тельно невозможной для больших п. Пусть п = 128, тогда 2" = 10³⁸ и (2")! пред­ставляет собой астрономическое число. Видим, что для п = 128 это преобразова­ние с помощью блока подстановки (substitution block, S-блок) является сложным (запутывающим). Впрочем, хотя S-блок с п = 128 можно считать идеальным, его реализация является невозможной, поскольку она потребует блока с 2п = 10³⁸ контактами.

Чтобы убедиться, что S-блок, приведенный на рис. 14.6, представляет собой нели­нейное преобразование, достаточно использовать теорему о суперпозиции, которая формулируется ниже. Предположим, что

^С=Та+7Ъ (₁₄.21) С =Т(а + Ъ),

где а и Ь — входные элементы, С и С'— выходные элементы, а Г— преобразование. Тогда

Если Г линейно, С=С для всех входных элементов.

Если Г нелинейно, СфС.

Предположим, а = 001 и 6 = 010; тогда, используя преобразование Т, показанное на рис. 14.6, получим следующее:

С=Г(001)® Г(010)=111 0000 = 111,

С = Г(001 0 010) = 7X011) = 110.

Здесь символ © обозначает сложение по модулю 2. Поскольку С* С, S-блок является нелинейным.

При перестановке (транспозиции), буквы исходного открытого текста в сообщении не заменяются другими буквами алфавита, как в классических шифрах, а просто пере­ставляются. Например, слово “THINK” после перестановки может выглядеть как шифрованный текст HKTNI. На рис. 14.7 приведен пример бинарной перестановки данных (линейная операция). Видно, что входные данные просто перемешиваются или переставляются. Преобразование выполняется с помощью блока перестановки (permutation block, P-блок). Технология, используемая сама по себе, имеет один ос­новной недостаток: она уязвима по отношению к обманным сообщениям. Обманное сообщение изображено на рис. 14.7. Подача на вход единственной 1 (при остальных 0) позволяет обнаружить одну из внутренних связей. Если криптоаналитику необхо­димо выполнить криптоанализ такой системы с помощью атаки открытого текста, он отправит последовательность таких обманных сообщений, при каждой передаче сме­щая единственную 1 на одну позицию. Таким образом, обнаруживаются все связи входа и выхода. Данный пример показывает, почему защищенность системы не долж­на зависеть от ее архитектуры.

14.3.4. Продукционный шифр

Для преобразований, включающих значительное число «-символьных сообщений, жела­тельным является применение обеих описанных выше схем (S-блока и P-блока). Шеннон [5] предложил использовать продукционный шифр, или комбинацию преобразований S- и Р- блоков, которые вместе могут дать более мощную систему шифрования, чем каждый из них в отдельности. Этот подход, выборочно использующий преобразования замещения и перестановки, был использован IBM в системе LUCIFER [7, 8] и стал основой нацио­нального стандарта шифрования данных (Data Encryption Standard — DES) [9]. На рис. 14.8 изображены такие комбинации Р- и S-блоков. Дешифрование выполняется об­ратным прогоном данных, при котором используются преобразования, обратные к преоб­разованию каждого S-блока. Систему, изображенную на рис. 14.8, реализовать довольно трудно, поскольку все S-блоки являются различными', случайно генерируемый ключ не­применим и система не дает возможности повторить одну и ту же последовательность опе­раций. Поэтому в системе LUCIFER [8] использовались два различных типа S-блоков, и S₀, которые могли быть общедоступными. Пример такой системы изображен на рис. 14.9. Входные данные преобразуются с помощью последовательности S- и P-блоков, опреде­ляемой ключом. В приведенном примере ключ размером 25 бит определяет, какой из двух блоков (Si или S₀) следует выбрать на каждой из 25 позиций схемы. Таким образом, под­робности аппарата шифрования могут быть открыты, поскольку защищенность системы обеспечивается ключом.

  Пример двоичного ключа 1010001011111011010111010 Рис. 14.9. Индивидуальные возможности, определяемые ключом

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

14.3.5. Стандарт шифрования данных

В 1977 году Национальное бюро стандартов США (National Bureau of Standards) приняло модифицированную систему LUCIFER в качестве Национального стан­дарта шифрования данных (Data Encryption Standard — DES) [9]. Как показано на рис. 14.10, с точки зрения системы ввода-вывода DES может считаться блочной системой шифрования с алфавитом в 2⁶⁴ символа. Входной блок из 64 бит, кото­рый является в этом алфавите символом открытого текста, заменяется новым символом шифрованного текста. На рис. 14.11 в виде блочной диаграммы показа­ны функции системы. Алгоритм шифрования начинается с начальной переста­новки 64 бит открытого текста, описанной в таблице начальной перестановки (табл. 14.1). Таблица начальной перестановки читается слева направо и сверху вниз, так что после перестановки биты х_х, х₂,..., х₆₄ превращаются в х₅₈, х₅₀, х₇. После этой начальной перестановки начинается основная часть алгоритма шиф­рования, состоящая из 16 итераций, которые используют стандартный блок, пока­занный на рис. 14.12. Для преобразования 64 бит входных данных в 64 бит вы­ходных, определенных как 32 бит левой половины и 32 бит правой, стандартный блок использует 48 бит ключа. Выход каждого стандартного блока становится входом следующего стандартного блока. Входные 32 бит правой половины (R, _,) без изменений подаются на выход и становятся 32 бит левой половины (L,). Эти R,-j бит с помощью таблицы расширения (табл. 14.2) также расширяются и пре­образуются в 48 бит, после чего суммируются по модулю 2 с 48 бит ключа. Как и в случае таблицы начальной перестановки, таблица расширения читается слева направо и сверху вниз.

Ключ

56 бит

DES ----------- Шифрованный текст

бит

Рис. 14.10. Стандарт шифрования данных (DES) в виде блочной системы шифрования

64-битовый ключ

Выбор перестановки 1

56-битовый ключ

28-битовый блок Do
Левый	сдвиг

К,

32 бит

32 бит

Рис. 14.12. Стандартный компоновочный блок

Таблица 14.1. Начальная перестановка

Таблица 14.2. Таблица расширения

Данная таблица расширяет биты
		/?,_!=*!, ХЪ...,*32
в биты
		(Л, - i)e - *32. •••,	*1, *2> •••> *32>			(14.22)

Отметим, что биты, обозначенные в первом и последнем столбцах таблицы расшире­ния, — это те битовые разряды, которые дважды использовались для расширения от 32 до 48 бит.

Далее (/?,_ i)_£ суммируется по модулю 2 с /-м ключом, выбор которого описывается позднее, а результат разделяется на восемь 6-битовых блоков.

В\, В2,..., В$

Иными словами,

Каждый из восьми 6-битовых блоков В_} используется как вход функции S-блока, воз­вращающей 4-битовый блок Sj{Bj). Таким образом, входные 48 бит с помощью функции S-блока преобразуются в 32 бит. Функция отображения S-блока Sj определена в табл. 14.3. Преобразование В_} = Ь_и Ь₂, Ь₃, Ь_л, Ь₅, Ь₆ выполняется следующим образом. Нужная строка — это Ьф₆, а нужный столбец — Ь₂Ьф₄Ь₅. Например, если Ь_{ = 110001, то преобразование юзвращает значение из строки 3, столбца 8, т.е. число 5 (в двоичной записи 0101). 32-битовый блок, полученный на выходе S-блока, переставляется с ис­пользованием таблицы перестановки (табл. 14.4). Как и другие таблицы, P-таблица чи­тается слева направо и сверху вниз, так что в результате перестановки битов х_1; х₂,..., х₃₂ получаем х₁₆, х₇,..., х₂₅. 32-битовый выход Р-таблицы суммируется по модулю 2 с 32 бит левой половины образуя выходные 32 бит правой половины (Л,).

Таблица 14.3. Функции выбора S-блока

Столбец

Строка

S,

И

s2

S3

I

S*

s5

И

И

s6

Столбец

Строка

s7

S8

Таблица 14.4. Таблица перестановки

Алгоритм стандартного блока может быть представлен следующим образом:

L, = R,._X, (14.24)

R_l=L,-_l®fl.R,._l,Kd. (14.25)

Здесь Дй,-1, К,) обозначает функциональное соотношение, включающее описанные выше расширение, преобразование в 5-блоке и перестановку. После 16 итераций в та­ких стандартных блоках данные размещаются согласно окончательной обратной пере­становке, описанной в табл. 14.5, где, как и ранее, выходные биты читаются слева на­право и сверху вниз.

Таблица 14.5. Окончательная перестановка

Для дешифрования применяется тот же алгоритм, но ключевая последователь­ность, используемая в стандартном блоке, берется в обратном порядке. Отметим, что

значение ДЛ, _ _lt А",), которое может быть также выражено через выход i-го блока как J{L_h Ki), делает процесс дешифрования возможным.

14.3.5.1. Выбор ключа

Выбор ключа также происходит в течение 16 итераций, как показано в соответст­вующей части рис. 14.11. Входной ключ состоит из 64-битового блока с 8 бит четно­сти в разрядах 8, 16,..., 64. Перестановочный выбор 1 отбрасывает биты четности и переставляет оставшиеся 56 бит согласно табл. 14.6. Выход данной процедуры делится пополам на два элемента — С и D, каждый из которых состоит из 28 бит. Выбор клю­ча проходит в 16 итерациях, проводимых для создания различных множеств 48 ключе­вых бит для каждой итерации шифрования. Блоки С и D последовательно сдвигаются согласно следующим выражениям:

Таблица 14.6. Круговая перестановка

		с,		и Д = LS,(D^i).		(14.26)

Здесь LSi — левый циклический сдвиг на число позиций, показанных в табл. 14.7. За­тем последовательность С„ D, переставляется согласно перестановочному выбору 2, показанному в табл. 14.8. Результатом является ключевая последовательность K_h кото­рая используется в i-Pi итерации алгоритма шифрования.

Таблица 14.7. Ключевая последовательность сдвигов влево Итерация i Количество сдвигов влево

ЛОЛ

	Итерация /			Количество сдвигов влево
Таблица 14.8.	Ключевая	перестановка 2

DES может реализовываться подобно блочной системе шифрования (см. рис. 14.11), что иногда называют методом шифровальной книги. Основным недостатком этого метода является то, что (при использовании одного ключа) данный блок входного открытого тек­ста будет всегда давать тот же выходной шифрованный блок. Еще один способ шифрова­ния, называемый способом шифрования с обратной связью, приводит к шифрованию от­дельных битов, а не символов, что дает поточное шифрование [3]. В системе шифрования с обратной связью (описанной ниже) шифрование сегмента открытого текста зависит не только от ключа и текущих данных, но и от некоторых предшествующих данных.

С конца 1970-х широко обсуждались два спорных момента, связанных с DES [10]. Первый касается длины ключа. Некоторые исследователи считали, что 56 бит не достаточ­но, чтобы исключить взлом путем перебора. Второй момент касается внутренней структу­ры 5-блоков, которые никогда не выпускались IBM. Агентство национальной безопасно­сти США, которое было привлечено к тестированию алгоритма DES, потребовало, чтобы эта информация не обсуждалась публично. Критики опасаются, что АНБ участвовало в проектировании этих схем и теперь способно “проникать” в любое сообщение, шифро­ванное согласно DES [10]. В настоящее время стандарт DES больше не является приемле­мым выбором, обеспечивающим надежное шифрование. Поиск 56-битового ключа с по­мощью недорогих компьютерных методов является делом нескольких дней [11]. (Некоторые альтернативные алгоритмы обсуждаются в разделе 14.6.)

Дата добавления: 2015-10-28