Алгоритм шифрования DES

Стандарт шифрования данных DES (Data Encryption Standart) предназначался для использования в гос. учреждениях США для защиты важной но не секретной информации. Фактически стал международным стандартом. Хотя алгоритм создавался около 30 лет назад в США, он до сих пор широко используется в коммерческих приложениях и считается надежным для этих целей.

Основные достоинства алгоритма DES:

- используется только один ключ длиной 56 битов;

- совместимость ПО от разных производителей;

- высокая скорость работы;

- достаточно высокая стойкость алгоритма.

Данный алгоритм использует программа DISKREET из пакета Norton Utilities, предназначенная для создания зашифрованных разделов на диске и многие другие.

Алгоритм DES – это симметричный блочный алгоритм, шифрующий данные 64-битными блоками с помощью 56-битового ключа. Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется только для контроля четности.

Процесс шифрования состоит из: начальной перестановки битов 64-битового блока, шестнадцати циклов (раундов) шифрования и обратной перестановки битов.

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

Рассмотрим структуру алгоритма шифрования DES

Данные обрабатывают 64-битовыми блоками.

Начальная перестановка делается на основе матрицы начальной перестановки IP (Initial Permutation). Данная матрица представляет собой таблицу из 64-х элементов.

Матрица начальной перестановки IP

58 50 42 34 26 18 10 0260 52 44 36 28 20 12 0462 54 46 38 30 22 14 0664 56 48 40 32 24 16 0857 49 41 33 25 17 09 0159 51 43 35 27 19 11 0361 53 45 37 29 21 13 0563 55 47 39 31 23 15 07

В результате перестановки бит 58 становится битом 1, бит 50 становится битом 2 и т.д.

Полученная последовательность битов разделяется на две последовательности по 32 бита: L₀ - левые или старшие биты, R₀ - правые или младшие биты.

Затем выполняется шифрование, состоящее из 16 раундов. Результат i -го раунда описывается следующими формулами:

L_i=R_i-1

R_i=L_i-1 Å f (R_i-1, K_i)

Структура алгоритма шифрования DES

	L0

	Начальная перестановка IP
		R0

		Шифротекст

	R16= L15Åf (R15,K16)		L16= R15

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

- 64-битовый ключ сокращается до 56-битового отбрасыванием каждого 8 бита, которые используются только для контроля четности.

- 56-битовый ключ делится пополам. 28-битовые половины цикличекси сдвигаются налево на один или два байта, в зависимости от раунда согласно специальной таблице.

Таблица сдвигов для вычисления ключа

Номер раунда	Сдвиг (бит)
01020304050607080910111213141516	1122222212222221

- Из полученной последовательности выбираются 48 из 56 битов по заданному правилу, определенному в матрице. Данная операция называется сжимающей перестановкой (т.к. меняется порядок битов и уменьшается их кол-во).

Матрица завершающей обработки ключа

14 17 11 24 01 0503 28 15 06 21 1023 19 12 04 26 0816 07 27 20 13 0241 52 31 37 47 5530 40 51 45 33 4844 49 39 56 34 5346 42 50 36 29 32

Ключ K_i будет состоять из битов 14, 17….32 полученной послед-ти.

Теперь вернемся к самому алгоритму.

f – это функция шифрования. Ее аргументы – 32 битовая послед-ть R_i-1, полученная на i-1 раунде и 48-битовый ключ K_i (который является результатом преобразования 64-битового ключа K).

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

Полученная последовательность подвергается конечной перестановке в соответствии с матрицей IP^-1, обратной матрице IP. Т.е. значение 1-го элемента матрицы IP^-1 равно 40, а значение 40-го элемента матрицы IP равно 1, значение 2-го элемента матрицы IP^-1 равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.

Матрица обратной перестановки IP ^-1

40 08 48 16 56 24 64 3239 07 47 15 55 23 63 3138 06 46 14 54 22 62 3037 05 45 13 53 21 61 2936 04 44 12 52 20 60 2835 03 43 11 51 19 59 2734 02 42 10 50 18 58 2633 01 41 09 49 17 57 25

Теперь рассмотрим функцию шифрования f (R_i-1,K_i)

48 бит

K_i (48 бит)

……………….

	Перестановка битов P

32 бита

f (R_i-1,K_i)

Для вычисления значения функции f используются следующие функции-матрицы:

- Расширитель 32-битовой последовательности до 48-битовой,

- S1, S2,..., S8 - преобразование 6-битового блока в 4-битовый,

- Р - перестановка бит в 32-битовой последовательности.

Функция расширения представляет собой матрицу, которая по определенному правилу перестанавливает биты в последовательнсти R_i-1 и увеличивает ее размер до 48 бит путем повторного использования части битов.

Функция расширения

32 01 02 03 04 0504 05 06 07 08 0908 09 10 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 01

Между полученной послед-тью и 48-битовым ключом K_i производится операция XOR.

Результат этой операции разбивается на восемь 6-битовых блоков, которые обрабатываются функциями S1-S8 согласно таблиц (для каждого S-блока своя таблица).

Таблица каждого S-блока состоит из 4 строк и 16 столбцов. Рассмотрим 6-битовый вход S-блока: b₁,b₂,…b₆. Биты b₁ и b₆ объединяются, образуя 2-битовое число от 0 до 3, соответствующее строке таблицы. Средние 4 бита объединяются, образуя число от 0 до 15, соответсвующее столбцу таблицы. На выходе S-блока – число находящееся на пересечении полученных строки и столбца.

Функции преобразования S1, S2,..., S8

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

Применив операцию выбора к каждому из 6-битовых блоков получаем 32-битовую последовательность.

Для получения результата функции шифрования биты полученной последовательности переставляются по таблице перестановки P. Во входной последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1 и т.д.

Функция перестановки P

16 07 20 2129 12 28 1701 15 23 2605 18 31 1002 08 24 1432 27 03 0919 13 30 0622 11 04 25

Процесс дешифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке, ключи также используются в обратном порядке K₁₆…K₁.

Дата добавления: 2014-01-07