Similar presentations:
Шифр 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.
Функция PermutedChoice 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.
Блоки подстановки S18.
Дополнительные функции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.
Функция шифрования f22.
Функция шифра 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.