Структура алгоритма DES

Рисунок 4.1. Структура алгоритма DES

Алгоритм DES также использует комбинацию подстановок и перестановок. DES осуществляет шифрование 64-битовых бло­ков данных с помощью 64-битового ключа, в котором значащими являются 56 бит (остальные 8 бит - проверочные биты для кон­троля на четность).

Процесс шифрования заключается в начальной перес­та­новке битов 64-битового блока, шестнадцати циклах шифрования в сети Фейстеля и в конечной перестановке битов. Дешифрование в DES является операцией, обратной шифрованию, и выполняется путем повторения опера­ций шифрования в обратной пос­ледовательности.

Все приводимые таблицы яв­ляются стандартными и должны вклю­чаться в реализацию алго­ритма DES в неизменном виде.

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

L и R - последовательности битов (левая (Left) и правая (R i ght));

LR - конкатенация последовательностей L и R.

Å - операция побитового сложения по модулю 2 (операция XOR).

Пусть из файла исходного текс­та счи­тан очередной 64-битовый (8-байто­вый) блок Т. Этот блок Т преобразуется с помо­щью матрицы начальной пере­станов­ки IР (см. табл. 4.1), которая имеет размер­ность 8х8 и представляет собой записанные по строчкам новые номера битов.

Перестановка перемещает каж­дый входной бит в другую позицию, ни один бит не используется дважды и ни один бит не игнорируется. Например, бит 58 входного блока Т становится битом 1, бит 50 - битом 2 и т.д. Эту перестановку можно описать выражением Т = IР (T).

Полученная последовательность битов Т ₀ разделяется на две по 32 бита: L ₀ - левые (старшие) и R ₀-правые (младшие) биты. Затем выпо­лняется итеративный процесс шифрования, состоящий из 16 циклов.

Пусть Т_i - результат i -й итерации:

T_i = L_iR_i,

где L_i = t₁ t₂... t₃₂ (первые 32 бита); R_i = t₃₃ t₃₄... t₆₄ (последние 32 бита). Тогда результат i -й итерации описывается следующими формулами:

L_i = R_{i -1},

R_i = L _{i -1}Å f (R _{i -1}, K _i), i = 1,2,...,16.

Функция f называется функцией шифрования. Ее аргументами являются последовательность R_{i -1}, получаемая на предыдущем шаге итерации, и 48-битовый ключ К _i, который является результатом преобразования 64-битового ключа шифра K. (Подробнее функция шифрования f и алгоритм получения ключа K описаны ниже.)

На последнем шаге итерации получают последовательности R ₁₆ и L ₁₆ (без пере­становки местами), которые конкатенируются в 64-битовую пос­ледовательность R ₁₆ L ₁₆.

По окончании шифрования осу­щес­твля­ет­ся восстановление позиций би­тов с помо­щью матрицы обратной пе­рестановки IР ^-1 (таблица 4.2).

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

Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Он может быть описан следующими формула­ми:        

R_{i -1}= L_i,

L _{i -1}= R_i Å f (L_i, K_i), i = 16,..., 2, 1.

Таким образом, для процесса расшифрования с переставленным входным блоком R ₁₆ L ₁₆ на первой итерации используется ключ K ₁₆, на второй итерации - K ₁₅ и т.д. На 16-й итерации используется ключ K ₁. На последнем шаге итерации будут получены последовательности L o и R o, которые конкатенируются в 64-битовую последовательность L ₀ R ₀. Затем в этой последовательности 64 бита переставляются в соответ­ствии с матрицей IР ^-1. Рeзультат такого преобразования - исходная последовательность битов (расшифрованное 64-битовое значение).

Функция шифрования

Теперь рассмотрим, что скрывается под преобразованием, обозна­ченным буквой f (рис.4.2).

Рисунок 4.2. Схема вычисления функции шифрования f

Аргументами функции шифрования f являются R_{i -1} (32 бита) и K_i (48 бит). Результат функции расширения Е(R_{i -1}) есть 48-бито­вое число Для вычисления значения функции f используются:

-функция Е (расширение 32 бит до 48);

-функции S₁, S₂,..., S₈ (преобразование 6-битового числа в 4-битовое);

-функция Р (перестановка битов в 32-битовой последователь­ности).

Функция расширения Е, выполняющая операцию перестановки с рас­ширением правой половины данных R_i от 32 до 48 битов и изменением их порядка, называется перестановкой с расширением (принимает блок из 32 бит и порождает блок из 48 бит), определяется таблицей 4.3.

У этой операции две задачи: привести раз­мер правой поло­вины в соответствие с клю­чом для операции Å (XOR) и полу­чить более длинный результат, который можно будет сжать в ходе операции подста­новки. Одна­ко криптографический смысл данной операции состо­ит в том, что за счет влияния одного бита на две подстановки быстрее возра­стает зависимость битов результата от битов исходных данных. Данная зависимость называет­ся лавинным эффектом. DES спроек­тирован так, чтобы как можно быстрее добиться зависимости каждого блока шифртекста от каждого бита открыто­го текста и каждого бита ключа.

Полученный после перестановки с расширением результат (обозна­чим его E(R_{i -1})) складывается по модулю 2 с текущим значением ключа K_i и затем разбивается на восемь 6-битовых блоков B₁,..., B₈:

E(R_{i -1})Å K_i =B₁B₂...B₈.

Номер столбца
		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
	1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8	S1
	2	4	1	4	8	13	6	2	11	15	12	9	7	3	10	5	0
	3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13
	0	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
	1	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5	S2
	2	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
	3	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9
	0	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
н	1	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1	S3
о	2	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
м	3	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12
е	0	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
р	1	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9	S4
	2	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
с	3	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14
т	0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
о	1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6	S5
о	2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
к	3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3
и	0	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
	1	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8	S6
	2	9	14	15	5	2	8	12	3	7	0	4	10	1	13	1	6
	3	4	3	2	12	9	5	15	10	11	14	1	7	6	0	8	13
	0	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
	1	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6	S7
	2	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
	3	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12
	0	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
	1	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2	S8
	2	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
	3	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

Таблица 4.4 .Функции преобразования (узлы замены)S₁,...,S₈

Каждый 6-битовый блок B _j преобразуется в 4-битовый блок с помо­щью отображения, заданного таблицами S₁,..., S₈. Эти таблицы называ­ются уз­лами замены (S‑boxes, S‑блоками) и опубликованы вместе с алгоритмом, в то время как критерии их выбора опубликованы не были (см.таблицу 4.4).

Элементами матриц S _i размером 4 строки и 16 столбцов являются числа от 0 до 15, которые в двоичной записи представляют собой 4-би­товые значения.

Совокупность 6-битовых блоков В₁,..., B₈ обеспечивает выбор 4-би­тового элемента (числа 0-15) в каждой из матриц S _i. Каждый блок B _i испо­льзуется для выбора номера элемента в матрице S _i следующим образом.

Пусть на вход матрицы S _i  поступает 6-битовый блок B _j = b₁ b₂ …b₆, тогда:

- двухбитовое число b ₁ b ₆ указывает номер строки матрицы (число от 0 до 3),

- четырехбитовое число b ₂ … b ₅ - номер столбца (число от 0 до 15).

Результаты узлов замены объединяются в один 32-би­товый блок:

S₁(B₁) … S₈(B₈).

Подстановка с помощью узлов замены является ключевым этапом DES. Другие действия алгоритма ли­ней­ны и легко поддаются анализу. S-блоки нелинейны и именно они в боль­шей степени, чем все остальное, обеспечивают криптостойкость DES.

Полученный блок преобра­зуется с помощью фун­кции переста­новки битов Р (матрица 8х4 из табл.4.5).

Таким образом, функция шифрования имеет вид

f (R_i-1, K _i), =Р(S₁(B₁),...,S₈(B₈)).

Генерация ключей

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

На каждой итерации используется новое значение ключа K_i, (длиной 48 бит). Новое значение ключа K_i вычисляется из начального ключа K. Процедура преобразования ключа K сводится к следующим действиям (см. рис.4.3).

Сначала 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита. Это биты, расположенные в позициях 8, 16, 24, 32, 40, 48, 56, 64. Они исполь­зуются для контроля по четности и позволяют проверять правильность ключа. Таким образом, в действите­льности ключ шифра является 56-бито­вым.

 Рисунок 4.3. Схема алгоритма вычисления подключей

Для удаления контрольных битов и подго­товки ключа к работе испо­льзуется функция G(K) первоначальной подго­товки ключа (табл. 4.6). Таблица 4.6 разделена на две части. Результат преобразова­ния G(K) разбивается на две поло­вины Со и Do по 28 бит каждая. Первые четыре строки матрицы G определяют, как выбираются биты последовательно­сти Со (первым битом Со будет бит 57 ключа шифра, затем бит 49 и т.д., а последними битами - биты 44 и 36 ключа).

Следующие четыре строки матрицы G определяют, как выбираются биты последовательности Do (т.е. последовательность Do будет состо­ять из битов 63, 55, 47,...,12, 4 ключа шифра).

После определения С₀ и D₀ рекурсивно определяются С _i, и D _i, i = 1, 2,..., 16. Для этого применяются операции циклического сдвига влево на один или два бита в зависимости от номера шага итерации, как показано в таблице4.7. Операции сдвига выполняются для последовательностей С _i, и D _i независимо.

Таблица 4.7.

Номер итерации	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Количество сдвигов влево (бит)	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

После сдвига выбирается 48 из 56 битов. Итак, ключ К _i, определяе­мый на каждом шаге итерации, есть резуль­тат выбо­ра конкретных битов из 56-битовой последователь­ности С _i D _i и их перестановки. Так как при этом не только выбирается подмножество би­тов, но и изме­няется их по­рядок, эта операция получила название перестановка со сжатием. Её также называют фун­кцией Н завершающей обработки ключа. Функция Н определяется матрицей, приведенной в таблице 4.8.

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

K_i =H(С _i D _i).