Главная | Обратная связь

Последовательность преобразований отдельного раунда

Теперь рассмотрим последовательность преобразований, используемую на каждом раунде.

Рис. 5. I-ый раунд DES

64-битный входной блок проходит через 16 раундов, при этом на каждой итерации получается промежуточное 64-битное значение. Левая и правая части каждого промежуточного значения трактуются как отдельные 32-битные значения, обозначенные L и R. Каждую итерацию можно описать следующим образом:

L_i = R_i-1
R_i =L_i-1 F (R_i-1, K_i)

Где обозначает операцию XOR.

Таким образом, выход левой половины L_i равен входу правой половины R_i-1. Выход правой половины R_i является результатом применения операции XOR к L_i-1 и функции F, зависящей от R_i-1 и K_i.

Рассмотрим функцию F более подробно.

R_i, которое подается на вход функции F, имеет длину 32 бита. Вначале R_i расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Расширение происходит следующим образом. 32 бита разбиваются на группы по 4 бита и затем расширяются до 6 битов, присоединяя крайние биты из двух соседних групп. Например, если часть входного сообщения

. . . efgh ijkl mnop . . .

то в результате расширения получается сообщение

. . . defghi hijklm lmnopq . . .

После этого для полученного 48-битного значения выполняется операция XOR с 48-битным подключом K_i. Затем полученное 48-битное значение подается на вход функции подстановки, результатом которой является 32-битное значение.

Подстановка состоит из восьми S-boxes, каждый из которых на входе получает 6 бит, а на выходе создает 4 бита. Эти преобразования определяются специальными таблицами. Первый и последний биты входного значения S-box определяют номер строки в таблице, средние 4 бита определяют номер столбца. Пересечение строки и столбца определяет 4-битный выход. Например, если входом является 011011, то номер строки равен 01 (строка 1) и номер столбца равен 1101 (столбец 13). Значение в строке 1 и столбце 13 равно 5, т.е. выходом является 0101.

Далее полученное 32-битное значение обрабатывается с помощью перестановки Р, целью которой является максимальное переупорядочивание битов, чтобы в следующем раунде шифрования с большой вероятностью каждый бит обрабатывался другим S-box.

Создание подключей

Ключ для отдельного раунда K_i состоит из 48 битов. Ключи K_i получаются по следующему алгоритму. Для 56-битного ключа, используемого на входе алгоритма, вначале выполняется перестановка в соответствии с таблицей Permuted Choice 1 (РС-1). Полученный 56-битный ключ разделяется на две 28-битные части, обозначаемые как C₀ и D₀ соответственно. На каждом раунде C_i и D_i независимо циклически сдвигаются влево на 1 или 2 бита, в зависимости от номера раунда. Полученные значения являются входом следующего раунда. Они также представляют собой вход в Permuted Choice 2 (РС-2), который создает 48-битное выходное значение, являющееся входом функции F (R_i-1, K_i).

Дешифрование

Процесс дешифрования аналогичен процессу шифрования. На входе алгоритма используется зашифрованный текст, но ключи K_i используются в обратной последовательности. K₁₆ используется на первом раунде, K₁ используется на последнем раунде. Пусть выходом i-ого раунда шифрования будет L_i||R_i. Тогда соответствующий вход (16-i)-ого раунда дешифрования будет R_i||L_i.

После последнего раунда процесса расшифрования две половины выхода меняются местами так, чтобы вход заключительной перестановки IP^-1 был R₁₆||L₁₆. Выходом этой стадии является незашифрованный текст.

Проверим корректность процесса дешифрования. Возьмем зашифрованный текст и ключ и используем их в качестве входа в алгоритм. На первом шаге выполним начальную перестановку IP и получим 64-битное значение L^d₀||R^d₀. Известно, что IP и IP^-1 взаимнообратны. Следовательно

L^d₀||R^d₀ = IP (зашифрованный текст)
Зашифрованный текст = IP^-1 (R₁₆||L₁₆)
L^d₀||R^d₀ = IP (IP^-1(R₁₆||L₁₆)) = R₁₆||L₁₆

Таким образом, вход первого раунда процесса дешифрования эквивалентен 32-битному выходу 16-ого раунда процесса шифрования, у которого левая и правая части записаны в обратном порядке.

Теперь мы должны показать, что выход первого раунда процесса дешифрования эквивалентен 32-битному входу 16-ого раунда процесса шифрования. Во-первых, рассмотрим процесс шифрования. Мы видим,что

L₁₆ = R₁₅
R₁₆ = L₁₅ F (R₁₅, K₁₆)

При дешифровании:

L^d₁ = R^d₀ = L₁₆ = R₁₅
R^d₁ = L^d₀ F (R^d₀, K₁₆)
= R₁₆ F (R^d₀, K₁₆)
= (L₁₅ F (R₁₅, K₁₆)) F (R₁₅, K₁₆)

XOR имеет следующие свойства:

(A B) C = A (B C)
D D =0
E 0 = E

Таким образом, мы имеем L^d₁ = R₁₅ и R^d₁ = L₁₅. Следовательно, выход первого раунда процесса дешифрования есть L₁₅||R₁₅, который является перестановкой входа 16-го раунда шифрования. Легко показать, что данное соответствие выполняется все 16 раундов. Мы можем описать этот процесс в общих терминах. Для i-ого раунда шифрующего алгоритма:

L_i = R_i-1
R_i = L_i-1 F (R_i-1, K_i)

Эти равенства можно записать по-другому:

R_i-1 = L_i
L_i-1 = R_i F (R_i-1, K_i) = R_i F (L_i, K_i)

Таким образом, мы описали входы i-ого раунда как функцию выходов.

Выход последней стадии процесса дешифрования есть R₀||L₀. Чтобы входом IP^-1 стадии было L₀||R₀, необходимо поменять местами левую и правую части. Но

IP^-1(L₀||R₀) = IP^-1 (IP (незашифрованный текст)) = незашифрованный текст

Т.е. получаем незашифрованный текст, что и демонстрирует возможность дешифрования DES.

 

21)