Стандарт шифрования данных (DES)

 

Одним из наиболее распространенных криптографических стандартов на шифрование данных, применяемых в США, является DЕS (Dаtа Еnсгtурtion Stаndаrt). Стандарт шифрования DES был опубликован в 1977 году. Первоначально метод, лежащий в основе данного стандарта, был разработан фирмой IВМ для своих целей. Он был проверен Агентством Национальной Безопасности США, которое не обнаружило в нем статистических или математических изъянов. Это означало, что дешифрация данных, защищенных с помощью DЕS, не могла быть выполнена статистическими (например, с помощью частотного словаря) или математическими ("прокручивание" в обратном направлении) методами.

После этого метод фирмы IВМ был принят в качестве федерального стандарта. Стандарт DЕS используется федеральными департаментами и агентствами для защиты всех достаточно важных данных в ЭВМ (исключая некоторые данные, методы защиты которых определяются специальными актами). Его применяют многие негосударственные институты, в том числе большинство банков и служб обращения денег. Оговоренный в стандарте алгоритм криптографической защиты данных опубликован для того, чтобы большинство пользователей могли использовать проверенный и апробированный алгоритм с хорошей криптостойкостью. Заметим, что, одной стороны, публикация алгоритма нежелательна, поскольку может привести к дешифрации закрытой информации. Но, с другой стороны, это не столь существенно (если стандарт сильный) по сравнению со слабыми методами защиты данных, используемыми государственными институтами. Иначе говоря, потери от публикации алгоритма криптографической защиты намного меньше, чем потеря от применения методов защиты с низкой криптостойкостью. Разумеется, стандартный алгоритм шифрования данных должен обладать такими характеристиками, чтобы его опубликование не сказалось на криптостойкости.

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

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

зашифровав сообщение с помощью одного пакета программ, для расшифровки можно использовать любой другой пакет про­грамм, соответствующий стандарту DES;

относительная простота алгоритма обеспечивает высокую ско­рость обработки;

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

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

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

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

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

LR - конкатенация последовательностей L и R, т.е. такая последовательность битов, длина которой равна сумме длин L R; в последовательности LR биты последовательности R следуют за битами последовательности L;

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

 

 

Рис.15. Обобщенная схема шифрования в алгоритме DES

 

Подробнее процесс шифрования данных поясняет рис. 16.

1. Первоначально каждые 64 бита входной последовательности перестанавливаются в соответствии с табл. 4.1. Таким образом, бит 58 входной последовательности становится битом 1; бит 59 - битом 2 и т.д.

Таблица 4.1

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

 

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

Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов). Пусть Тi- результат i-й итерации:

Ti = L_iR_i,

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

Li = R_i-1, i = 1,2,..., 16;

Ri = L_i-1+f(R_i-1,Ki), i= 1,2,..., 16.

 

 

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

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

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

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

Таблица 4.2

Матрица обратной перестановки

 

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

Итеративный процесс расшифровки может быть описан следующими формулами:

 

R_i-1 = L_i, i = 1,2,…,16;

L_i-1 = R_i + f (L_i, K_i), i=1,2,…, 16.

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

Рассмотрим, что скрывается под преобразованием, обозначенным буквой f. Схема вычисления функции шифрования f (R_i-1,K_i) показана на рис. 17.

 

 

 

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

 

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

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

функции S1, S2,..., S8 (преобразование 6-битового числа в 4-битовое);

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

Рассмотрим определения этих функций.

Аргументами функции шифрования f являются R_i-1 (32 би­та) и К_i (48 бит).

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

Таблица 4.3

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

 

Как видно из табл. 4.3 часть бит (например, 1, 32 и т.д.) повторяются несколько раз; за счет этого 32 бита расширяются до 48 бит.

Полученный результат (обозначим его E(R_i-1)) складывается по модулю 2 (операция XOR) с текущим значением ключа K_i (который состоит из 48 бит) и затем разбивается на восемь 6-битовых блоков Bi, B₂,..., В₈:

 

E(R_i-1)+Ki = B₁B₂... В₈.

 

Далее каждый из этих блоков используется как номер эле­мента в функциях-матрицах S₁, S₂,..., S₈, содержащих 4-битовые значения.

Следует отметить, что выбор элемента в матрице S_j осу­ществляется достаточно оригинальным образом.

Пусть на вход матрицы S_j, поступает 6-битовый блок Bj = b₁ b₂ b₃ b₄ b₅ b₆, тогда двух битовое число b₁b₆ указывает номер строки матрицы, а четырех битовое число Ь₂ Ь₃ b₄ b₅ - номер столбца.

Например, если на вход матрицы S₁ поступает 6-битовый блок В₁= Ь₁ b₂ b₃ b₄ b₅ b₆ = = 100110, то 2-битовое число b₁ b₆ = 10₍₂₎ = 2₁₀ указывает строку с номером 2 матрицы S₁, а 4-битовое число b₂ b₃'b₄ b₅=0011₍₂₎=3(₁₀) указывает столбец с номером 3 матрицы S₁.

Это означает, что в матрице S₁ блок B₁ = 100110 выбирает элемент на пересечении строки с номером 2 и столбца с номером 3, т.е. элемент 8₍₁₀) = =1000_{2). Совокупность 6-битовых блоков B₁, B₂,..., В₈ обеспечивает выбор четырех битового элемента в каждой из матриц S₁, S₂,..., S₈.

В результате получаем S₁(B₁) S₂(B₂) S₃(B₃)... S₈(B₈), т.е. 32-битовый блок (поскольку матрицы S_j содержат 4-битовые элемен­ты). Этот 32-битовый блок преобразуется с помощью функции пе­рестановки битов Р (табл.4.4).

 

Таблица 4.4

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

 

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

f(R_i_₁,K_i) = P(S₁(B₁).............................. S₈(B₈)).

 

На каждой итерации (рис. 16) используется новое значение ключа K_j (длиной 48 бит). Новое значение ключа K_j вычисляется из начального ключа К (рис.18).

 

 

 

Рис. 18. Схема алгоритма вычисления ключей К_i

 

 

Ключ К представ­ляет собой 64-битовый блок с 8 битами контроля по четности, рас­положенными в позициях 8, 16, 24, 32, 40, 48, 56, 64. Для удаления контрольных битов и подготовки ключа к работе используется функция G первоначальной подготовки ключа (табл. 4.5).

Таблица 4.5

Функция G первоначальной подготовки ключа

 

 

 

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

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

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

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

Операции сдвига выполняются для последовательностей С_i и D_i независимо. Например, последовательность С₃ получается посредством циклического сдвига влево на две позиции последо­вательности С₂, а последовательность D₃ - посредством сдвига влево на две позиции последовательности D₂, C₁₆ и D₁₆ получают­ся из C₁₅ и D₁₅ посредством сдвига влево на одну позицию.

Таблица 4.6

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

 

Номер итерации	Количество Si сдвигов влево, бит	Номер итерации	Количество s, сдвигов влево, бит
		9 1

 

Ключ К_j, определяемый на каждом шаге итерации, есть результат выбора конкретных битов из 56-битовой последователь­ности С_j, D_j и их перестановки. Другими словами, ключ К_j =Н(С_j D_j), где функция Н определяется матрицей, завершающей обработку ключа (табл. 4.7).

 

Таблица 4.7

Функция Н завершающей обработки ключа

 

 

Как следует из табл.4.7, первым битом ключа К_j будет 14-й бит последовательности С_j D_j, вторым - 17-й бит, 47-м битом клю­ча К_j будет 29-й бит С_jD_j а 48-м битом - 32-й бит С_jD_j.