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

Лабораторная работа №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₁_,а в раунде 2 применяют K₂; на стороне дешифрования в раунде 1 нужен K₂, а в раунде 2 - K₁.

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

Пример 3

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

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

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

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

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

Таблица 2.
Начальная обработка	Исходный текст: 11110010 После IP:10111001 L₀: 1011 R₀: 1001	Ключ шифра: 1011100110
Раунд 1	L₁: 1001 R₁: 0111	Ключ раунда: 10111100
Раунд 2	L₂: 1011 R₂: 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-перестановку по варианту