DES (Data Encryption Standard)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 00:54, 12 июня 2016.
TemplateDifinitionIcon.svg Определение «Определение - DES»
DES (Data Encryption Standard) — симметричный алгоритм шифрования, в котором один ключ используется как для шифрования, так и для расшифрования данных. DES разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FIPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит(в преобразовании учавствуют раундовые ключи по 48 бит). Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:

История блочного шифра DES

В 1972 году, после проведения исследования потребностей правительства США в компьютерной безопасности, американское НБС (Национальное Бюро Стандартов) — теперь переименовано НИСТ (Национальный Институт Стандартов и Технологий) — определило необходимость в общеправительственном стандарте шифрования некритичной информации. 15 мая 1973 года, после консультации с АНБ (Агентством национальной безопасности), НБС объявило конкурс на шифр, который удовлетворит строгим критериям проекта, но ни один конкурсант не обеспечивал выполнение всех требований. Второй конкурс был начат 27 августа 1974. На сей раз, шифр Lucifer, представленный IBM и развитый в течение периода 1973—1974 сочли приемлемым, он был основан на более раннем алгоритме Хорста Фейстеля.

17 марта 1975 года предложенный алгоритм DES был издан в Федеральном Регистре. В следующем году было проведено 2 открытых симпозиума по обсуждению этого стандарта, где подверглись жёсткой критике изменения, внесённые АНБ в алгоритм: уменьшение первоначальной длины ключа и S-блоки (блоки подстановки), критерии проектирования которых не раскрывались. АНБ подозревалось в сознательном ослаблении алгоритма с целью, чтобы АНБ могло легко просматривать зашифрованные сообщения. После чего сенатом США была проведена проверка действий АНБ, результатом которой стало заявление, опубликованное в 1978, в котором говорилось о том, что в процессе разработки DES АНБ убедило IBM, что уменьшенной длины ключа более чем достаточно для всех коммерческих приложений, использующих DES, косвенно помогало в разработке S-перестановок, а также, что окончательный алгоритм DES был лучшим, по их мнению, алгоритмом шифрования и был лишён статистической или математической слабости. Также было обнаружено, что АНБ никогда не вмешивалось в разработку этого алгоритма.

Часть подозрений в скрытой слабости S-перестановок была снята в 1990, когда были опубликованы результаты независимых исследований Эли Бихама (Eli Biham) и Ади Шамира (Adi Shamir) по дифференциальному криптоанализу — основному методу взлома блочных алгоритмов шифрования с симметричным ключом. S-блоки алгоритма DES оказались намного более устойчивыми к атакам, чем, если бы их выбрали случайно. Это означает, что такая техника анализа была известна АНБ ещё в 70-х годах XX века.

DES является блочным шифром. Чтобы понять, как работает DES, необходимо рассмотреть принцип работы блочного шифра, сеть Фейстеля.

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

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

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

Исходный текст T (блок 64 бит)преобразуется c помощью начальной перестановки IP которая определяется таблицей 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

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

Рис. 1. Схема работы DES.

Получение 16 ключей по 48 бит из клача 56 бит

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

Таблица 1.
57 49 41 33 25 17 9 1 58 50 42 34 26 18
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
14 6 61 53 45 37 29 21 13 5 28 20 12 4

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

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

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

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

Описание функции F

В функции F находится вся не линейная часть, осуществляется она с помощью S и P преобразований. Функция представлена на рисунке 2. На вход поступает 32 бита, затем происходит функция расширения Е, которая описана в таблице.

Рис. 2. Схема функции F.
Таблица 4. Функция расширения 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

Описание S преобразования

48 бит делится на подблоки по 6 бит (S-box). Функция S преобразует 6 бит в 4 бита. По таблице можно увидеть как определяется преобразование S.

Преобразования определяются таблицей 5.

Таблица 5. Преобразования , i=1…16
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
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
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
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
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
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
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
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
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

Описание P преобразования

Перестановка P задана таблицей 6:

Таблица 6. Перестановка 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

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

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

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


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

Рис. 3. Схема расшифрования DES.

При расшифровании данных все действия выполняются в обратном порядке. В 16 циклах расшифрования, в отличие от шифрования c помощью прямого преобразования сетью Фейстеля, здесь используется обратное преобразование сетью Фейстеля.


Схема расшифрования указана на Рис.3.
Ключ , i=1,…,16, функция f, перестановка IP и такие же как и в процессе шифрования.

Криптостойкость алгоритма DES

Нелинейность преобразований в DES средствами только S-блоков, в случае, если они имеют слабину, позволяет осуществлять контроль за шифрованной перепиской. Выбор S-блоков требует соблюдения нескольких условий:

  • Каждая строка каждого блока должна быть перестановкой множества {0,1,2,……,15}
  • S-блоки не должны являться линейной или афинной функцией своих аргументов.
  • Изменение одного бита на входе S-блока должно приводить к изменению по крайней мере двух битов на выходе.
  • Для каждого S-блока и любого аргумента х значение S(x) и должны различаться по крайней мере двумя битами.

Из-за небольшого числа возможных ключей (всего ), появляется возможность их полного перебора на быстродействующей вычислительной технике за реальное время. В 1998 году The Electronic Foundation используя специальный компьютер DES-Cracker, удалось взломать DES за 3 дня.

В алгоритме DES существуют слабые и частично-слабые ключи. Слабыми ключами называется ключи k такие что , x — блок 64 бит. Частично-слабые ключи — пары ключей такие что
Известны 4 слабых ключа, они приведены в таблице 8. Для каждого слабого ключа существует «постоянные точки», то есть таких 64-битовых блоков х, в которых

Таблица 8. DES-Слабые ключи
Слабые ключи(hexadecimal)
0101-0101-0101-0101
FEFE-FEFE-FEFE-FEFE
1F1F-1F1F-0E0E-0E0E
E0E0-E0E0-F1F1-F1F1

обозначает вектор, состоящий из 28 нулевых битов.

Существуют 6 частично-слабых пар ключей, они приведены в таблице 9. Для каждого из 12 частично-слабых ключей существуют «анти-постоянные точки», то есть такие блоки х, что

Таблица 9. Частично-слабые ключи
Пары частично-слабых ключей
01FE-01FE-01FE-01FE,----FE01-FE01-FE01-FE01
1FE0-1FE0-1FE0-1FE0,----E0F1-E0F1-E0F1-E0F1
01E0-01E0-01F1-01F1,----E001-E001-F101-F101
1FFE-1FFE-0EFE-0EFE,----FE1F-FE1F-FE0E-FE0E
O11F-011F-010E-010E,----1F01-1F01-0E01-0E01
E0FE-E0FE-F1FE-F1FE,----FEE0-FEE0-FEF1-FEF1
Таблица 10. Известные атаки на DES.
Методы атаки Известные откр. тексты Выбранные отк. тексты Объём памяти Количество операций
Полный поиск 1 - Незначительный
Линейный Криптоанализ - Для текста
Линейный Криптоанализ - Для текста
Диффер. Криптоанализ - Для текста
Диффер. Криптоанализ - Для текста
  • Метод полного поиска требует одну известную пару шифрованного и расшифрованного текста, незначительный объём памяти, и для его выполнения нужны шагов.
  • Дифференциальный криптоанализ — первую такую атаку на DES заявили Biham и Shamir. Эта атака требует шифрования открытых текстов выбранных нападающим, и для её выполнения нужны шагов. Теоретически являясь точкой разрыва, эта атака непрактична из-за чрезмерных требований к подбору данных и сложности организации атаки по выбранному открытому тексту. Сами авторы этой атаки Biham и Shamir заявили, что считают DES защищенным для такой атаки.
  • Линейный криптоанализ разработан Matsui. Этот метод позволяет восстановить ключ DES с помощью анализа известных открытых текстов, при этом требуется шагов для выполнения. Первый экспериментальный криптоанализ DES, основанный на открытии Matsui, был успешно выполнен в течение 50 дней на автоматизированных рабочих местах 12 HP 9735.

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

Увеличение криптостойкости алгоритма DES

Чтобы увеличивать криптостойкость DES появляются несколько вариантов: double DES (2DES), triple DES (3DES), DESX, G-DES.

  • Методы 2DES и 3DES основаны на DES, но увеличивают длину ключей (2DES — 112 бит, 3DES — 168 бит) и поэтому увеличивается криптостойкость.
  • Схема 3DES имеет вид , где ключи для каждого шифра DES. Это вариант известен как в ЕЕЕ так как три DES операции являются шифрованием. Существует 3 типа алгоритма 3DES:
  • DES-EEE3: Шифруется три раза с 3 разными ключами.
  • DES-EDE3: 3DES операции шифровка-расшифровка-шифровка с 3 разными ключами.
  • DES-EEE2 и DES-EDE2: Как и предыдущие, за исключением того, что первая и третья операции используют одинаковый ключ.
Самый популярный тип при использовании 3DES — это DES-EDE3, для него алгоритм выглядит так:
Зашифрование: .
Расшифрование:
При выполнении алгоритма 3DES ключи могут выбрать так:
  • независимы.
  • независимы, а
  • .
  • Метод DESX создан Рональдом Ривестом и формально продемонстрирована Killian и Rogaway. Этод метод — усиленный вариант DES, поддерживаемый инструментарием RSA Security. DESX отличается от DES тем, что каждый бит входного открытого текста DESX логически суммируется по модулью 2 с 64 битами дополнительного ключа, а затем шифруется по алгоритму DES. Каждый бит результата также логически суммируется по модулью 2 с другими 64 битами ключа. Главной причиной использования DESX является простой в вычислительном смысле способ значительного повысить стойкость DES к атакам полного перебора ключа.
  • Метод G-DES разработан Schaumuller-Bichl для повышения производительности DES на основе увеличения размером шфрованного блока. Заявлялось, что G-DES защищен так же как и DES. Однако, Biham и Shamir показали, что G-DES с рекомендуемыми параметрами легко взламывается, а при любых изменениях параметров шифр становится ещё менее защищен чем DES.
  • Ещё другой вариант DES использует независимые суб-ключи. Различно от алгоритма DES, в котором на основе 56-битного секретного ключа пользователя алгоритм DES получает шестнадцать 48-битных суб-ключей для использования в каждом из 16 раундов, в этом варианте использует 768-битного ключа (разделенного на 16 48-битных подключей) вместо 16 зависимых 48-битных ключей, создаваемых по ключевому графику алгоритма DES. Хотя очевидно, что использование независимых суб-ключей значительно усложнит полный поиск ключа, но стойкость к атаке дифференциальным или линейным криптоанализом не намного превысит стойкость обычного DES. По оценке Biham для дифференциального криптоанализа DES с независимыми подключами требуется выбранных открытых текстов, в то время как для линейного криптоанализа требуется известных открытых текстов.

Уязвимости алгоритма DES

Слабость DES : - это свойство DES сокращает простой перебор в 2 раза!

См. также

  1. "SP-сеть" материал из Википедии — свободной энциклопедии
  2. "Сеть Фейстеля" материал из Википедии — свободной энциклопедии
  3. "DES" материал из Википедии — свободной энциклопедии
  4. "3DES" материал из Википедии — свободной энциклопедии