Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Блочные алгоритмы шифрования ГОСТ и DES

Шифрование алгоритмом DES

3.1 Краткие теоретические сведения

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

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

Рисунок 3.1 - Обобщенная схема шифрования в алгоритме DES

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

Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс взлома шифра.

Пусть из файла исходного текста считан очередной 64-битовый блок То. Этот блок преобразуется с помощью матрицы начальной перестановки IP (табл. П1).

Биты входного блока Т (64 бита) переставляются в соответствии с матрицей IP: бит 58 входного блока Т становится битом 1, бит 50 - битом 2 и т.д. Эту перестановку можно описать выражением ТО = IР(Т). Полученная последовательность бит То разделяется на две последовательности: Lo - левые, или старшие, биты, Ro - правые, или младшие, биты - каждая из которых содержит 32 бита.

Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов). Пусть Т; - результат i - й итерации: Тi- = Li-Ri -, где Li. = t1, t32… t32 (первые 32 бита); Ri. = t33, t34… t64 (последние 32 бита). Тогда результат i - й итерации описывается следующими формулами: Li = Ri-1, i = 1,2,…, 16; Ri = Li-1 + f (Ri-1, Ki), i = 1,2,…, 16.

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

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

По окончании шифрования осуществляется восстановление позиций бит с помощью матрицы обратной перестановки (табл. П2).

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

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

Ri-1 = Li, i = 1,2,…, 16;

Li-1 = Ri + f (Li, Ki), i = 1,2,…, 16

Таким образом, для процесса расшифровывания с переставленным входным блоком R]6L16 на первой итерации используется ключ К16, на второй итерации - К15 и т.д. На 16-й итерации используется ключ Kj. На последнем шаге итерации будут получены последовательности Lo и Ro, которые конкатенируются в 64-битовую последовательность L0R0. Затем в этой последовательности 64 бита переставляются в соответствии с матрицей IP. Результат такого преобразования - исходная последовательность бит (расшифрованное 64-битовое значение).

Реализация функции шифрования

Схема вычисления функции шифрования f (Ri-1, Ki) показана на рис. 3.2.

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

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

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

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

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

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

Аргументами функции шифрования f являются R i-1 (32 бита) и Кi,-

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

В соответствии с табл. ПЗ первые три бита E(R i-1) - это биты 32, 1 и 2, а последние - 31, 32 и 1. Полученный результат (обозначим его E(R)4)) складывается по модулю 2 с текущим значением ключа Кi и затем разбивается на восемь 6-битовых блоков B1, В2,…, B8 = E (R i-1) + Кi. Далее каждый из этих блоков используется как номер элемента в функциях - матрицах S1, S2,…, S8, содержащих 4-битовые значения (табл. П8).

Следует отметить, что выбор элемента в матрице S осуществляется достаточно оригинальным образом. Пусть на вход матрицы S поступает 6-битовый блок Bj = b1b2b3b4b5b6, тогда 2-битовое число b, b6 указывает номер

строки матрицы, а 4-битовое число b2b3b4b5 - номер столбца. Например, если на вход матрицы S1 поступает 6-битовый блок B1 = b1b2b3b4b5b6 = 100110 (2) то 2-битовое число b1b6 = 10 (2) = 2 (2) указывает строку с номером 2 матрицы S1, a 4-битовое число b2b3b4b5 = 0011 (2) = 3 (10) указывает столбец с номером 3 матрицы Sj. Это означает, что в матрице Sj блок Bj = 100110 выбирает элемент на пересечении строки с номером 2 и столбца с номером 3, т.е. элемент 8 (10) = 1000 (2) Совокупность 6-битовых блоков B1, В2,…, В8 обеспечивает выбор 4-битового элемента в каждой из матриц S1, S2,…, S8.

В результате получаем S1(BI), S2(B1),…, S8(B1), т.е. 32-битовый блок (поскольку матрицы S содержат 4-битовые элементы). Этот 32-битовый блок преобразуется с помощью функции перестановки бит Р (табл. П4). Таким образом, функция шифрования f (Ri-1, Ki) = P(S1(BI), S2(B1),…, S8(B1))

Алгоритм вычисления ключей

Как нетрудно заметить, на каждой итерации используется новое значение ключа Кi - (длиной 48 бит). Новое значение ключа Кi - вычисляется из начального ключа К (рис. 1.3).

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

Табл. П5 разделена на две части. Результат преобразования G(K) разбивается на две половины Со и Do, по 28 бит каждая. Первые четыре строки матрицы G определяют, как выбираются биты последовательности С (первым битом Со будет бит 57 ключа шифра, затем бит 49 и т.д., а последними битами - биты 44 и 36 ключа). Следующие четыре строки матрицы G определяют, как выбираются биты последовательности Do (т.е. последовательность Do будет состоять из бит 63, 55,47,…, 12, 4 ключа шифра),

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

После определения Со и Do рекурсивно определяются Сi и Di; i = 1,2,…, 16. Для этого применяются операции циклического сдвига влево на один или два бита в зависимости от номера шага итерации, как показано в табл. П7.

Операции сдвига выполняются для последовательностей Сi и Di независимо. Например, последовательность С3 получается посредством циклического сдвига влево на две позиции последовательности С2, а последовательность D3 - посредством сдвига влево на две позиции последовательности D2, С и D16 получаются из С15 и D15 посредством сдвига влево на одну позицию.

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

Другими словами, ключ Кi- = H(CiDi), где функция Н определяется матрицей, завершающей обработку ключа (табл. П6).

Как следует из табл. П6, первым битом ключа Кi будет 14-й бит последовательности CiDi, вторым - 17-й бит, 47-м битом ключа Кi будет 29-й бит CiDi, а 48-м битом - 32-й бит CiDi.

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

СКАЧАТЬ ОРИГИНАЛ
Блочные алгоритмы шифрования ГОСТ и DES