Стандарт шифрования данных DES

Лекция 4 Ст андарт шиф рования данны х DES 1 Введение Ст андарт шиф рования данны х (DES) — блочный шифр с симметричными ключами, разработан Национальным Институтом Стандартов и Технологии (NIST – National Institute of Standards and Technology) США. DES был издан в эскизном виде в марте 1975 года как Федеральны й Ст андарт Обработки Инф ормации (FIPS – Federal Information Processing Standard) . В январе 1977 года после доработки DES был издан как FIPS 46. Позже NIST предложил новый стандарт FIPS 46-3, который рекомендует использование тройного DES (трехкратно повторенный шифр DES). 2 Шиф рование и дешифрование в DES DES — блочны й шиф р с симмет ричны ми ключами. На стороне шифрования DES принимает 64 -битовый исходный текст и порождает 64 -битовый зашифрованный текст; на стороне дешифрования DES принимает 64 -битовый зашифрованный текст и порождает 64 -битовый исходный текст. На обеих сторонах для шифрования и дешифрования применяется один и тот же 56 -битовый ключ. 3 Общая ст рукт ура DES Процесс шифрования состоит из двух прямых перестановок (P –блоков), которые называются начальной и конечной перестановками, и шестнадцати раундов Фейстеля. Каждый раунд использует различные сгенерированные 48 -битовые ключи. 4 Начальны е и конечны е перест ановки Каждая из перестановок принимает 64 -битовый вход и переставляет его элементы по заданному правилу. Эти перестановки — прямые перестановки без ключей, которые инверсны друг другу. Например, в начальной перестановке 58 -й бит на входе переходит в первый бит на выходе. В конечной перестановке первый входной бит переходит в 58 -й бит на выходе. 5 Правила перест ановки для P -блока Правила перестановки для этого P -блока задаются таблицей, которую можно представить как 64 -элементный массив. Значение каждого элемента массива определяет номер входа, а порядковый номер (индекс) элемента определяет номер выхода. Начальны е перестановки Конечны е перестановки 58 50 42 34 26 18 10 02 40 08 48 16 56 24 64 32 60 52 44 36 28 20 12 04 39 07 47 15 55 23 63 31 62 54 46 38 30 22 14 06 38 06 46 14 54 22 62 30 64 56 48 40 32 24 16 08 37 05 45 13 53 21 61 29 57 49 41 33 25 17 09 01 36 04 44 12 52 20 60 28 59 51 43 35 27 19 11 03 35 03 43 11 51 19 59 27 61 53 45 37 29 21 13 05 34 02 42 10 50 18 58 26 63 55 47 39 31 23 15 07 33 01 41 09 49 17 57 25 6 Раунды DES использует 16 раундов. Каждый раунд DES применяет шифр Фейстеля. Раунд I принимает левую и правую половину LI-1 RI-1 зашифрованного блока от предыдущего раунда (или начального блока перестановки) и LI и RI, которые поступают на следующий раунд (или конечный блок перестановки). Каждый раунд имеет два элемента шифра: смеситель и устройство замены. Каждый из этих элементов является обратимым. Все необратимые элементы сосредоточены в функции f (RI1,KI). 7 Функция DES Основной блок DES — функция DES. Функция DES с помощью 48 -битового ключа зашифровывает 32 самых правых бита RI-1, чтобы получить на выходе 32 -битовое слово. Эта функция содержит четыре секции: P -блок расширения, отбеливатель (XOR), группу S -блоков и прямой P -блок. 8 P-блок расширения Так как вход RI-1 имеет длину 32 бита, а ключ KI — длину 48 битов, мы сначала должны расширить RI-1 до 48 бит. RI-1 разделяется на 8 секций по 4 бита. Каждая секция на 4 бита расширяется до 6 бит. Эта перестановка расширения следует по заранее определенным правилам. Для секции значения входных бит 1, 2, 3 и 4 присваиваются битам 2, 3, 4 и 5 соответственно на выходе. Выходной бит 1 формируется на основе входного бита 4 из предыдущей секции; бит выхода 6 формируется из бита 1 в следующей секции. Если секции 1 и 8 рассматривать как соседние секции, то те же самые правила применяются к битам 1 и 32. 9 Таблица блока расширения Хотя отношения между входом и выходом могут быть определены математически, но чтобы определить этот P -блок, DES использует таблицу. Число выходов таблицы - 48, но диапазон значений — только от 1 до 32. Некоторые из входов идут больше чем к одному выходу. Например, значение входного бита 5 становится значением битов выхода 6 и 8. 32 01 02 03 04 05 04 05 06 07 08 09 08 09 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 10 От беливатель и S-блоки После расширения DES использует операцию XOR (ИСКЛЮЧАЮЩЕЕ ИЛИ) над расширенной частью правой секции и ключом раунда. Правая секция и ключ имеют длину 48 бит. Ключ раунда используется только для этой операции. S -блоки смешивают информацию. DES использует 8 S –блоков, каждый с 6 -ю входными битами и 4 -мя выходными. 11 Правила для S- блока Данные из 48 битов от второй операции DES разделяются на 8 частей по 6 битов, и каждая часть поступает в S-блок. Результат каждого блока — 4 бита. После их объединения результатом являются 32 -бита. Подстановка в каждом блоке следует по заранее определенным правилам, основанным на таблице из 4 -х строк и 16 -ти столбцов. Комбинация битов 1 и 6 на входе определяет одну из четырех строк; комбинация битов от 2 -го до 5 -го определяет один из шестнадцати столбцов. 12 Табличное задание S -блока Для каждого S -блока задается собственная таблица, поэтому необходимо иметь восемь таблиц, например таких, как это показано ниже. Значение входа (номер строки и номер столбца) и значения выхода даются как десятичные числа, чтобы сэкономить место на странице. В реальности они могут быть заменены двоичными числами. Таблица для S-блока 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07 1 00 15 07 04 14 02 13 10 03 06 12 11 09 05 03 08 2 04 01 14 07 13 06 02 11 15 12 09 07 03 10 05 00 3 15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13 Например, входная последовательность S блока 1 — 100011 дает выход 1100, а вход 000000 дает выход 1110. 13 Генерация ключей Генератор ключей создает шестнадцать ключей по 48 битов из ключа шифра на 56 битов. Ключ шифра обычно дается как ключ из 64 -х битов, в котором 8 дополнительных битов являются битами проверки. Они отбрасываются перед фактическим процессом генерации ключей. 14 Процесс генерации ключей 15 Удаление битов проверки Предварительный процесс перед расширением ключей — перест ановка сж ат ия удаляет биты четности (биты 8, 16, 24, 32..., 64) из 64 -битового ключа и переставляет остальную часть битов согласно таблице. Оставшиеся 56 битов — фактический ключ шифра, который используется, чтобы генерировать ключи раунда. Таблица удаления проверочных битов 57 49 41 33 25 17 09 01 58 50 42 34 26 18 10 02 59 51 43 35 27 19 11 03 60 52 44 36 63 55 47 39 31 23 15 07 62 54 46 38 30 22 14 06 61 53 45 37 16 Сдвиг влево После прямой перестановки ключ разделен на две части по 28 битов. Каждая часть сдвигается влево (циклический сдвиг) на один или два бита. В раундах 1, 2, 9 и 16 смещение – на один бит, в других раундах — на два бита. Затем эти две части объединяются, чтобы создать часть в 56 бит. Таблица показывает число сдвигов для каждого раунда. Число сдвигаемых бит Раунд 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Число 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 бит 17 Перест ановка сж ат ия Перестановка сжатия ( P -блок) изменяет 56 битов на 48 битов, которые используются для формирования ключа раунда. Таблица сжатия ключа 14 17 11 24 01 05 03 28 15 06 21 10 23 19 12 04 26 08 16 07 27 20 13 02 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 18 Шиф р и обрат ны й шиф р Используя смеситель и устройство замены, мы можем создать шифр и обратный шифр для каждого из 16 -ти раундов. Шифр используется на стороне шифрования; обратный шифр — на стороне дешифрования. Алгоритмы создания шифра и обратного шифра аналогичны. Левая секция исходного текста L0 на стороне шифрования шифруется как L16, и L16 дешифруется на стороне дешифратора как L0. Аналогичная ситуация с R0 и R16. Чтобы сделать возможным обратное шифрование, нужно, чтобы: - последний раунд содержал только смеситель и не содержал устройства замены; - ключи раундов K1, …, K16 применялись при шифровании и дешифровании в обратном порядке. 19 Алгорит м создания шиф ра и обрат ного шиф ра 20 Итоги •Стандарт шифрования данных (DES) — блочный шифр с симметричными ключами, изданный национальным Институтом Стандартов и Технологии (NIST) как FIPS 46. •На стороне шифрования DES принимает исходный текст на 64 бита и создает зашифрованный текст на 64 бита. На стороне дешифрования DES принимает зашифрованный текст на 64 бита и создает блок на 64 бита исходного текста. Ключ шифра на 56 битов одного типа используется и для шифрования, и для дешифрования. •Процесс шифрования состоит из двух перестановок ( P -блоки), которые называются начальными и конечными перестановками, и шестнадцати раундов Фейстеля. Каждый раунд DES — шифр Фейстеля с двумя элементами (смеситель и 21 Итоги •Основой DES является функция DES. Функция DES применяет ключ на 48 битов к самым правым 32 битам, чтобы получить на выходе 32 бита. Эта функция составлена из четырех операций: перестановки расширения, отбеливателя (который использует ключ), группы S -блоков и прямой перестановки. •Генератор ключей раунда создает из ключа шифра на 56 битов 16 ключей по 48 битов. Однако ключ шифра обычно представляется как ключ на 64 бита, в котором 8 дополнительных битов являются проверочными битами — они отбрасываются перед фактическим процессом генерирования ключей. •Одно из решений по улучшению безопасности DES состоит в том, чтобы пользоваться многократными DES, которые используют кратное число применения ключей (двукратный или трехкратный DES). 22 Обзорны е вопросы по лекции 4 1. Каков размер блока в DES? Каков размер ключа шифра в DES? Каков размер ключей раунда в DES? 2. Каково число раундов в DES? 3. Сколько смесителей и устройств замены используется в при шифровании и дешифрования? 4. Сколько перестановок используется в алгоритме шифра DES? 5. Сколько операций ИСКЛЮЧАЮЩЕЕ ИЛИ используется в DES-шифре? 6. Почему DES-функции необходима расширяющая перестановка? 7. Почему генератор ключей раунда нуждается в удалении проверочных бит? 23