DES

DES - блочный шифр.

Размер блока - 64 бита.
Размер зашифрованного блока - 64 бита.
Длина ключа - 56 бита (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа).

Безопасность полностью определяется ключом.

На простейшем уровне алгоритм представляет ничего большего, чем комбинация двух основных методов шифрования: смещения и диффузии. Фундаментальным строительным блоком DES является применение к тексту единичной комбинации этих методов (подстановка, а за ней перестановка) зависящей от ключа. Такой блок называется этапом. DES состоит из 16 этапов, одинаковая комбинация методов применяется к открытому тексту 16 раз.

Схема алгоритма

Исходный текст — блок 64 бит. Процесс шифрования состоит из

начальной перестановки,
16 циклов шифрования,
конечной перестановки.

Начальная перестановка

Исходный текст $T$ (блок 64 бит) преобразуется c помощью начальной перестановки $\mathrm{IP}$ которая определяется таблицей 1:

Таблица 1. Начальная перестановка IP
58	50	42	34	26	18	10	2	60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6	64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1	59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5	63	55	47	39	31	23	15	7

$T_0=\mathrm{IP}(T)$ .

Циклы шифрования

Полученный после начальной перестановки, 64-битовый блок $T_0$ участвует в 16-циклах преобразования Фейстеля.

Цикл преобразования Фейстеля

На вход $i$ преобразования поступает выход предыдущего этапа $T_{i-1}$ . Он разбивается на две равные части по 32 бита - левую $L_{i-1}$ и правую $R_{i-1}$ .

Затем эти части преобразуются по правилам

$L_{i}=R_{i-1}$

$R_{i}=L_{i-1}\oplus f(R_{i-1},K_{i})$

где $f$ - основная функция шифрования (Фейстеля).

На выходе мы получаем новый 64-битовый блок:

$T_{i}=L_{i}R_{i}$ .

Основная функция шифрования.

Таблица 2. Функция расширения E
32	1	2	3	4	5
4	5	6	7	8	9
8	9	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
28	29	30	31	32	1

Аргументами функции $f$ являются 32-битовый вектор $R_{i-1}$ и 48-битовый ключ $K_i$ , который является результатом преобразования исходного ключа шифрования $K$ .

Для вычисления функции $f$ используются

функция расширения $\mathrm{E}$
$\mathrm{S}$ преобразование, состоящее из 8 $\mathrm{S}$ -блоков
перестановка $P$

Функция $\mathrm{E}$ расширяет 32-битовый вектор $R_{i-1}$ до 48 - битового вектора $\mathrm{E}(R_{i-1})$ дублируя некоторые биты этого вектора. Порядок битов полученного вектора $\mathrm{E}(R_{i-1})$ показан в таблице 2.

Полученный после расширения блок $\mathrm{E}(R_{i-1})$ складывают по модулю 2 с ключом цикла $i$ и разбивают на восемь 6-битовых частей.

$\mathrm{E}(R_{i-1})\oplus K_i=B_1B_2\ldots B_8$ .

Затем каждый 6-битовый блок $B_j$ преобразуется с помощью $S_j$ -преобразования в 4-битовый блок $B'_j$ .

$B'_j=S_j(B_j),~j=1,\ldots,8$ .

Перестановка $\mathrm{P}$ применяется к выходному блоку $B'_1B'_2\ldots B'_8$ и задается таблицей 4.

Таблица 4. Перестановка P
16	7	20	21	29	12	28	17
1	15	23	26	5	18	31	10
2	8	24	14	32	27	3	9
19	13	30	6	22	11	4	25

Получаем окончательное значение основной функции на $i$ -ом цикле.

Конечная перестановка

Конечная перестановка $\mathrm{IP}^{-1}$ действует на $T_{16}$ и является обратной к первоначальной перестановке. Конечная перестановка определяется таблицей 8.

Таблица 8. Обратная перестановка $\mathrm{IP}^{-1}$
40	8	48	16	56	24	64	32	39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30	37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28	35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26	33	1	41	9	49	17	57	25

Алгоритм получение ключей для каждого цикла

Есть 64-битовый начальный ключ $K$ .

младший бит каждого байта в ключе отвечает за четность количества единиц в ключе, при шифровании они отбрасываются.
Делается перестановка, показанная в таблице 5

Таблица 5.
57	49	41	33	25	17	9	1	58	50	42	34	26	18	$C_0$
10	2	59	51	43	35	27	19	11	3	60	52	44	36
63	55	47	39	31	23	15	7	62	54	46	38	30	22	$D_0$
14	6	61	53	45	37	29	21	13	5	28	20	12	4

$C_i$ и $D_i$ получаются из $C_{i-1},D_{i-1}$ циклическим сдвигом влево. Сдвиг определяется на каждом шаге таблицей 6

Таблица 6.
i	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

Ключ $k_i,~i=1,\ldots,16$ состоит из 48 бит, выбранных из битов вектора $C_iD_i$ (56) согласно таблице 7.

Таблица 7.
14	17	11	24	1	5	3	28	15	6	21	10	23	19	12	4
26	8	16	7	27	20	13	2	41	52	31	37	47	55	30	40
51	45	33	48	44	49	39	56	34	53	46	42	50	36	29	32

Lucifer

Последняя версия:

Входной блок - 128 бит.
Выходной блок - 128 бит.
Длина ключа - 128 бит.
У этого алгоритма 16 этапов.

Lucifer - это набор перестановок и подстановок, его блоки похожи на блоки DES. В DES результат функции $f$ объединяется с помощью XOR со входом предыдущего этапа, образуя вход следующего этапа. У S-блоков алгоритма Lucifer 4-битовые входы и 4-битовые выходы, вход S-блоков представляет собой перетасованный выход S-блоков предыдущего этапа, входом S-блоков первого этапа является открытый тест. Для выбора используемого S-блока из двух возможных применяется бит ключа. В отличие от DES половины блока между этапами не переставляются и вообще понятие половины блока не используется в алгоритме Lucifer. У этого алгоритма 16-этапов, 128-битовые блоки и более простое, чем в DES, распределение ключей.

Шнаер 226

Сказать "Спасибо"

Особенности построения блочных шифров на примере шифров Lucifer и DES

DES