WikiSort.ru - Не сортированное

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

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

По таблице первые 3 бита результирующего блока ${\displaystyle \mathrm {IP} (T)}$ после начальной перестановки ${\displaystyle \mathrm {IP} }$ являются битами 58, 50, 42 входного блока ${\displaystyle T}$ , а его 3 последние бита являются битами 23, 15, 7 входного блока.

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

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

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

Разбить IP(T) на две части ${\displaystyle L_{0},R_{0}}$ , где ${\displaystyle L_{0},R_{0}}$  — соответственно 32 старших битов и 32 младших битов блока ${\displaystyle T_{0}}$ IP(T)= ${\displaystyle L_{0}R_{0}}$

Пусть ${\displaystyle T_{i-1}=L_{i-1}R_{i-1}}$ результат (i-1) итерации, тогда результат i-ой итерации ${\displaystyle T_{i}=L_{i}R_{i}}$ определяется:

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

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

Левая половина ${\displaystyle L_{i}}$ равна правой половине предыдущего вектора ${\displaystyle L_{i-1}R_{i-1}}$ . А правая половина ${\displaystyle R_{i}}$  — это битовое сложение ${\displaystyle L_{i-1}}$ и ${\displaystyle f(R_{i-1},k_{i})}$ по модулю 2.

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

Основная функция шифрования (функция Фейстеля)

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

Для вычисления функции ${\displaystyle f}$ последовательно используются

1. функция расширения ${\displaystyle \mathrm {E} }$ ,
2. сложение по модулю 2 с ключом ${\displaystyle k_{i}}$
3. преобразование ${\displaystyle \mathrm {S} }$ , состоящее из 8 преобразований ${\displaystyle \mathrm {S} }$ -блоков ${\displaystyle \mathrm {S} _{1},\mathrm {S} _{2},\mathrm {S} _{3}\ldots \ \mathrm {S} _{8}}$ ,
4. перестановка ${\displaystyle \mathrm {P} }$ .

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

Первые три бита вектора ${\displaystyle \mathrm {E} (R_{i-1})}$ являются битами 32, 1, 2 вектора ${\displaystyle R_{i-1}}$ . По таблице 2 видно, что биты 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 дублируются. Последние 3 бита вектора ${\displaystyle E(R_{i-1})}$  — это биты 31, 32, 1 вектора ${\displaystyle R_{i-1}}$ . Полученный после перестановки блок ${\displaystyle \mathrm {E} (R_{i-1})}$ складывается по модулю 2 с ключами ${\displaystyle k_{i}}$ и затем представляется в виде восьми последовательных блоков ${\displaystyle B_{1},B_{2},...B_{8}}$ .

${\displaystyle \mathrm {E} (R_{i-1})\oplus k_{i}=B_{1}B_{2}...B_{8}}$

Каждый ${\displaystyle B_{j}}$ является 6-битовым блоком. Далее каждый из блоков ${\displaystyle B_{j}}$ трансформируется в 4-битовый блок ${\displaystyle B'_{j}}$ с помощью преобразований ${\displaystyle S_{j}}$ . Преобразования ${\displaystyle S_{j}}$ определяются таблицей 3.

Таблица 3. Преобразования ${\displaystyle S_{i}}$ , i=1…8

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8	${\displaystyle S_{1}}$
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13
0	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
1	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5	${\displaystyle S_{2}}$
2	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
3	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9
0	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
1	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1	${\displaystyle S_{3}}$
2	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
3	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12
0	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
1	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9	${\displaystyle S_{4}}$
2	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
3	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14
0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6	${\displaystyle S_{5}}$
2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3
0	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
1	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8	${\displaystyle S_{6}}$
2	9	14	15	5	2	8	12	3	7	0	4	10	1	13	11	6
3	4	3	2	12	9	5	15	10	11	14	1	7	6	0	8	13
0	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
1	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6	${\displaystyle S_{7}}$
2	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
3	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12
0	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
1	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2	${\displaystyle S_{8}}$
2	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
3	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

Предположим, что ${\displaystyle B_{3}=101111}$ , и мы хотим найти ${\displaystyle B'_{3}}$ . Первый и последний разряды ${\displaystyle B_{3}}$ являются двоичной записью числа а, 0<=a<=3, средние 4 разряда представляют число b, 0<=b<=15. Строки таблицы S3 нумеруются от 0 до 3, столбцы таблицы S3 нумеруются от 0 до 15. Пара чисел (а, b) определяет число, находящееся в пересечении строки а и столбца b. Двоичное представление этого числа дает ${\displaystyle B'_{3}}$ . В нашем случае ${\displaystyle a=11_{2}=3}$ , ${\displaystyle b=0111_{2}=7}$ , а число, определяемое парой (3,7), равно 7. Его двоичное представление ${\displaystyle B'_{3}}$ =0111.

Значение функции ${\displaystyle f(R_{i-1},k_{i})}$ (32 бит) получается перестановкой Р, применяемой к 32-битовому блоку ${\displaystyle B'_{1}B'_{2}...B'_{8}}$ . Перестановка Р задана таблицей 4.

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

Генерирование ключей ${\displaystyle k_{i}}$

Ключи ${\displaystyle k_{i}}$ получаются из начального ключа ${\displaystyle k}$ (56 бит = 7 байтов или 7 символов в ASCII) следующим образом. Добавляются биты в позиции 8, 16, 24, 32, 40, 48, 56, 64 ключа ${\displaystyle k}$ таким образом, чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определена в таблице 5.

Таблица 5.

57	49	41	33	25	17	9	1	58	50	42	34	26	18	${\displaystyle 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	${\displaystyle D_{0}}$
14	6	61	53	45	37	29	21	13	5	28	20	12	4

Эта перестановка определяется двумя блоками ${\displaystyle C_{0}}$ и ${\displaystyle D_{0}}$ по 28 бит каждый. Первые 3 бита ${\displaystyle C_{0}}$ есть биты 57, 49, 41 расширенного ключа. А первые три бита ${\displaystyle D_{0}}$ есть биты 63, 55, 47 расширенного ключа. ${\displaystyle C_{i},D_{i}}$ i=1,2,3…получаются из ${\displaystyle C_{i-1},D_{i-1}}$ одним или двумя левыми циклическими сдвигами согласно таблице 6.

Ключ ${\displaystyle k_{i}}$ , i=1,…16 состоит из 48 бит, выбранных из битов вектора ${\displaystyle C_{i}D_{i}}$ (56 бит) согласно таблице 7. Первый и второй биты ${\displaystyle k_{i}}$ есть биты 14, 17 вектора ${\displaystyle C_{i}D_{i}}$

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

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

Таблица 8. Обратная перестановка ${\displaystyle \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

Слабые ключи

Слабыми ключами называется ключи k такие, что ${\displaystyle DES_{k}(DES_{k}(x))=x}$ , где x — 64-битный блок.

Известны 4 слабых ключа, они приведены в таблице 9. Для каждого слабого ключа существует ${\displaystyle 2^{32}}$ неподвижные точки, то есть таких 64-битных блоков х, для которых ${\displaystyle DES_{k}(x)=x}$ .

Таблица 9. DES-Слабые ключи

Слабые ключи (hexadecimal)	${\displaystyle C_{0}}$	${\displaystyle D_{0}}$
0101-0101-0101-0101	${\displaystyle [0]^{28}}$	${\displaystyle [0]^{28}}$
FEFE-FEFE-FEFE-FEFE	${\displaystyle [1]^{28}}$	${\displaystyle [1]^{28}}$
1F1F-1F1F-0E0E-0E0E	${\displaystyle [0]^{28}}$	${\displaystyle [1]^{28}}$
E0E0-E0E0-F1F1-F1F1	${\displaystyle [1]^{28}}$	${\displaystyle [0]^{28}}$

${\displaystyle [0]^{28}}$ обозначает вектор, состоящий из 28 нулевых битов.

Частично слабые ключи

В алгоритме DES существуют слабые и частично слабые ключи. Частично слабые ключи — это такие пары ключей ${\displaystyle (k_{1},k_{2})}$ , что ${\displaystyle DES_{k1}(DES_{k2}(x))=x.}$

Существуют 6 частично слабых пар ключей, они приведены в таблице 10. Для каждого из 12 частично слабых ключей существуют ${\displaystyle 2^{32}}$ «антинеподвижные точки», то есть такие блоки х, что ${\displaystyle DES_{k}(x)={\tilde {x}}.}$

Таблица 10. Частично слабые ключи

${\displaystyle C_{0}}$	${\displaystyle D_{0}}$	Пары частично слабых ключей	${\displaystyle C_{0}}$	${\displaystyle D_{0}}$
${\displaystyle [01]^{14}}$	${\displaystyle [01]^{14}}$	01FE-01FE-01FE-01FE,----FE01-FE01-FE01-FE01	${\displaystyle [10]^{14}}$	${\displaystyle [10]^{14}}$
${\displaystyle [01]^{14}}$	${\displaystyle [01]^{14}}$	1FE0-1FE0-1FE0-1FE0,----E0F1-E0F1-E0F1-E0F1	${\displaystyle [10]^{14}}$	${\displaystyle [10]^{14}}$
${\displaystyle [01]^{14}}$	${\displaystyle [0]^{28}}$	01E0-01E0-01F1-01F1,----E001-E001-F101-F101	${\displaystyle [10]^{14}}$	${\displaystyle [0]^{28}}$
${\displaystyle [01]^{14}}$	${\displaystyle [1]^{28}}$	1FFE-1FFE-0EFE-0EFE,----FE1F-FE1F-FE0E-FE0E	${\displaystyle [0]^{28}}$	${\displaystyle [1]^{28}}$
${\displaystyle [0]^{28}}$	${\displaystyle [01]^{14}}$	011F-011F-010E-010E,----1F01-1F01-0E01-0E01	${\displaystyle [0]^{28}}$	${\displaystyle [10]^{14}}$
${\displaystyle [1]^{28}}$	${\displaystyle [01]^{14}}$	E0FE-E0FE-F1FE-F1FE,----FEE0-FEE0-FEF1-FEF1	${\displaystyle [1]^{28}}$	${\displaystyle [10]^{14}}$

Известные атаки на DES

Таблица 11. Известные атаки на DES.

Методы атаки	Известные откр. тексты	Выбранные отк. тексты	Объём памяти	Количество операций
Полный поиск	1	-	Незначительный	${\displaystyle 2^{55}}$
Линейный Криптоанализ	${\displaystyle 2^{43}(85\%)}$	-	Для текста	${\displaystyle 2^{43}}$
Линейный Криптоанализ	${\displaystyle 2^{38}(10\%)}$	-	Для текста	${\displaystyle 2^{50}}$
Диффер. Криптоанализ	-	${\displaystyle 2^{47}}$	Для текста	${\displaystyle 2^{47}}$
Диффер. Криптоанализ	${\displaystyle 2^{55}}$	-	Для текста	${\displaystyle 2^{55}}$

• Метод полного перебора требует одну известную пару шифрованного и расшифрованного текста, незначительный объём памяти, и его выполнение требует около ${\displaystyle 2^{55}}$ шагов.
• Дифференциальный криптоанализ — первую такую атаку на DES заявили Бихам и Шамир. Эта атака требует шифрования ${\displaystyle 2^{47}}$ открытых текстов, выбранных нападающим, и для её выполнения нужны примерно ${\displaystyle 2^{47}}$ шагов. Теоретически являясь точкой разрыва, эта атака непрактична из-за чрезмерных требований к подбору данных и сложности организации атаки по выбранному открытому тексту. Сами авторы этой атаки Biham и Shamir заявили, что считают DES защищённым для такой атаки.
• Линейный криптоанализ разработан Matsui. Этот метод позволяет восстановить ключ DES с помощью анализа ${\displaystyle 2^{43}}$ известных открытых текстов, при этом требуется примерно ${\displaystyle 2^{43}}$ шагов для выполнения. Первый экспериментальный криптоанализ DES, основанный на открытии Matsui, был успешно выполнен в течение 50 дней на автоматизированных рабочих местах 12 HP 9735.

Для линейного и дифференциального криптоанализа требуется достаточно большой объём памяти для сохранения выбранных (известных) открытых текстов до начала атаки.