Шифр DES

1.

Методы и средства
криптографической защиты
информации
ЛЕКТОР Д.Т.Н., ШАКУРСКИЙ МАКСИМ ВИКТОРОВИЧ

2.

ШИФР DES – Data Encryption System
Шифр DES относится к устаревшим, но его рассмотрение представляет
собой интерес с точки зрения отправного пункта развития блочных
криптографических шифров. Более того, одна из его модификаций TripleDES
используется на момент чтения данного курса.
DES (англ. Data Encryption Standard) — алгоритм для симметричного
шифрования, разработанный фирмой IBM и утверждённый правительством
США в 1977 году как официальный стандарт (FIPS 46-3). Размер блока для
DES равен 64 битам. В основе алгоритма лежит сеть Фейстеля с 16 циклами
(раундами) и ключом, имеющим длину 56 бит. Алгоритм использует
комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1)
преобразований.

3.

Устойчивость шифра DES
В 1998 году алгоритм DES был взломан суперкомпьютером менее чем за 3
дня. В виду малой длины ключа алгоритм DES считался не надёжным,
поэтому ещё в 1978 году были предложены алгоритмы по его усилению.
Прямым развитием DES в настоящее время является алгоритм Triple DES
(3DES). В 3DES шифрование/расшифровка выполняются путём троекратного
выполнения алгоритма DES.
Шифр DES регламентируется стандартом FIPS publication 46-3
прекратившим своё действие 19.05.2005. В данной главе, при описании
шифра, использованы иллюстрации из данного стандарта.

4.

Взаимодействие блоков в DES
Для DES рекомендовано несколько режимов:
ECB (англ. electronic code book) — режим «электронной кодовой книги» (простая замена);
CBC (англ. cipher block chaining) — режим сцепления блоков;
CFB (англ. cipher feed back) — режим обратной связи по шифротексту;
OFB (англ. output feed back) — режим обратной связи по выходу;
Counter Mode (CM) — режим счётчика.

5.

Структура шифра
Шифр DES построен на основе сети Фейстеля.
Структура шифра включает в себя следующие блоки и обозначения:
INPUT – блок шифруемых данных (содержащий 64 бита информации);
INITIAL PERMUTATION (IP) – блок начальной перестановки;
Далее следуют 16 раундов шифрования на основе сети Фейстеля:
L0..L16 – левая часть блока шифруемых данных (длинной 32 бита);
R0..R16 – правая часть блока шифруемых данных (длинной 32 бита);
K0..K16 – раундовые ключи, генерация которых подробно рассмотрена ниже;
f – функция шифрования, подробно рассмотренная ниже;
⊕ - функция сложения по модулю 2 (операция исключающее или);
INVERSE INITIAL PERMUTATION (IP-1) – выходная перестановка;
OUTPUT – блок зашифрованных данных (содержащий 64 бита информации).

6.

Функция шифрования f
На вход функции шифрования подаётся правая часть шифруемых
данных R0..R15 (в зависимости от раунда шифрования),
содержащая 32 бита информации и раундовый ключ K1..K16 (в
зависимости от раунда шифрования), содержащий 48 бит
информации.
Структура функции шифрования включает в себя следующие
блоки и обозначения:
E – блок расширения данных, формирующая из 32 битного блока
48 битный блок информации;
⊕ - функция сложения по модулю 2 (операция исключающее
или);
S1..S8 – блоки подстановки, каждый из которых преобразует
входящие 6 бит шифруемых данных в 4 бита зашифрованных
данных на основе таблицы подстановки; при этом каждый из
восьми блоков однозначно определён стандартом.
P – блок перестановки.

7.

Формирование
раундовых ключей
KEY – на вход алгоритма передаётся ключ шифра DES содержащий 56
бит данных. Здесь важно заметить, что ключ длинной 56 бит
дополняется ещё 8 битами до размера в 64 бита таким образом, что
каждые 8 бит в 64-битного представления ключа содержат 7 бит
оригинального ключа и 1 добавочный бит, значение которого
определяется таким образом, что сумма бит в байте должна иметь
нечётное значение;
PERMUTED CHOICE 1 – блок выбора 56 бит исходного ключа из 64 бит
дополненного ключа в соответствии с заданной таблицей
перестановки;
C0..16 – правая часть 56 битного блока, содержащая 28 бит;
D0..16 – левая часть 56 битного блока, содержащая 28 бит;
LEFT SHIFT – циклический сдвиг влево;
PERMUTED CHOICE 2 – выборка из 56 битного блока,
сформированного объединением двух 28 битных блоков (результат
двух операций LEFT SHIFT над блоками C и D) 48 бит в соответствии с
определённой таблицей выбора.

8.

Модель генерации раундовых ключей
Для генерации нам потребуется создание трёх подпрограмм в
виде функций: Permuted Choice 1, Permuted Choice 2 и Left Shift.
Заметим, что на рисунке некоторые блоки регистрового сдвига
обозначены, как Left Shift, другие, как Left Shifts. Данная
особенность будет рассмотрена и учтена при моделировании
функции Left Shift. Учитывая, что в пределах генерации ключей
есть дополнительные действия, включим их в данные функции,
что значительно упростит структуру алгоритма.

9.

Функция Permuted
Choice 1.

10.

Пояснения

11.

Функция Left Shift
Данная подпрограмма реализует циклический сдвиг влево для 28 бит данных блоков,
коими являются блоки C и D.

12.

Функция Permuted Choice 2
Функция выполняет слияние двух
массивов C и D и выбор бит ключа в
соответствии с таблицей перестановки
PC-2

13.

Функция генерации ключей
KeySchedule.

14.

Модель функции шифрования f
Для её реализации сформируем необходимый вспомогательные функции:
Функция E – расширение массива данных
Функция S – функция подстановки
Функция P – функция перестановки
После реализации данных функций реализуем
саму функцию шифрования f.

15.

Функция расширения массива
данных E.
Расширение основано на
дублировании ряда бит в соответствии
с таблицей ниже.

16.

Функция подстановки S.
Если обозначить 6 бит в виде маски abcdef, то биты af образуют первую группу из двух бит, а биты bcde
образуют вторую группу из четырёх бит. Две данные группы используются для определения четырёх бит
подстановки.

17.

Блоки подстановки S

18.

Дополнительные функции
A10 a 21 f 20 a 2 f
B10 b 23 c 2 2 d 21 e 20 b 8 c 4 d 2 e
Функция AB формирует из 6-битного
числа массив из двух координат.
Функция dtb4 формирует из
десятичного числа массив из 4 бит
Функция Sn формирует массив S как
список матриц подстановки S.

19.

S функция
Организуется цикл на 8 итераций, для каждого блока из 6 бит.
Из массива, содержащего 48 бит выделяется последовательно, на каждой итерации 6 бит данных.
Определяем координаты элемента таблицы Sn подстановки.
Выбираем таблицу подстановки, в соответствии с обрабатываемым блоком, и выбираем из неё нужно
значение с помощью координат элемента подстановки.
Переводим данное значение в
формат матрицы из 4-х элементов.
Записываем полученные 4 бита в новый
блок данных на соответствующие
позиции.

20.

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

21.

Функция шифрования f

22.

Функция шифра DES
Необходимые действия:
Функция Initial Permutation
Разбиение блока 64 бита на два блока L и R по 32 бита
Организация цикла из 16 итераций шифрования и
реализация тела цикла на основе сети Фейстеля
Объединение двух блоков L и R в единый блок, размером 64
бита
Функция Inversed Initial Permutattion

23.

Функция Initial Permutation
(начальная перестановка)
Функция IP представляет собой
функцию перестановки в чистом
виде, поэтому её реализация
крайне проста для понимания

24.

Функция Inverse Initial Permutation
(конечная перестановка)
Данная функция является
обратной для функции IP, то есть
IIP(IP(K))=K

25.

Функция шифра DES
Теперь, когда все вспомогательные функции готовы, сформируем функцию шифрования
DES

26.

Заключение!
Для ключа шифра:10316E028C8F3B4A и шифруемом блоке 0000000000000000.