DES

Материал из Википедии — свободной энциклопедии
Текущая версия страницы покане проверялась опытными участниками и может значительно отличаться отверсии, проверенной 22 марта 2015 года; проверки требуют86 правок.
Перейти к навигацииПерейти к поиску
У этого термина существуют и другие значения, см.DES (значения).
DES, Data Encryption Standard
СоздательIBM
Создан1977
Опубликован1977 год
Размер ключа56 бит + 8 проверочных
Размер блока64 бит
Число раундов16
ТипСеть Фейстеля
Логотип Викисклада Медиафайлы на Викискладе

DES (англ. Data Encryption Standard) — алгоритм длясимметричногошифрования, разработанный фирмойIBM и утверждённый правительствомСША в 1977 году как официальный стандарт (FIPS 46-3). Размер блока для DES равен64битам. В основе алгоритма лежитсеть Фейстеля с 16 циклами (раундами) иключом, имеющим длину56бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:

  • ECB (англ. electroniccodebook) — режим «электронной кодовой книги» (простая замена);
  • CBC (англ. cipherblockchaining) — режим сцепления блоков;
  • CFB (англ. cipherfeedback) — режим обратной связи пошифротексту;
  • OFB (англ. outputfeedback) — режим обратной связи по выходу;
  • Counter Mode (CM) — режим счётчика.

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

Содержание

История

[править |править код]

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

НБС проконсультировалось сАНБ (агентством национальной безопасности США) и15 мая1973 года объявило первый конкурс на создание шифра. Были сформулированы строгие требования к новому шифру. ФирмаIBM представила на конкурсе разработанный ею шифр, называемый «Люцифер» (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 дней с помощью огромной сети, состоящей из десятков тысяч компьютеров[1].

Общественная организация «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, необходимо рассмотреть принцип работыблочного шифра,сеть Фейстеля.

Блочный шифр

[править |править код]
Основная статья:Блочный шифр

Рис. 1. Прямое преобразование сетью Фейстеля

Рис. 2. Обратное преобразование сетью Фейстеля

Входными данными дляблочного шифра служат:

  • блок размером n бит;
  • ключ размером k бит.

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

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

Базовые преобразования:

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

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

Преобразования сетью Фейстеля

[править |править код]

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

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

[править |править код]
Рис.3 Схема шифрования алгоритма DES
Рис.4 Подробная схема шифрования алгоритма DES

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

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

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

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

[править |править код]

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

Таблица 1. Начальнаяперестановка IP
585042342618102605244362820124
625446383022146645648403224168
57494133251791595143352719113
615345372921135635547393123157

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

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

[править |править код]

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

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

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

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

Li=Ri1{\displaystyle L_{i}=R_{i-1}}
Ri=Li1f(Ri1,ki){\displaystyle R_{i}=L_{i-1}\oplus f(R_{i-1},k_{i})}

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

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

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

[править |править код]

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

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

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

Таблица 2. Функция расширения E
3212345
456789
8910111213
121314151617
161718192021
202122232425
242526272829
28293031321

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

E(Ri1)ki=B1B2...B8{\displaystyle \mathrm {E} (R_{i-1})\oplus k_{i}=B_{1}B_{2}...B_{8}}

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

Рис.5 Схема работы функции f
Таблица 3. ПреобразованияSi{\displaystyle S_{i}}, i=1…8
0123456789101112131415
01441312151183106125907
10157414213110612119538S1{\displaystyle S_{1}}
24114813621115129731050
31512824917511314100613
01518146113497213120510
13134715281412011069115S2{\displaystyle S_{2}}
20147111041315812693215
31381013154211671205149
01009146315511312711428
11370934610285141211151S3{\displaystyle S_{3}}
21364981530111212510147
31101306987415143115212
07131430691012851112415
11381156150347212110149S4{\displaystyle S_{4}}
21069012117131513145284
33150610113894511127214
02124171011685315130149
11411212471315015103986S5{\displaystyle S_{5}}
24211110137815912563014
31181271142136150910453
01211015926801334147511
11015427129561131401138S6{\displaystyle S_{6}}
29141552812370410113116
34321295151011141760813
04112141508133129751061
11301174911014351221586S7{\displaystyle S_{7}}
21411131237141015680592
36111381410795015142312
01328461511110931450127
11151381037412561101492S8{\displaystyle S_{8}}
27114191214206101315358
32114741081315129035611

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

Таблица 4. Перестановка P
167202129122817
11523265183110
282414322739
19133062211425

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

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

[править |править код]

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

Рис.6 Схема расшифрования алгоритма DES
Таблица 5.
57494133251791585042342618C0{\displaystyle C_{0}}
10259514335271911360524436
635547393123157625446383022D0{\displaystyle D_{0}}
1466153453729211352820124

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

Таблица 6.
i12345678910111213141516
Число сдвига1122222212222221

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

Таблица 7.
141711241532815621102319124
26816727201324152313747553040
51453348444939563453464250362932

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

[править |править код]

КонечнаяперестановкаIP1{\displaystyle \mathrm {IP} ^{-1}} действует наT161{\displaystyle T_{16}^{-1}} (гдеT161=R16+L16{\displaystyle T_{16}^{-1}=R_{16}+L_{16}}) и является обратной к первоначальной перестановке. Конечная перестановка определяется таблицей 8.

Таблица 8. ОбратнаяперестановкаIP1{\displaystyle \mathrm {IP} ^{-1}}
408481656246432397471555236331
386461454226230375451353216129
364441252206028353431151195927
34242105018582633141949175725

Схема расшифрования

[править |править код]

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

Ri1=Li{\displaystyle R_{i-1}=L_{i}}
Li1=Rif(Li,ki){\displaystyle L_{i-1}=R_{i}\oplus f(L_{i},k_{i})}

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

Псевдокод

[править |править код]
// Все переменные беззнаковые 64-битные// Предварительная обработка: дополнение разницы в размере в байтахДополнить сообщение до кратного 64 битамvar key // Ключи, предоставленные пользователемvar keys[16]var left, right// Генерация ключей// PC1 (64 бита в 56 бит)key := перестановка(key, PC1)left := (key сдвиг вправо на 28 бит) and 0xFFFFFFFright := key и 0xFFFFFFFfor i от 0 до 16 doright := 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 doreverse keysend if// Шифрование или расшифрованиеfor каждый 64-битный блок дополненного сообщения dovar tmp// IPchunk := перестановка(chunk, IP)left := chunk сдвиг вправо на 32 битаright := chunk and 0xFFFFFFFFfor i от 0 до 16 dotmp := right// E (32 бита в 48 бит)right := расширение(right, E)right := right xor keys[i]// Подстановка (48 бит в 32 бита)right := подстановка(right)// Pright := перестановка(right, P)right := right xor leftleft := tmpend for// Объединить right и leftvar cipher_chunk := (right сдвиг влево на 32 бита) or left// Конечная перестановкаcipher_chunk := перестановка(cipher_chunk, FP)end for

Режимы использования DES

[править |править код]
Основная статья:Режим шифрования

DES может использоваться в четырёх режимах.

  1. Режим электронной кодовой книги (ECB —Electronic Codebook): обычное использование DES какблочного шифра. Шифруемый текст разбивается на блоки, при этом каждый блок шифруется отдельно, не взаимодействуя с другими блоками (см. Рис.7).
    Рис.7 Режим электронной кодовой книги — ECB
  2. Режим сцепления блоков шифротекста (СВС —Cipher Block Chaining) (см. Рис.8). Каждый очередной блокMi{\displaystyle M_{i}} i>=1, перед зашифровыванием складывается по модулю 2 с предыдущим блоком зашифрованного текстаCi1{\displaystyle C_{i-1}}. ВекторC0{\displaystyle C_{0}} — начальный вектор, он меняется ежедневно и хранится в секрете.
    Рис.8 Режим сцепления блоков — СВС
  3. Режим обратной связи по шифротексту (Cipher Feedback) (см. Рис.9). В режимеCFB вырабатывается блочная «гамма»Z0,Z1,...{\displaystyle Z_{0},Z_{1},...}Zi=DESk(Ci1){\displaystyle Z_{i}=DES_{k}(C_{i-1})}Ci=MiZi{\displaystyle C_{i}=M_{i}\oplus Z_{i}}. Начальный векторC0{\displaystyle C_{0}} является синхропосылкой и предназначен для того, чтобы разные наборы данных шифровались по-разному с использованием одного и того же секретного ключа. Синхропосылка посылается получателю в открытом виде вместе с зашифрованным файлом. Алгоритм DES, в отличие от предыдущих режимов, используется только как шифрование (в обоих случаях).
    Рис.9 Режим обратной связи по шифротексту — CFB
  4. Режим обратной связи по выходу (OFB —Output Feedback) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма»Z0,Z1,...{\displaystyle Z_{0},Z_{1},...}Zi=DESk(Zi1)Ci=MiZi{\displaystyle Z_{i}=DES_{k}(Z_{i-1})C_{i}=M_{i}\oplus Z_{i}}, i>=1. Режим также использует DES только как шифрование (в обоих случаях).
    Рис.10 Режим обратной связи по выходу — OFB

Достоинства и недостатки режимов:

  • В режимахECB иOFB искажение при передаче одного 64-битового блока шифротекстаCi{\displaystyle C_{i}} приводит к искажению после расшифрования только соответствующего открытого блокаMi{\displaystyle M_{i}}, поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.

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

[править |править код]

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

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

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

Слабые ключи

[править |править код]

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

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

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

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

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

[править |править код]

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

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

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

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

[править |править код]
Таблица 11. Известные атаки на DES.
Методы атакиИзвестные откр. текстыВыбранные отк. текстыОбъём памятиКоличество операций
Полный поискqweqweqweqerqe-Незначительный255{\displaystyle 2^{55}}
Линейный Криптоанализ243(85%){\displaystyle 2^{43}(85\%)}-Для текста243{\displaystyle 2^{43}}
Линейный Криптоанализ238(10%){\displaystyle 2^{38}(10\%)}-Для текста250{\displaystyle 2^{50}}
Диффер. Криптоанализ-247{\displaystyle 2^{47}}Для текста247{\displaystyle 2^{47}}
Диффер. Криптоанализ255{\displaystyle 2^{55}}-Для текста255{\displaystyle 2^{55}}
  • Методполного перебора требует одну известную пару шифрованного и расшифрованного текста, незначительный объём памяти, и его выполнение требует около255{\displaystyle 2^{55}} шагов.
  • Дифференциальный криптоанализ — первую такую атаку на DES заявилиБихам иШамир. Эта атака требует шифрования247{\displaystyle 2^{47}} открытых текстов, выбранных нападающим, и для её выполнения нужны примерно247{\displaystyle 2^{47}} шагов. Теоретически являясь точкой разрыва, эта атака непрактична из-за чрезмерных требований к подбору данных и сложности организации атаки по выбранному открытому тексту. Сами авторы этой атаки Biham и Shamir заявили, что считают DES защищённым для такой атаки.
  • Линейный криптоанализ разработан Matsui. Этот метод позволяет восстановить ключ DES с помощью анализа243{\displaystyle 2^{43}} известных открытых текстов, при этом требуется примерно243{\displaystyle 2^{43}} шагов для выполнения. Первый экспериментальный криптоанализ 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(k3,DES(k2,DES(k1,M))){\displaystyle DES(k_{3},DES(k_{2},DES(k_{1},M)))}, гдеk1,k2,k3{\displaystyle k_{1},k_{2},k_{3}} ключи для каждого шифра DES. Это вариант известен как в ЕЕЕ, так как три DES операции являются шифрованием. Существует 3 типа алгоритма 3DES:
  • DES-EEE3: Шифруется три раза с 3 разными ключами.
  • DES-EDE3: 3DES операции шифровка-расшифровка-шифровка с 3 разными ключами.
  • DES-EEE2 иDES-EDE2: Как и предыдущие, за исключением того, что первая и третья операции используют одинаковый ключ.
Самый популярный тип при использовании 3DES — это DES-EDE3, для него алгоритм выглядит так:
Зашифрование:C=Ek3(Ek21(Ek1(P))){\displaystyle C=E_{k_{3}}(E_{k_{2}}^{-1}(E_{k_{1}}(P)))}.
Расшифрование:P=Ek11(Ek2(Ek31(C))){\displaystyle P=E_{k_{1}}^{-1}(E_{k_{2}}(E_{k_{3}}^{-1}(C)))}
При выполнении алгоритма 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 с независимыми подключами требуется261{\displaystyle 2^{61}} выбранных открытых текстов, в то время как для линейного криптоанализа требуется260{\displaystyle 2^{60}} известных открытых текстов.

Применение

[править |править код]

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

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

Примечания

[править |править код]
  1. distributed.net: проект RSA DES II-1  (неопр.). Дата обращения: 1 января 2018. Архивировано 31 декабря 2017 года.

Литература

[править |править код]
Перейти к шаблону «Симметричные криптосистемы»
Потоковые шифры
Сеть Фейстеля
SP-сеть
Другие
Эта статьянуждается в переработке.Пожалуйста, уточните проблему в статье с помощьюболее узкого шаблона.
Пожалуйста, улучшите статью в соответствии справилами написания статей.(16 декабря 2008)
Источник —https://ru.wikipedia.org/w/index.php?title=DES&oldid=142568544
Категории:
Скрытые категории: