Просмотр кода страницы DES

{{значения}}

{{Карточка блочного шифра
| название = DES, Data Encryption Standard
| изображение = DES algorithm scheme.png
| создатель = [[IBM]]
| опубликован = [[1977]] год
| размер ключа = 56 бит + 8 проверочных
| размер блока = 64 бит
| число раундов = 16
| тип = [[Сеть Фейстеля]]
}}

'''DES''' ({{lang-en|Data Encryption Standard}}) — алгоритм для [[Симметричный шифр|симметричного]] [[Шифрование|шифрования]], разработанный фирмой [[IBM]] и утверждённый правительством [[США]] в 1977 году как официальный стандарт ([[FIPS]] 46-3). Размер блока для DES равен {{nobr|64 [[бит]]ам}}. В основе алгоритма лежит [[сеть Фейстеля]] с 16 циклами ([[Раунд (в криптографии)|раундами]]) и [[Ключ (криптография)|ключом]], имеющим длину {{nobr|56 [[бит]]}}. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:
* [[Режим шифрования#Electronic Codebook (ECB)|ECB]] ({{lang-en|'''e'''lectronic '''c'''ode '''b'''ook}}) — режим «электронной кодовой книги» (простая замена);
* [[Режим шифрования#Cipher Block Chaining (CBC)|CBC]] ({{lang-en|'''c'''ipher '''b'''lock '''c'''haining}}) — режим сцепления блоков;
* [[Режим шифрования#Cipher Feedback (CFB)|CFB]] ({{lang-en|'''c'''ipher '''f'''eed '''b'''ack}}) — режим обратной связи по [[шифротекст]]у;
* [[Режим шифрования#Output Feedback (OFB)|OFB]] ({{lang-en|'''o'''utput '''f'''eed '''b'''ack}}) — режим обратной связи по выходу;
* [[Counter Mode (CTR)|Counter Mode (CM)]] — режим счётчика.

Прямым развитием DES в настоящее время является алгоритм [[3DES|Triple DES]] (3DES). В 3DES шифрование/расшифрование выполняются путём троекратного выполнения алгоритма DES.

== История ==
В [[1972 год]]у было проведено исследование потребности правительства [[США]] в компьютерной безопасности. Американское «национальное бюро стандартов» (НБС) (ныне известное, как [[NIST]] — «национальный институт стандартов и технологий») определило необходимость в общеправительственном стандарте шифрования некритичной информации.

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

[[17 марта]] [[1975 год]]а предложенный алгоритм DES был издан в «Федеральном реестре». В [[1976 год]]у для обсуждения DES было проведено два открытых симпозиума. На симпозиумах жёсткой критике подверглись изменения, внесённые в алгоритм организацией АНБ. АНБ уменьшило первоначальную длину ключа и S-блоки (блоки подстановки), критерии проектирования которых не раскрывались. АНБ подозревалось в сознательном ослаблении алгоритма с той целью, чтобы АНБ могло легко просматривать зашифрованные сообщения. Сенат США проверил действия АНБ и в [[1978 год]]у опубликовал заявление, в котором сообщалось следующее:
* в процессе разработки алгоритма представители АНБ убедили создателей DES в том, что уменьшенной длины ключа более чем достаточно для всех коммерческих приложений;
* представители АНБ косвенно помогали в разработке S-перестановок;
* окончательная версия алгоритма была, по мнению проверяющих, лучшим алгоритмом шифрования, к тому же лишённым статистической или математической слабости;
* представители АНБ никогда не вмешивались в разработку алгоритма DES.

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

Алгоритм DES удалось «взломать» за 39 дней с помощью огромной сети, состоящей из десятков тысяч компьютеров<ref>{{Cite web |url=https://www.distributed.net/DES |title=distributed.net: проект RSA DES II-1 |access-date=2018-01-01 |archive-date=2017-12-31 |archive-url=https://web.archive.org/web/20171231111343/http://www.distributed.net/DES |deadlink=no }}</ref>.

Общественная организация «[[Electronic Frontier Foundation|EFF]]», занимающаяся проблемами информационной безопасности и личной тайны в сети [[Интернет]], инициировала исследование «DES Challenge II» с целью выявления проблем DES. В рамках исследования сотрудники фирмы «RSA Laboratory» построили суперкомпьютер стоимостью 250 тыс. долл. В [[1998 год]]у суперкомпьютер выполнил расшифровку данных, закодированных методом DES с использованием 56-битного ключа, менее чем за три дня. Суперкомпьютер получил название «EFF DES Cracker». Специально по этому случаю учёные организовали пресс-конференцию и с беспокойством говорили о том, что злоумышленники вряд ли упустят случай воспользоваться подобной уязвимостью.

Некоторые правительственные чиновники и специалисты утверждали, что для взлома кода DES требуется суперкомпьютер стоимостью в несколько миллионов долларов. «Правительству пора признать ненадёжность DES и поддержать создание более мощного стандарта шифрования», — сказал президент EFF Барри Штайнхардт. Экспортные ограничения, накладываемые правительством США, касаются технологий шифрования по ключам длиной более 40 бит. Однако, как показали результаты эксперимента RSA Laboratory, существует возможность взлома и более мощного кода. Проблема усугублялась тем, что стоимость постройки подобного суперкомпьютера неуклонно снижалась. «Через четыре-пять лет такие компьютеры будут стоять в любой школе», — заявил Джон Гилмор, руководитель проекта «DES Challenge» и один из основателей EFF.

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

== Блочный шифр ==
{{main|Блочный шифр}}

{{anchor|picture_1}}
[[Файл:СетьФ1.PNG|frame|<center>Рис. 1. Прямое преобразование сетью Фейстеля</center>|right]]

{{anchor|picture_2}}
[[Файл:СетьФ2.PNG|frame|<center>Рис. 2. Обратное преобразование сетью Фейстеля</center>|right]]

Входными данными для [[блочный шифр|блочного шифра]] служат:
* блок размером n бит;
* ключ размером k бит.

На выходе (после применения шифрующих преобразований) получается зашифрованный блок размером n бит, причём незначительные различия входных данных, как правило, приводят к существенному изменению результата.

Блочные шифры реализуются путём многократного применения к блокам исходного [[Открытый текст|текста]] некоторых базовых преобразований.

Базовые преобразования:
* сложное преобразование на одной локальной части блока;
* простое преобразование между частями блока.

Так как преобразования производятся поблочно, требуется разделение исходных данных на блоки необходимого размера. При этом формат исходных данных не имеет значения (будь то текстовые документы, изображения или другие файлы). Данные должны интерпретироваться в двоичном виде (как последовательность нулей и единиц) и только после этого должны разбиваться на блоки. Все вышеперечисленное может осуществляться как программными, так и аппаратными средствами.

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

== Схема шифрования алгоритма DES ==
[[Файл:DES algorithm scheme.png|thumb|400px|<center>Рис.3 Схема шифрования алгоритма DES</center>|right]]
[[Файл:DES Encryption Scheme - Russian Language.png|frame|<center>Рис.4 Подробная схема шифрования алгоритма DES</center>|right]]

Схема шифрования алгоритма DES указана на Рис.3.

Исходный текст — блок 64 бит.

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

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

{| class="wikitable"
|+ Таблица 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 бита результирующего блока <math>\mathrm{IP}(T)</math> после начальной перестановки <math>\mathrm{IP}</math> являются битами 58, 50, 42 входного блока <math>T</math>, а его 3 последние бита являются битами 23, 15, 7 входного блока.

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

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

Разбить IP(T) на две части <math>L_0, R_0</math>, где <math>L_0, R_0</math> — соответственно 32 старших битов и 32 младших битов блока <math>T_0</math> IP(T)= <math>L_0R_0</math>

Пусть <math>T_{i-1} = L_{i-1}R_{i-1}</math> результат (i-1) итерации, тогда результат i-ой итерации <math>T_i = L_iR_i</math> определяется:

: <math>L_i = R_{i-1}</math>
: <math>R_i = L_{i-1}\oplus f(R_{i-1},k_i)</math>

Левая половина <math>L_i</math> равна правой половине предыдущего вектора <math>L_{i-1}R_{i-1}</math>. А правая половина <math>R_i</math> — это битовое сложение <math>L_{i-1}</math> и <math>f(R_{i-1},k_i)</math> по модулю 2.

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

=== Основная функция шифрования (функция Фейстеля) ===
[[Аргумент (программирование)|Аргумент]]ами функции <math>f</math> являются 32-битовый [[Индексный массив|вектор]] <math>R_{i-1}</math> и 48-битовый ключ <math>k_i</math>, который является результатом преобразования 56-битового исходного ключа шифра <math>k</math>.
Для вычисления функции <math>f</math> последовательно используются
#[[Функция (программирование)|функция]] расширения <math>\mathrm{E}</math>,
# сложение по модулю 2 с ключом <math>k_i</math>
# преобразование <math>\mathrm{S}</math>, состоящее из 8 преобразований <math>\mathrm{S}</math>-блоков <math>\mathrm{S}_1,\mathrm{S}_2,\mathrm{S}_3\ldots\ \mathrm{S}_8</math>,
# [[перестановка]] <math>\mathrm{P}</math>.

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

{| class="wikitable"
|+ Таблица 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
|}

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

:<math>\mathrm{E}(R_{i-1})\oplus k_i= B_1B_2...B_8</math>

Каждый <math>B_j</math> является 6-битовым блоком.
Далее каждый из блоков <math>B_j</math> трансформируется в 4-битовый [[блок]] <math>B'_j</math> с помощью преобразований <math>S_j</math>. Преобразования <math>S_j</math> определяются таблицей 3.

[[Файл:FuncFFF.PNG|frame|<center>Рис.5 Схема работы функции f</center>|right]]
{| class="wikitable"
|+ Таблица 3. Преобразования <math>S_i</math>, 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||style="background: #90ff00"|
|-
!1||0|||15||7||4||14||2||13||1||10||6||12||11||9||5||3||8||style="background: #90ff00"|<math>S_1</math>
|-
!2||4||1||14||8||13||6||2||11||15||12||9||7||3||10||5||0||style="background: #90ff00"|
|-
!3||15||12||8||2||4||9||1||7||5||11||3||14||10||0||6||13||style="background: #90ff00"|
|-
|
|-
!0||15||1||8||14||6||11||3||4||9||7||2||13||12||0||5||10||style="background: #10bb00"|
|-
!1||3||13||4||7||15||2||8||14||12||0||1||10||6||9||11||5||style="background: #10bb00"|<math>S_2</math>
|-
!2||0||14||7||11||10||4||13||1||5||8||12||6||9||3||2||15||style="background: #10bb00"|
|-
!3||13||8||10||1||3||15||4||2||11||6||7||12||0||5||14||9||style="background: #10bb00"|
|-
|
|-
!0||10||0||9||14||6||3||15||5||1||13||12||7||11||4||2||8||style="background: #90ff00"|
|-
!1||13||7||0||9||3||4||6||10||2||8||5||14||12||11||15||1||style="background: #90ff00"| <math>S_3</math>
|-
!2||13||6||4||9||8||15||3||0||11||1||2||12||5||10||14||7||style="background: #90ff00"|
|-
!3||1||10||13||0||6||9||8||7||4||15||14||3||11||5||2||12||style="background: #90ff00"|
|-
|
|-
!0||7||13||14||3||0||6||9||10||1||2||8||5||11||12||4||15||style="background: #10bb00"|
|-
!1||13||8||11||5||6||15||0||3||4||7||2||12||1||10||14||9||style="background: #10bb00"|<math>S_4</math>
|-
!2||10||6||9||0||12||11||7||13||15||1||3||14||5||2||8||4||style="background: #10bb00"|
|-
!3||3||15||0||6||10||1||13||8||9||4||5||11||12||7||2||14||style="background: #10bb00"|
|-
|
|-
!0||2||12||4||1||7||10||11||6||8||5||3||15||13||0||14||9||style="background: #90ff00"|
|-
!1||14||11||2||12||4||7||13||1||5||0||15||10||3||9||8||6||style="background: #90ff00"|<math>S_5</math>
|-
!2||4||2||1||11||10||13||7||8||15||9||12||5||6||3||0||14||style="background: #90ff00"|
|-
!3||11||8||12||7||1||14||2||13||6||15||0||9||10||4||5||3||style="background: #90ff00"|
|-
|
|-
!0||12||1||10||15||9||2||6||8||0||13||3||4||14||7||5||11||style="background: #10bb00"|
|-
!1||10||15||4||2||7||12||9||5||6||1||13||14||0||11||3||8||style="background: #10bb00"|<math>S_6</math>
|-
!2||9||14||15||5||2||8||12||3||7||0||4||10||1||13||11||6||style="background: #10bb00"|
|-
!3||4||3||2||12||9||5||15||10||11||14||1||7||6||0||8||13||style="background: #10bb00"|
|-
|
|-
!0||4||11||2||14||15||0||8||13||3||12||9||7||5||10||6||1||style="background: #90ff00"|
|-
!1||13||0||11||7||4||9||1||10||14||3||5||12||2||15||8||6||style="background: #90ff00"|<math>S_7</math>
|-
!2||1||4||11||13||12||3||7||14||10||15||6||8||0||5||9||2||style="background: #90ff00"|
|-
!3||6||11||13||8||1||4||10||7||9||5||0||15||14||2||3||12||style="background: #90ff00"|
|-
|
|-
!0||13||2||8||4||6||15||11||1||10||9||3||14||5||0||12||7||style="background: #10bb00"|
|-
!1||1||15||13||8||10||3||7||4||12||5||6||11||0||14||9||2||style="background: #10bb00"|<math>S_8</math>
|-
!2||7||11||4||1||9||12||14||2||0||6||10||13||15||3||5||8||style="background: #10bb00"|
|-
!3||2||1||14||7||4||10||8||13||15||12||9||0||3||5||6||11||style="background: #10bb00"|
|-
|}

Предположим, что <math>B_3 = 101111</math>, и мы хотим найти <math>B'_3</math>. Первый и последний разряды <math>B_3</math> являются двоичной записью числа а, 0<=a<=3, средние 4 разряда представляют число b, 0<=b<=15. Строки таблицы S3 нумеруются от 0 до 3, столбцы таблицы S3 нумеруются от 0 до 15. Пара чисел (а, b) определяет число, находящееся в пересечении строки а и столбца b.
Двоичное представление этого числа дает <math>B'_3</math> . В нашем случае <math>a = 11_2 = 3</math>, <math>b = 0111_2 = 7</math>, а число, определяемое парой (3,7), равно 7. Его двоичное представление <math>B'_3</math>=0111.
Значение функции <math>f(R_{i-1},k_i)</math> (32 [[бит]]) получается перестановкой Р, применяемой к 32-битовому блоку <math>B'_1B'_2...B'_8</math>. [[Перестановка]] Р задана таблицей 4.

{| class="wikitable"
|+ Таблица 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
|}
<math>f(R_{i-1},k_i) = P(B'_1B'_2...B'_8)</math><br>
Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f — это биты 16, 7, 20, 21 вектора <math>B'_1B'_2...B'_8</math>

=== Генерирование ключей <math>k_i</math>===
Ключи <math>k_i</math> получаются из начального ключа <math>k</math> (56 [[бит]] = 7 байтов или 7 символов в [[ASCII]]) следующим образом. Добавляются биты в позиции 8, 16, 24, 32, 40, 48, 56, 64 ключа <math>k</math> таким образом, чтобы каждый [[байт]] содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определена в таблице 5.

[[Файл:DES Encryption Decoding Scheme - Russian Language.png|frame|<center>Рис.6 Схема расшифрования алгоритма DES</center>|right]]
{| class="wikitable"
|+ Таблица 5.
|-
|57||49||41||33||25||17||9||1||58||50||42||34||26||18||style="background: #90ff00"|<math>C_0</math>
|-
|10||2||59||51||43||35||27||19||11||3||60||52||44||36||style="background: #90ff00"|
|-
|63||55||47||39||31||23||15||7||62||54||46||38||30||22||style="background: #10bb00"|<math>D_0</math>
|-
|14||6||61||53||45||37||29||21||13||5||28||20||12||4||style="background: #10bb00"|
|}

Эта перестановка определяется двумя блоками <math>C_0</math> и <math>D_0</math> по 28 [[бит]] каждый.
Первые 3 бита <math>C_0</math> есть биты 57, 49, 41 расширенного ключа. А первые три бита <math>D_0</math> есть биты 63, 55, 47 расширенного ключа.
<math>C_i, D_i</math> i=1,2,3…получаются из <math>C_{i-1}, D_{i-1}</math> одним или двумя левыми циклическими сдвигами согласно таблице 6.

{| class="wikitable"
|+ Таблица 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
|}

Ключ <math>k_i</math>, i=1,…16 состоит из 48 бит, выбранных из битов вектора <math>C_iD_i</math> (56 [[бит]]) согласно таблице 7.
Первый и второй биты <math>k_i</math> есть биты 14, 17 вектора <math>C_iD_i</math>

{| class="wikitable"
|+ Таблица 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
|}

=== Конечная перестановка ===
Конечная [[перестановка]] <math>\mathrm{IP}^{-1}</math> действует на <math>T^{-1}_{16}</math> (где <math>T^{-1}_{16} = R_{16} + L_{16}</math>) и является обратной к первоначальной перестановке. Конечная перестановка определяется таблицей 8.

{| class="wikitable"
|+ Таблица 8. Обратная [[перестановка]] <math>\mathrm{IP}^{-1}</math>
|-
|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
|}

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

<math>R_{i-1} = L_i</math><br>
<math>L_{i-1} = R_i \oplus f(L_i,k_i)</math>

Схема расшифрования указана на Рис.6.<br>
Ключ <math>k_i</math>, i=16,…,1, функция f, перестановка IP и <math>IP^{-1}</math> такие же, как и в процессе шифрования. Алгоритм генерации ключей зависит только от ключа пользователя, поэтому при расшифровании они идентичны.

== Псевдокод ==
<syntaxhighlight>
// Все переменные беззнаковые 64-битные

// Предварительная обработка: дополнение разницы в размере в байтах
Дополнить сообщение до кратного 64 битам

var key // Ключи, предоставленные пользователем
var keys[16]
var left, right

// Генерация ключей

// PC1 (64 бита в 56 бит)
key := перестановка(key, PC1)
left := (key сдвиг вправо на 28 бит) and 0xFFFFFFF
right := key и 0xFFFFFFF

for i от 0 до 16 do
	right := right циклический сдвиг влево на KEY_shift[i]
	left := left циклический сдвиг влево на KEY_shift[i]
	var concat := (left сдвиг влево на 28 бит) or right
	// PC2 (56 бит в 48 бит)
	keys[i] := перестановка(concat, PC2)
end for

// Для расшифрования сообщения изменить порядок ключей
if decrypt do
	reverse keys
end if

// Шифрование или расшифрование
for каждый 64-битный блок дополненного сообщения do
	var tmp

	// IP
	chunk := перестановка(chunk, IP)
	left := chunk сдвиг вправо на 32 бита
	right := chunk and 0xFFFFFFFF
	for i от 0 до 16 do
		tmp := right
		// E (32 бита в 48 бит)
		right := расширение(right, E)
		right := right xor keys[i]
		// Подстановка (48 бит в 32 бита)
		right := подстановка(right)
		// P
		right := перестановка(right, P)
		right := right xor left
		left := tmp
	end for
	// Объединить right и left
	var cipher_chunk := (right сдвиг влево на 32 бита) or left
	// Конечная перестановка
	cipher_chunk := перестановка(cipher_chunk, FP)
end for
</syntaxhighlight>

== Режимы использования DES ==
{{main|Режим шифрования}}
DES может использоваться в четырёх режимах.

# [[Режим электронной кодовой книги]] ([[Electronic Codebook|ECB]] — [[Electronic Codebook]]): обычное использование DES как [[блочный шифр|блочного шифра]]. Шифруемый текст разбивается на блоки, при этом каждый блок шифруется отдельно, не взаимодействуя с другими блоками (см. Рис.7).
#: [[Файл:ECB1.JPG|frame|<center>Рис.7 Режим электронной кодовой книги — ECB</center>|center]]
# [[Режим сцепления блоков шифротекста]] ([[Cipher Block Chaining|СВС]] — [[Cipher Block Chaining]]) (см. Рис.8). Каждый очередной блок <math>M_i</math> i>=1, перед зашифровыванием складывается по модулю 2 с предыдущим блоком зашифрованного текста <math>C_{i-1}</math>. Вектор <math>C_0</math> — начальный вектор, он меняется ежедневно и хранится в секрете.
#:[[Файл:Diagram of Cipher Block Chaining with Russian text.png|frame|<center>Рис.8 Режим сцепления блоков — СВС</center>|center]]
# [[Режим обратной связи по шифротексту]] ([[Cipher Feedback]]) (см. Рис.9). В режиме [[CFB]] вырабатывается блочная «[[блочная гамма|гамма]]» <math>Z_0, Z_1,... </math><math>Z_i=DES_k(C_{i-1})</math> <math>C_i = M_i \oplus Z_i</math>. Начальный вектор <math>C_0</math> является синхропосылкой и предназначен для того, чтобы разные наборы данных шифровались по-разному с использованием одного и того же секретного ключа. Синхропосылка посылается получателю в открытом виде вместе с зашифрованным файлом. Алгоритм DES, в отличие от предыдущих режимов, используется только как шифрование (в обоих случаях).
#: [[Файл:Cfb-des.ru.svg|thumb|<center>Рис.9 Режим обратной связи по шифротексту — CFB</center>|center|615px]]
# [[Режим обратной связи по выходу]] ([[Output Feedback|OFB]] — [[Output Feedback]]) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма» <math>Z_0, Z_1,...</math> <math>Z_i=DES_k(Z_{i-1})
C_i = M_i \oplus Z_i </math>, i>=1. Режим также использует DES только как шифрование (в обоих случаях).
#: [[Файл:OFB.PNG|frame|<center>Рис.10 Режим обратной связи по выходу — OFB</center>|center]]

'''Достоинства и недостатки режимов:'''
* В режимах [[Electronic Codebook|ECB]] и [[Output Feedback|OFB]] искажение при передаче одного 64-битового блока шифротекста <math> C_i</math> приводит к искажению после расшифрования только соответствующего открытого блока <math> M_i</math>, поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.

== Криптостойкость алгоритма DES ==
Нелинейность преобразований в DES средствами только S-блоков и использование слабых S-блоков позволяет осуществлять контроль над шифрованной перепиской. Выбор S-блоков требует соблюдения нескольких условий:
* Каждая строка каждого блока должна быть перестановкой множества {0, 1, 2, …, 15}
* S-блоки не должны являться линейной или афинной функцией своих аргументов.
* Изменение одного бита на входе S-блока должно приводить к изменению, по крайней мере, двух битов на выходе.
* Для каждого S-блока и любого аргумента ''х'' значение ''S''(''x'') и <math>S(x \oplus 001100_2) </math> должны различаться, по крайней мере, двумя битами.

Из-за небольшого числа возможных ключей (всего <math>2^{56}</math>), появляется возможность их полного перебора на быстродействующей вычислительной технике за реальное время. В [[1998 год]]у [[Electronic Frontier Foundation]], используя специальный компьютер DES-Cracker, удалось взломать DES за 3 дня.

=== Слабые ключи ===
Слабыми ключами называется ключи ''k'' такие, что <math>DES_k(DES_k(x)) = x</math>, где ''x'' — 64-битный блок.

Известны 4 слабых ключа, они приведены в таблице 9.
Для каждого слабого ключа существует <math>2^{32}</math> [[неподвижная точка|неподвижные точки]], то есть таких 64-битных блоков ''х'', для которых <math>DES_k(x) = x</math>.

{| class="wikitable"
|+ Таблица 9. DES-Слабые ключи
|-
|Слабые ключи (hexadecimal)||<math>C_0</math>||<math>D_0</math>
|-
|0101-0101-0101-0101||<math>[0]^{28}</math>||<math>[0]^{28}</math>
|-
|FEFE-FEFE-FEFE-FEFE||<math>[1]^{28}</math>||<math>[1]^{28}</math>
|-
|1F1F-1F1F-0E0E-0E0E||<math>[0]^{28}</math>||<math>[1]^{28}</math>
|-
|E0E0-E0E0-F1F1-F1F1||<math>[1]^{28}</math>||<math>[0]^{28}</math>
|}
<math>[0]^{28}</math> обозначает вектор, состоящий из 28 нулевых битов.

=== Частично слабые ключи ===
В алгоритме DES существуют слабые и частично слабые ключи. Частично слабые ключи — это такие пары ключей <math>(k_1, k_2)</math>, что <math>DES_{k1}(DES_{k2}(x)) = x.</math>

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

{| class="wikitable"
|+ Таблица 10. Частично слабые ключи
|-
|<math>C_0</math>||<math>D_0</math>||Пары частично слабых ключей||<math>C_0</math>||<math>D_0</math>
|-
|<math>[01]^{14}</math>||<math>[01]^{14}</math>||01FE-01FE-01FE-01FE,----FE01-FE01-FE01-FE01||<math>[10]^{14}</math>||<math>[10]^{14}</math>
|-
|<math>[01]^{14}</math>||<math>[01]^{14}</math>||1FE0-1FE0-1FE0-1FE0,----E0F1-E0F1-E0F1-E0F1||<math>[10]^{14}</math>||<math>[10]^{14}</math>
|-
|<math>[01]^{14}</math>||<math>[0]^{28}</math>||01E0-01E0-01F1-01F1,----E001-E001-F101-F101||<math>[10]^{14}</math>||<math>[0]^{28}</math>
|-
|<math>[01]^{14}</math>||<math>[1]^{28}</math>||1FFE-1FFE-0EFE-0EFE,----FE1F-FE1F-FE0E-FE0E||<math>[0]^{28}</math>||<math>[1]^{28}</math>
|-
|<math>[0]^{28}</math>||<math>[01]^{14}</math>||011F-011F-010E-010E,----1F01-1F01-0E01-0E01||<math>[0]^{28}</math>||<math>[10]^{14}</math>
|-
|<math>[1]^{28}</math>||<math>[01]^{14}</math>||E0FE-E0FE-F1FE-F1FE,----FEE0-FEE0-FEF1-FEF1||<math>[1]^{28}</math>||<math>[10]^{14}</math>
|}

=== Известные атаки на DES ===
{| class="wikitable"
|+ Таблица 11. Известные атаки на DES.
|-
|Методы атаки||Известные откр. тексты||Выбранные отк. тексты||Объём памяти||Количество операций
|-
|Полный поиск||qweqweqweqerqe
|<nowiki>-</nowiki>||Незначительный||<math>2^{55}</math>
|-
|Линейный Криптоанализ||<math>2^{43} (85\%)</math>||-||Для текста||<math>2^{43}</math>
|-
|Линейный Криптоанализ||<math>2^{38} (10\%)</math>||-||Для текста||<math>2^{50}</math>
|-
|Диффер. Криптоанализ||-||<math>2^{47}</math>||Для текста||<math>2^{47}</math>
|-
|Диффер. Криптоанализ||<math>2^{55}</math>||-||Для текста||<math>2^{55}</math>
|}

* Метод [[Полный перебор|полного перебора]] требует одну известную пару шифрованного и расшифрованного текста, незначительный объём памяти, и его выполнение требует около <math>2^{55}</math> шагов.
* [[Дифференциальный криптоанализ]] — первую такую атаку на DES заявили [[Бихам, Эли|Бихам]] и [[Шамир, Ади|Шамир]]. Эта атака требует шифрования <math>2^{47}</math> открытых текстов, выбранных нападающим, и для её выполнения нужны примерно <math>2^{47}</math> шагов. Теоретически являясь точкой разрыва, эта атака непрактична из-за чрезмерных требований к подбору данных и сложности организации атаки по выбранному открытому тексту. Сами авторы этой атаки Biham и Shamir заявили, что считают DES защищённым для такой атаки.
* [[Линейный криптоанализ]] разработан Matsui. Этот метод позволяет восстановить ключ DES с помощью анализа <math>2^{43}</math> известных открытых текстов, при этом требуется примерно <math>2^{43}</math> шагов для выполнения. Первый экспериментальный криптоанализ 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 имеет вид <math>DES(k_3,DES(k_2,DES(k_1,M)))</math>, где <math>k_1,k_2,k_3</math> ключи для каждого шифра DES. Это вариант известен как в ЕЕЕ, так как три DES операции являются шифрованием. Существует 3 типа алгоритма 3DES:

:* [[DES-EEE3]]: Шифруется три раза с 3 разными ключами.
:* [[DES-EDE3]]: 3DES операции шифровка-расшифровка-шифровка с 3 разными ключами.
:* [[DES-EEE2]] и [[DES-EDE2]]: Как и предыдущие, за исключением того, что первая и третья операции используют одинаковый ключ.

: Самый популярный тип при использовании 3DES — это DES-EDE3, для него алгоритм выглядит так:'''
: [[Шифрование|Зашифрование]]: <math>C = E_{k_3}(E^{-1}_{k_2}(E_{k_1}(P)))</math>.
: [[Расшифрование]]: <math>P = E^{-1}_{k_1}(E_{k_2}(E^{-1}_{k_3}(C)))</math>

: При выполнении алгоритма 3DES ключи могут выбрать так:
:* <math>k_1,k_2,k_3</math> независимы.
:* <math>k_1,k_2</math> независимы, а <math>k_1 = k_3</math>
:* <math>k_1=k_2=k_3</math>.

* Метод [[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 с независимыми подключами требуется <math>2^{61}</math> выбранных открытых текстов, в то время как для линейного криптоанализа требуется <math>2^{60}</math> известных открытых текстов.

== Применение ==
DES был национальным стандартом [[США]] в [[1977]]—[[1980]] гг., но в настоящее время DES используется (с ключом длины 56 бит) только для устаревших систем, чаще всего используют его более криптоустойчивый вид ([[3DES]], [[DESX]]). 3DES является простой эффективной заменой DES, и сейчас он рассмотрен как стандарт. В ближайшее время DES и [[3DES|Triple DES]] будут заменены алгоритмом [[Advanced Encryption Standard|AES]] (Advanced Encryption Standard — Расширенный Стандарт Шифрования).

Алгоритм DES широко применяется для защиты финансовой информации: так, модуль [[Thales|THALES]] ({{iw|Racal||en|}}) HSM RG7000 полностью поддерживает операции [[3DES|TripleDES]] для эмиссии и обработки кредитных карт [[VISA]], EuroPay и проч. Канальные шифраторы THALES (Racal) DataDryptor [[2000]] используют [[3DES|TripleDES]] для прозрачного шифрования потоков информации. Также алгоритм DES используется во многих других устройствах и решениях THALES-eSECURITY.

== Примечания ==
{{примечания}}

== Литература ==
* {{книга |автор=А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин |название=Основы криптографии}}
* {{книга |автор=A. Menezes, Pvan Oorschot, S. Vanstone |ссылка=http://www.cacr.math.uwaterloo.ca/hac |название=Handbook of Applied Cryptography}}
* {{книга |автор=Семенов Ю. А. |ссылка=http://book.itep.ru/6/des_641.htm |название=Алгоритм DES}}
* [http://everything2.com/title/DES Query for DES]

{{симметричные криптоалгоритмы}}

{{переработать|дата=2008-12-16}}

[[Категория:Блочные шифры]]
[[Категория:Сеть Фейстеля]]
[[Категория:Стандарты криптографии]]