Лабораторная работа № 5. Методы криптографии. Реализация режимов стандарта DES

Цель работы

Знакомство с методами реализации основных процедур стандарта DES, приобретение навыков программирования криптографических процедур.

2. Теоретические положения

В 1977 году Национальное бюро стандартов США (NBS) опубликовало стандарт шифрования данных Data Encryption Standart (DES), предназначенный для использования в государственных и правительственных учреждениях США для защиты от несанкционированного доступа важной информации. Алгоритм, положенный в основу стандарта распространялся достаточно быстро, и уже в 1980 году был одобрен ANSI. С этого момента DES превратился в стандарт не только по названию, но и фактически. Появляются программное обеспечение и специализированные микроЭВМ, предназначенные для шифрования/дешифрования информации в сетях передачи данных и на магнитных носителях. К настоящему времени DES является наиболее распространенным алгоритмом, используемом в системах защиты коммерческой информации. Более того, реализация стандарта DES в таких системах является просто признаком хорошего тона. Почему же DES добился такой популярности?

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

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

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

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

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

Информацию о стандарте DES можно найти в книге Хоффмана Л. Дж. и журнале “Монитор”, который в 1992 году опубликовал целую серию статей, посвященных коммерческим системам шифрования. Не стоит удивляться, что начиналась эта серия со статьи о DES.

В нашей стране тоже был разработан стандарт на шифрование данных. Существует даже ГОСТ 28147-89 в котором этот алгоритм изложен полностью. Кстати при изучении этого ГОСТа можно сделать заключение, что отечественный стандарт очень похож на DES.

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

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

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

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

T₀ = IP(T) (1)

Таблица 1

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

Затем шестнадцать раз повторяется процедура шифрования этого блока с помощью функции f. Пусть T_i обозначает результат i-ой операции. Тогда обозначим, что

L_i=t₁…t₃₂, (первые 32 бита) R_i=t₃₃…t₆₄ (последние 32 бита), то есть

T_i=L_iR_i (2)

Тогда результатом i-ой итерации будет

L_i=R_i-1 (3)

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

где: – поразрядная операция исключающее или (^);

K_i – i-е преобразование ключа шифрования.

Функция f выполняет операции над значением R_i-1 (результатом прошлой операции) и текущим значением 48-битового ключа K_i (с отсечением лишних битов). Кстати, после 16-й итерации левая и правая половины блока местами не меняются (рис. 2).

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

Таблица 2

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

Теперь рассмотрим, что же скрывается под преобразованием, скрытым буквой f. На каждой итерации массив R_i-1 с помощью таблицы распределения Е (таблица 4) расширяется до 48 битов.

Таблица 3

Таблица распределения битов Е

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

Полученный результат (обозначим его Е(R_i-1)) складывается по модулю 2 (операция XOR) с текущим значением ключа K_i и затем разбивается на восемь блоков B₁…B_8.

То есть:

E(Ri-1)+Ki=B1B2…B8 (5)

Далее каждый из этих блоков используется как номер элемента в матрицах S1…S8, содержащих четырехбитовые значения (таблица 5).

В результате, применив операцию выбора к каждому из блоков, мы получим:

S1(B₁) S2(B₂) S3(B₃)… S8(B₈)

Этот 32 – битовый блок (матрицы S_j содержат 4 – битовые значения) преобразуется с помощью матрицы перестановки P (таблица 4)

Таблица 4

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

Таким образом,

f(R_i-1,K_i)=P(S1(B₁),…S8(B₈))

Таблица 5

Матрицы преобразования 16 ´ 4 S1…S8

Номер столбца

S1

S2

S3

S4

S5

S6

S7

S8

Общая схема данного участка программы представлена на рис. 4

Рис.4. Вычисление функции F(R_i,K_i)

Следует отметить, что выбор элемента в матрице Sj осуществляется довольно оригинальным образом. Пусть на вход поступает 6-битовый блок Bj=b1b2b3b4b5b6, тогда двухбитовое число b1b6 выбирает строку матрицы, а b2b3b4b5 – номер столбца. Результатом Sj(B_j) будет 4-битовое число, расположенное по указанному адресу.

Например, если B₃ = 100110, тогда необходимо извлечь значение, размещенное в 3-м столбце второй строки, что составит 9.

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

На каждой итерации используется новое значение ключа K_i, которое вычисляется из начального ключа K. K представляет собой 64-битовый блок с восемью битами контроля по четности, расположенными в позициях 8,16,24,32,40,48,56,64.

Для удаления контрольных битов и подготовки ключа к работе используется матрица PC^-1 (таблица 6).

Таблица 6

Матрица первоначальной подготовки ключа PC^-1

Результат преобразования PC^-1 (K) разбивается на две половины C₀ и D₀ по 28 битов каждая. После этого блоки C₀ и D₀ на каждой итерации последовательно сдвигаются влево (циклически). Пусть C_i и D_i обозначают значения, которые были получены на i – й операции:

C_i = LS_i(C_i-1); D_i = LS_i(D_i-1) (6)

где LS_i – представляет собой i-й элемент матрицы сдвига (см. таблицу 7).

Таблица 7

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

Номер итерации	Сдвиг (бит)

Полученное значение вновь “перемешивается” в соответствии с матрицей PC^-2 (таблица 8).

Таблица 8

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

Схема алгоритма вычисления i-й итерации ключа приведена на рис.5.

Рис.5. Алгоритм вычисления ключа

Итак, алгоритм шифрования изложен полностью. Теперь о том, как происходит дешифрование.

Дешифрование в DES является операцией обратной шифрованию и выполняется путем повторения операций шифрования в обратном порядке.

Восстановление исходного текста осуществляется по этому же алгоритму, но вначале используется ключ K-15, затем K-14, и так далее.

3. Задание на работу

Получить вариант задания у преподавателя для разработки конкретной процедуры стандарта DES в интегрированной среде Delphi или C++ Builder.

Вариант	Название процедуры	Обозначение
	Процедура перестановки бит на основе матрицы перестановки	Per(char* in_B, char* out_B, char* Mat_P, int L) In_B – массив исходного блока данных; Out_B – массив результирующего блока данных; Mat_P – массив матрицы перестановки; L – количество элементов в матрице перестановки.
	Процедура циклического сдвига влево блока данных на заданное количество разрядов	L_Sdvig(char* B, int N, int L) B – массив блока данных; N – длина блока данных в битах; L – количество разрядов сдвига.
	Процедура циклического сдвига вправо блока данных на заданное количество разрядов	R_Sdvig(char* B, int N, int L) B – массив блока данных; N – длина блока данных в битах; L – количество разрядов сдвига.
	Процедура формирования ключей (рис. 5)	Create_Klu(AnsiString Klutch, char Klu_M[16][6]) Klutch – исходный 64-х битный ключ; Klu_M – двухмерный массив шестнадцати 48-и битных ключей.
	Процедура F(Ri,Ki) (рис. 4)	F2(char* in_R, char* K, char* out_R) in_R – массив исходного блока данных Ri; K – массив i-го ключа Ki; out_R – массив результирующего блока данных функции.
	Процедура разбиения 56-и битного блока данных на два 28-и битных блока	R_CD(char* R, char* C, char* D) R – массив исходного 56-и битного блока данных; C, D – массивы результирующих 28-и битных блоков данных (C – младшие 28 бит, D – старшие).
	Процедура объединения двух 28-и битных блоков данных в один 56-и битный блока данных битных блока	CD _R(char* C, char* D, char* R) C, D – массивы исходных 28-и битных блоков данных (C – младшие 28 бит, D – старшие); R – массив результирующего 56-и битного блока данных;

В случае проектирования ПО в интегрированной среде Delphi в списках формальных аргументов вместо массивов символов необходимо использовать байтовые массивы (char* in_B º in_B: Array of Byte).

4. Оборудование

ПЭВМ с архитектурой IBM PC, операционная система – Windows 95, интегрированная среда – C++ Builder или Delphi версии не ниже 3.0

5. Порядок выполнения работы

1) Согласно полученному варианту задания разработать и отладить ПО конкретной криптографической процедуры.

2) Разработать методику тестирования правильности функционирования для конкретной процедуры. Оценить правильность функционирования конкретной процедуры.

3) Оформить отчет.

6. Оформление отчета

Отчет должен содержать:

− задание на лабораторную работу;

− листинг разработанного ПО для реализации конкретной криптографической процедуры;

− результаты исследования правильности функционирования конкретной процедуры.

7. Контрольные вопросы

1) Какие одноключевые криптографические преобразования Вам известны?

2) В каких случаях находят применение двухключевые криптографические методы, а в каких – одноключевые?

3) Какие методы побитовой обработки операндов реализованы в C++ Builder?

4) Какие методы побитовой обработки операндов реализованы в Delphi?

5) Поясните реализацию функции F (рис. 4).

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

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

Дата добавления: 2015-05-07