DES шифр

DES (Data Encryption Standart) — Симметричный алгоритм шифрования, в котором один ключ используется, как для шифрования, так и для расшифрования данных. DES разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FTPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:
режим электронной кодовой книги (ECB — Electronic Code Book),
режим сцепления блоков (СВС — Cipher Block Chaining),
режим обратной связи по шифротексту (CFB — Cipher Feed Back),
режим обратной связи по выходу (OFB — Output Feed Back).
Блочный шифр
Входными данными для блочного шифра служат блок размером n бит и k-битный ключ. На выходе, после применения шифрующего преобразования, получается n-битный зашифрованный блок, причём незначительные различия входных данных как правило приводят к существенному изменению результата. Блочные шифры реализуются путём многократного применения к блокам исходного текста некоторых базовых преобразований.
Базовые преобразования:
Сложное преобразование на одной локальной части блока.
Простое преобразование между частями блока. Так как преобразование производится поблочно, как отдельный шаг требуется разделение исходных данных на блоки необходимого размера. При этом вне зависимости от формата исходных данных, будь то текстовые документы, изображения или другие файлы, они должны быть интерпретированы в бинарный вид и только после этого разбиты на блоки. Все вышеперечисленное может осуществляться программными, так и аппаратами средствами.

Преобразования Сетью Фейстеля
Это преобразование над векторами (блоками) представляющими собой левую и правую половины регистра сдвига. В алгоритме DES используются прямое преобразование сетью Фейстеля в шифровании (см. Рис.1) и обратное преобразование сетью Фейстеля в расшифрование (см. Рис.2).

Схема шифрования алгоритма DES

Исходный текст — блок 64 бит.
Шифрованный текст — блок 64 бит.

Процесс шифрования состоит в начальной перестановке, 16 циклах шифрования и конечной перестановке.
Рассмотрим подробную схему алгоритма DES:
LiRi=1,2ldots.левая и правая половины 64-битового блока LiRi
ki — 48 битовые ключи
f — функция шифрования
IP — начальная перестановка
IP-1 — конечная перестановка.

По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58, 50, 42 входного блока Т, а его 3 последние бита являются битами 23, 15, 7 входного блока. Дальше 64-битовой блок IP(T) участвует в 16-циклах преобразования Фейстеля.

— 16 циклов преобразования Фейстеля:

Разбить IP(T) на две части L0,R0, где L0,R0 — соответствено 32 старших битов и 32 младших битов блока T0 IP(T)= L0R0

Пусть Ti -1 = Li -1Ri -1 результат (i-1) итерации, тогда результат i-ой интерации Ti = LiRi определяется:

Li = Ri - 1

Левая половина Li равна правой половине предыдущего вектора Li - 1Ri - 1. А правая половина Ri — это битовое сложение Li - 1 и f(Ri - 1,ki) по модулю 2.

В 16-циклх преобразования Фейстеля функция f играет роль шифрования. Рассмотрим подробно функцию f.

Аргументы функции f являются 32 битовой вектор Ri - 1, 48 битовой ключ ki, которые являются результатом преобразования 56 битового исходного ключа шифра k.

Для вычисления функции f используются фукция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков , и перестановка P.

Функция Е расширяется 32 битовой вектор Ri - 1 до 48 битовой вектор E(Ri - 1) путем дублирования некоторых битов из Ri - 1 при этом порядок битов вектора E(Ri - 1) указан в таблице 2.

Первые три бита вектора E(Ri - 1) являются битами 32, 1, 2 вектора Ri -1. По таблице 2 видно что биты 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 дублируются. Последние 3 биты вектора E(Ri - 1) — это биты 31, 32, 1 вектора Ri - 1. Полученный после перестановки блок E(Ri -1) складывается по модулю 2 с ключами ki и затем представляются в виде восьми последовательных блоков B1,B2,...B8.
E(Ri - 1) = B1B2...B8
Каждый Bj является 6-битовым блоком. Далее каждый из блоков Bj трансформируется в 4 битовой блок B'j с помощью преобразований Sj. Преобразования Sj определяется таблицей 3.

Предположим что B3 = 101111 и мы хотим найти B'3. Первый и последний разряды B3 являются двоичной записью числа а, 0<=a<=3, средние 4 разряды представляют число b, 0<=b<=15. Строки таблицы S3 нумеруются от 0 до 3, столбцы таблицы S3 нумеруются от 0 до 15.Пара числа(а,b) определяет число,находящее в пересечении строки а и столбцы b. Двоичное представление этого числа дает B'3 .В нашем случае a = 112 = 3,b = 01112 = 7, число определяется парой (3,7) равно 7, следует B'3=0111.
Значение функции f(Ri - 1,ki) (32 бит) получается перестановкой Р, применяемой к 32 битовому блоку B'1B'2...B'8. Перестановка Р задана таблицей 4.

f(Ri - 1,ki) = P(B'1B'2...B'8)
Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f — это бита 16, 7, 20, 21 вектора B'1B'2...B'8

Генерирование ключей ki.
Ключи ki получаются из начального ключа k (56 бит = 7 байтов или 7 символов в АSCII) таким образом. Восемь битов, находящих в позициях 8, 16, 24, 32, 40, 48, 56, 64 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определенна как в таблице 5.

Эта перестановка определяется двумя блоками C0 и D0 по 28 бит каждый. Первые 3 бита C0 есть биты 57, 49, 41 расширенного ключа. А первые три бита D0 есть биты 63, 55, 47 расширенного ключа. Ci,Di i=1,2,3…получаются из Ci - 1,Di - 1 одним или двумя левыми циклическими сдвигами согласно таблице 6.

Ключ ki, i=1,…16 состоит из 48 бит, выбранных из битов вектора CiDi (56 бит) согласно таблице 7. Первый и второй биты ki есть биты 14, 17 вектора CiDi

Конечная перестановка IP - 1 действует на T16 и используется для востановления позиции. Она является обратной к перестановке IP. Конечная перестановка определяется таблицей 8.

Режимы использования DES
DES может используется в четырех режимах.
Режим электронной кодовой книги (ЕСВ — Electronic Code Book): обычное использование DES как блочного шифра (см. Рис.7).

Режим сцепления блоков (СВС — Cipher Block Chaining) (см. Рис.8). Каждый очередной блок Ci i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста Mi + 1. Вектор C0 — начальный вектор, он меняется ежедневно и хранится в секрете.

Режим обратной связи по шифротексту (CFB — Cipher Feed Back) (см. Рис.9). В режиме СFB вырабатывается блочная «гамма» Z0,Z1,...Zi = DESk(Ci - 1)

. Начальный вектор C0 сохраняется в секрете.

Режим обратной связи по выходу (OFB — Output Feed Back) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма» Z0,Z1,...

, i>=1

Режим ECB прост в реализации, но возможно проведение критоанализа
В режимах ECB и OFB искажение при передаче одного 64-битового блока шифротекста Ci приводит к искажению после расшифрования только соответствующего открытого блока Mi , поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.
В режимах CBC и CFB искажение при передаче одного блока шифрованного текста Сi приводит к искажению на приёмнике не более двух блоков открытого текста Mi,Mi + 1. Изменение Mi приводит к изменению всех остальных блоковMi + 1,Mi + 2… Это свойство используется для выработки кода аутентификации сообщения.

Обновлено: 11.03.2015