Перестановка с помощью Р-блоков

123 4 56789 10 1112131415 16 1718192021 22 2324

Nd

v __ у_

У ___ У- __ У

У ___ У- __ У-

У __ у_

Рис. 12-3. Перестановка с расширением.

Хотя выходной блок больше входного, каждый входной блок генерирует уникальный выходной блок.

Табл. 12-5. Перестановка с расширением

32,	1,	2,	з,	4,	5,	4,	5,	6,	7,	8,	9,
8,	9,	10,	И,	12.,	13,	12,	13,	14,	15,	16,	17,
16,	17,	18,	19,	20,	21,	20,	21,	22,	23,	24,	25,
24,	25,	26,	27,	28,	29,	28,	29,	30,	31,	32,

Подстановка с помощью S-блоков

После объединения сжатого блока с расширенным блоком с помощью XOR над 48-битовым результатом выполняется операция подстановки. Подстановки производятся в восьми блоках подстановки, или S-блоках (от substitution). У каждого S-блока 6-битовый вход и 4-битовый выход, всего используется восемь различных S-блоков. (Для восьми S-блоков DES потребуется 256 байтов памяти.) 48 битов делятся на восемь 6-битовых подблока. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок - S-блоком 1, вт о-рой - S-блоком 2, и так далее. См. 8-й.

46-битовый вход

32-битовый выход

Рис. 12-4. Подстановка - S-блоки.

Каждый S-блок представляет собой таблицу из 2 строк и 16 столбцов. Каждый элемент в блоке является 4-битовым числом. По 6 входным битам S-блока определяется, под какими номерами столбцов и строк искать выходное значение. Все восемь S-блоков показаны в 6-й.

						Табл. 12-6. S-блоки
S-блок 1:
14, 4,	13,	1,	2,	15,	И,	8, 3,	10,	6,	12.,	5,	9,	0,	7,
0, 15,	7,	4,	14,	2,	13,	1, Ю,	6,	12.,	И,	9,	5,	з,	8,

4, 1,	14,	8,	13,	6,	2,	И,	15,	12,	9,	7,	з,	10,	5,	0,
15, 12,	8,	2,	4,	9,	1,	7,	5,	И,	з,	14,	10,	о,	6,	13,
S-блок 2:
15, 1,	8,	14,	6,	И,	з,	4,	9,	7,	2,	13,	12,	о,	5,	10,
3, 13,	4,	7,	15,	2,	8,	14,	12,	0,	1,	10,	6,	9,	И,	5,
0, 14,	7,	И,	10,	4,	13,	1,	5,	8,	12,	6,	9,	з,	2,	15,
13, 8,	10,	1,	з,	15,	4,	2,	И,	6,	7,	12,	0,	5,	14,	9,
S-блок 3:
10, 0,	9,	14,	6,	з,	15,	5,	1,	13,	12,	7,	И,	4,	2,	8,
13, 7,	0,	9,	з,	4,	6,	10,	2,	8,	5,	14,	12,	И,	15,	1,
13, 6,	4,	9,	8,	15,	з,	0,	И,	1,	2,	12,	5,	10,	14,	7,
1, 10,	13,	0,	6,	9,	8,	7,	4,	15,	14,	з,	И,	5,	2,	12,
S-блок 4:
7, 13,	14,	з,	о,	6,	9,	10,	1,	2,	8,	5,	И,	12,	4,	15,
13, 8,	И,	5,	6.	15,	0,	з,	4,	7,	2,	12,	1,	10,	14,	9,
10, 6,	9,	0,	12,	И,	7,	13,	15,	1,	з,	14,	5,	2,	8,	4,
3, 15,	0,	6,	10,	1,	13,	8,	9,	4,	5,	И,	12,	7,	2,	14,
S-блок 5:
2, 12,	4,	1,	7,	10,	И,	6,	8,	5,	з,	15,	13,	0,	14,	9,
14, И,	2,	12,	4,	7,	13,	1,	5,	0,	15,	10,	з,	9,	8,	6,
4, 2,	1,	И,	10,	13,	7,	8,	15,	9,	12,	5,	6,	з,	0,	14,
И, 8,	12,	7,	1,	14,	2,	13,	6,	15,	0,	9,	10,	4,	5,	з,
S-блок 6:
12, 1,	10,	15,	9,	2,	6,	8,	0,	13,	з,	4,	14,	7,	5,	И,
10, 15,	4,	2,	7,	12,	9,	5,	6,	1,	13,	14,	0,	И,	з,	8,
9, 14,	15,	5,	2,	8,	12,	з,	7,	0,	4,	10,	1,	13,	И,	6,
4, 3,	2,	12,	9,	5,	15,	10,	И,	14,	1,	7,	6,	о,	8,	13,
S-блок 7:
4, И,	2,	14,	15,	0,	8,	13,	з,	12,	9,	7,	5,	10,	6,	1,
13, 0,	И,	7,	4,	9,	1,	10,	14,	з,	5,	12,	2,	15,	8,	6,
1, 4,	И,	13,	12,	з,	7,	14,	10,	15,	6,	8,	0,	5,	9,	2,
6, И,	13,	8,	1,	4,	10,	7,	9,	5,	0,	15,	14,	2,	з,	12,
S-блок 8:
13, 2,	8,	4,	6,	15,	И,	1,	10,	9,	з,	14,	5,	0,	12,	7,
1, 15,	13,	8,	10,	з,	7,	4,	12,	5,	6,	И,	0,	14,	9,	2,
7, И,	4,	1,	9,	12,	14,	2,	0,	6,	10,	13,	15,	з,	5,	8,
2, 1,	14,	7,	4,	10,	8,	13,	15,	12,	9,	0,	з,	5,	6,	И

Входные биты особым образом определяют элемент S-блока. Рассмотрим 6-битовый вход S-блока: Ъ_ъ Ъ₂, Ъ_ъ, Ь₄, Ь₅ и Ь₆. Биты Ъ_х и Ь₆ объединяются, образуя 2-битовое число от 0 до 3, соответствующее строке таблицы. Средние 4 бита, с Ь₂ по Ь₅, объединяются, образуя 4-битовое число от 0 до 15, соответствующее столбцу табл и-

цы.

Например, пусть на вход шестого S-блока (т.е., биты функции XOR с 31 по 36) попадает 110011. Первый и последний бит, объединяясь, образуют И, что соответствует строке 3 шестого S-блока. Средние 4 бита образ у-ют 1001, что соответствует столбцу 9 того же S-блока. Элемент S-блока 6, находящийся на пересечении строки 3 и столбца 9, - это 14. (Не забывайте, что строки и столбцы нумеруются с 0, а не с 1.) Вместо 110011 подста в-ляется 1110.

Конечно же, намного легче реализовать S-блоки программно в виде массивов с 64 элементами. Для этого потребуется переупорядочить элементы, что не является трудной задачей. (Изменить индексы, не изменяя пор я-док элементов, недостаточно. S-блоки спроектированы очень тщательно.) Однако такой способ описания S-блоков помогает понять, как они работают. Каждый S-блок можно рассматривать как функцию подстановки 4-битового элемента: Ь₂ по ^являются входом, а некоторое 4-битовое число - результатом. Биты Ъ_г и Ь₆ опреде­ляются соседними блоками, они определяют одну из четырех функций подстановки, возможных в данном S-блоке.

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

В результате этого этапа подстановки получаются восемь 4-битовых блоков, которые вновь объединяются в единый 32-битовый блок. Этот блок поступает на вход следующего этапа - перестановки с помощью Р-блоков.

32-битовый выход подстановки с помощью S-блоков, перетасовываются в соответствии с Р-блоком. Эта п е-рестановка перемещает каждый входной бит в другую позицию, ни один бит не используется дважды, и ни один бит не игнорируется. Этот процесс называется прямой перестановкой или просто перестановкой. Позиции, в которые перемещаются биты, показаны в 5-й. Например, бит 21 перемещается в позицию 4, а бит 4 - в позицию 31.

Табл. 12-7. Перестановка с помощью P-блоков

16, Т, 20^ 2й 29^ \2, 28^ \П, 1^ \5, 23^ 26^ 5^ 18^ Ъ\, W,

2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, И, 4, 25

Наконец, результат перестановки с помощью Р-блока объединяется посредством XOR с левой половиной первоначального 64-битового блока. Затем левая и правая половины меняются местами, и начинается следу то­щий этап.

Дата добавления: 2014-11-29