Перестановка с помощью Р-блоков
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, Ъъ, Ь4, Ь5 и Ь6. Биты Ъх и Ь6 объединяются, образуя 2-битовое число от 0 до 3, соответствующее строке таблицы. Средние 4 бита, с Ь2 по Ь5, объединяются, образуя 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-битового элемента: Ь2 по ^являются входом, а некоторое 4-битовое число - результатом. Биты Ъг и Ь6 определяются соседними блоками, они определяют одну из четырех функций подстановки, возможных в данном 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-битового блока. Затем левая и правая половины меняются местами, и начинается следу тощий этап.