Во втором раунде нет устройства замены

Лабораторная работа №6

Упрощенный DES (S-DES)

Упрощенный DES (S-DES) разработан профессором Эдуардом Шаефером (Edward Schaefer) Университета Санта-Клары и является образовательным инструментом для помощи студентам при изучении структуры DES - для шифрования и дешифрования с использованием блочных шифров и ключей с небольшим количеством битов.

Структура S-DES

S-DES - блочный шифр, как это показано на рис. 1.

Рис. 1. Шифрование и дешифрование в S – DES

 

На стороне шифрования S-DES принимает исходный текст по 8 битов и создает зашифрованный текст по 8 битов; на стороне дешифрования S- DES принимает зашифрованный текст на 8 битов и создает 8-битовый открытый текст. Один и тот же ключ шифра на 10 битов используется и для шифрования, и для дешифрования.

Остановимся на шифровании, а потом обсудим дешифрование. Процесс шифрования состоит из двух перестановок (P-блоки), которые мы называем начальными и конечными перестановками (их также называют IP и IP^-1), и двух раундов Файстеля. Каждый раунд использует различные ключи раунда по 8 битов, сгенерированные от ключа шифра согласно заранее заданному алгоритму. Рисунок 2 показывает элементы шифра S-DES на стороне шифрования.

Рис. 2. Общая структура S-DES устройства шифрования

 

Рисунок 3 показывает начальные и конечные перестановки (P-блоки). Каждая из этих перестановок получает входную информацию на 8 битов и переставляет их согласно заранее заданному правилу. Эти перестановки - прямые перестановки, которые инверсны друг другу. Эти две перестановки не имеют никакого криптографического значения в S-DES. Они включены в S-DES, чтобы совместить их с полным DES.

 

Рис. 3. Начальная и конечная перестановки (IP и IP-1)

 

Раунды

S-DES использует два раунда. Каждый раунд S-DES - это шифр Файстеля, как это показано на рис.4

Рис. 4. Раунд S-DES (сторона шифрования)

 

Раунд получает L_{I -1} и R_{I -1} от предыдущего раунда (или начального блока перестановки) и создает L_I и R_I, которые поступают в следующий раунд (или конечный блок перестановки). Мы можем принять, что каждый раунд имеет два элемента шифра: смеситель и устройство замены. Каждый из этих элементов является обратимым. Устройство замены, очевидно, является обратимым. Оно меняет левую половину текста с правой половиной. Смеситель является обратимым из-за операции ИСКЛЮЧАЮЩЕЕ ИЛИ. Все необратимые элементы собраны в функции f (R_{I -1,} K_I).

 

Функция S-DES

Основа S-DES - функция S-DES. Функция S-DES применяет ключ на 8 битов к самым правым 4 битам (R_{I -1}), чтобы формирует выход на 4 бита. Эта функция составлена из четырех секций: P-блока расширения, отбеливателя, группы S-блоков и прямого P-блока, как показано на рис. 4.

P-блок расширения - R_I-1 вход на 4 бита, и K_I - ключ на 8 битов, так что мы сначала должны расширить R_I-1 до 8 битов.

Хотя отношения между входом и выходом могут быть определены математически, S-DES использует таблицу, чтобы определить P-блок, как это показано на рис. 5. Обратите внимание, что число портов выхода - 8, но диапазон значения - только 1-4. Некоторые из входов идут больше чем в один выход.

Отбеливатель (ИСКЛЮЧАЮЩЕЕ ИЛИ). После перестановки расширения S-DES используют операцию ИСКЛЮЧАЮЩЕЕ ИЛИ для сложения расширенной правой секции и ключа раунда. Обратите внимание, что ключи раунда используются только в этой операции.

S-блоки. S-блоки делают реальное смешивание (перемешивание). S-DES используют два S-блока, каждый с входом на 4 бита и выводом на 2 бита (см. рис. 6).

Рис. 5. P -блок расширения

 

Рис. 6. S-блоки

 

Данные по 8 битов от второй операции разделены на две части по 4 бита, и каждый кусок подается в свой блок. Результат каждого блока - отрезок на 2 бита; когда они объединяются, в результате получается текст на 4 бита. Подстановка в каждом блоке соответствует заранее определенным правилам, основанным на записях в таблицах 4 x 4. Комбинация входных битов 1 и 4 определяет одну из четырех строк; комбинация битов 2 и 3 определяет один из четырех столбцов, как показано на рис. 6.

Поскольку каждый S-блок имеет свою собственную таблицу, необходимы две таблицы, как это видно на рис.6, чтобы определить выход этих блоков. Значения входов (номер строки и номер столбца) и значения выходов на рисунке даются в виде десятичных чисел, чтобы сохранить пространство. Они должны быть изменены на двоичные значения.

Пример 1

На вход S-блока 1 подается число 1010₂. Каким будет выход?

Решение

Если мы запишем вместе первый и четвертый биты, мы получим 10 в двоичном виде или 2 в десятичном числе. Остающиеся биты - 01 в двоичном виде, - это 1 в десятичном числе. Мы ищем последовательно значение 2, столбец 1, на рис. 6 (S-блок 1). Результат в десятичном виде - 2, а в двоичном - это 10. Таким образом, вход 1010₂ дает выход 10₂.

Прямая перестановка. Последняя операция в функции S-DES - прямая перестановка с входом на 4 бита и выходом на 4 бита. Отношения входа-выхода для этой операции показаны на рисунке 7 и следуют тем же общим правилам, что и предыдущие таблицы перестановки.

Рис. 7. P-блок прямой перестановки

 

Генерация ключей

Генератор ключей раунда создает два ключа на 8 битов из ключа шифра на 10 битов.

 

Прямая перестановка

Первый процесс - прямая перестановка. Этот процесс переставляет 10 битов в ключе согласно заранее заданной таблице, как это показано на рис. 8.

 

Сдвиг влево

После прямой перестановки ключ разделяется на две части по 5 битов. Каждая часть сдвигается влево (циклический сдвиг) на r бит, где r - номер раунда (1 или 2). Эти две части затем объединяются, чтобы сформировать модуль на 10 битов.

 

Перестановка сжатия

Перестановка сжатия (P-блок) изменяет 10 битов на 8 битов, которые используются как ключ для раунда. Таблица перестановки сжатия показана на рис. 8.

Рис. 8. Генератор ключей

 

Пример2

Табл. 1 показывает три случая генерации ключей.

Таблица O.1.
Шаги	Случай 1	Случай 2	Случай 3
Ключ шифра
после перестановки
После разделения	L: 11001 R:01110	L: 00000 R:00000	L: 11111 R: 11111
Раунд 1:	Сдвинутые ключи:	L: 10011 R: 11100	L: 00000 R: 00000	L: 11111 R: 11111
Комбинация ключей:
Ключ раунда 1:
Раунд 2:	Сдвинутые ключи:	L: 01110 R: 10011	L: 00000 R: 00000	L: 1111 R: 11111
Ключ раунда 2:
Комбинация ключей:

Случаи 2 и 3 показывают, что ни одна из операций, используемых в процессе генерации ключей, не эффективна, если ключ шифра состоит из всех нулей или всех единиц. Нужно избегать такого типа ключей шифра.

Шифр и обратный шифр

Используя смесители и устройства замены, мы можем создать шифр и обратный шифр в два раунда. Шифр применяется на стороне шифрования; обратный шифр - на стороне дешифрования. Чтобы сделать шифр и обратный шифр, используются похожие алгоритмы. Раунд 2 имеет только смеситель и не имеет устройства замены. Это показано на рис.9.

Мы говорили, что смеситель самообратим, так же как и устройство замены. Конечные и начальные перестановки также инверсны друг другу. Левая часть исходного текста на стороне шифрования, L₀, зашифрована как L₂; L₂ на стороне дешифрования расшифрована как L₀. Аналогичная ситуация - с правой частью.

Очень важно запомнить, что ключи шифров раунда (K₁ и K₂), должны использоваться в обратном порядке. На стороне шифрования в раунде 1 применяют K_1, а в раунде 2 применяют K₂; на стороне дешифрования в раунде 1 нужен K₂, а в раунде 2 - K₁.

Во втором раунде нет устройства замены

Пример 3

Мы выбираем случайный блок исходного текста и случайный ключ. Определяем, какой блок зашифрованного текста получится, если

Исходный текст: 11110010 Ключ:1011100110 Зашифрованный текст: 11101011

Посмотрим результат каждого раунда и текста, созданного до и после раундов. Таблица 2 показывает результат шагов перед началом раунда. Исходный текст проходит начальную перестановку, чтобы создать различные 8 битов. После этого шага текст разбит на два части, L₀ и R₀. Таблица показывает результаты двух раундов, которые включают смешивание и заполнение (исключая второй раунд). Результаты последних раундов (L₂ и R₂) объединены.

Рис. 9. S-DES шифр и обратный шифр

 

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

Таблица 2.
Начальная обработка	Исходный текст: 11110010 После IP:10111001 L0: 1011 R0: 1001	Ключ шифра: 1011100110
Раунд 1	L1: 1001 R1: 0111	Ключ раунда: 10111100
Раунд 2	L2: 1011 R2: 0lll	Ключ раунда: 11010011
Конечная обработка	Перед IP-1 10110111 Зашифрованный текст: 11101011

 

Стоит упомянуть здесь некоторые важные положения. Сначала правая часть каждого раунда - та же самая, что и левая секция из следующего раунда. Причины в том, что правая часть проходит смеситель без изменения, но устройство замены перемещает ее левую часть. Например, R₁ проходит через смеситель второго раунда без изменения, но затем эта часть становится L₂ из-за устройства замены. Интересно то, что эта точка не имеет устройства замены в последнем раунде. Поэтому R₁, становится R₂ вместо того чтобы стать L₂.

 

Задание на лабораторную работу

8-битовый исходный текст – две последние цифры номера зачетной книжки.

10-битовый ключ – две предпоследние цифры номера зачетной книжки (два первых бита берется произвольно).

 

Например:

№ зачетной книжки 030933

8-битовый исходный текст = 33 = 0011 0011

10-битовый ключ = 09 = 0000 1001 + 00(два первых бита берется произвольно) =

 

Для шифрования 8-битового блока исходного текста выбираем IP-перестановку по варианту

№ варианта	IP-перестановка
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.