ФЭНДОМ


DES, Data Encryption Standard
Создатель:

IBM

Создан:

1977 г.

Опубликован:

1977 г.

Размер ключа:

56 бит

Размер блока:

64 бит

Число раундов:

16

Тип:

Сеть Фейстеля


DES (Data Encruption Standart) — Симметричный алгоритм шифрования, в котором один ключ используется как и для шифрования так и для расшифрования данных. DES разрабртан фирмой IBM и утвержен правительством США в 1977 году как официальный стандарт (FTPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинирование нелинейного (S -блок) и линейного (перестановки E, IP, IP-1). Для DES рекомендовано несколько режимов: Режим электронной кодовой книги (EВС- Electronic Code Book), режим сцепления блоков (СВС- Cipher Block Chaining), режим обратной связи по шифртексту (CFB- Cipher Feed Back), режим обратной связи по выходу (OFB- Output Feed Back).

История Править

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

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

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

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

Блочный шифр Править

Файл:СетьФейстеля1.PNG
Файл:СетьФейстеля2.PNG

Алфавитом, на котором действует блочный шифр, является множетсво двоичных векторов блоков открытого текста одинаковой длины (64, 128,... бит).

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

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

- Сложное преобразование на одной локальной части блока.

- Простое преобразование между частями блока.

Так как объекты, на которые действует блочный шифр являются блоком, то один шаг при шифровании - это преобразование данных, которые должны зашифровать, в блоки.Данные могут сохранять в files .text, .word, .map, .jpg…При таком преобразовании во первых нужно сохранять данные в бинарном виде, потом разбить такие бинарные files в блоки, может есть еще другие способы.Все, сказаные здесь, могут осуществляться программами или аппаратами.

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

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

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

Файл:Шифрование.PNG
Файл:Code.PNG

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

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

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

Шифрованный текст – блок 64 бит.

Расмотрим подробную схему алгоримта DES:

L_i,L_i, i=1,2,\ldots левая и правая половины 64-битового блока L_iR_i

k_i – 48 битовые ключи, f – функция шифрования, IP - начальная перестановка, IP^{-1} – конечная перестановка.

Процесс шифрования.

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

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

585042342618102605244362820124
625446383022146645648403224168
57494133251791595143352719113
615345372921135635547393123157

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

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

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

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

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

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

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

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

Для вычисления функции f используются фукция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков S_1,S_2,S_3\ldots\ S_8, и перестановка P.

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

Таблица 2.Функция расширения E

3212345
456789
8910111213
121314151617
161718192021
202122232425
242526272829
28293031321

Первые три бита вектора E(R_{i-1}) являются битами 32, 1, 2 вектора R_{i-1}. По таблице 2 видно что биты 1,4,5,8,9,12,13,16,17,20,21,24,25,28,29,32 дублируются. Последние 3 биты вектора E(R_{i-1}) - это биты 31,32,1 вектора R_{i-1}. Полученный после перестановки блок E(R_{i-1}) складывается по модулю 2 с ключами k_i и затем представляются в виде восьми последовательных блоков B_1,B_2,...B_8.</br> E(R_{i-1})= B_1B_2...B_8</br>. Каждый B_j является 6-битовым блоком. Далее каждый из блоков B_j трансформируется в 4 битовой блок B'_j с помощью преобразований S_j. Преобразования S_j определяется таблицей 3.

Файл:FuncF.JPEG

Таблица 3.Преобразования S_i ,i=1...16

0123456789101112131415
01441312151183106125907
10157414213110612119538S_1
2414813621115129731050
3112824917511314100613
01518146113497213120510
13134715281412011069115S_2
20147111041315812693215
31381013154211671205149
01009146315511312711428
11370934610285141211151 S_3
21364981530111212510147
31101306987415143115212
07131430691012851112415
11381156150347212110149S_4
21069012117131513145284
33150610113894511127214
02124171011685315130149
11411212471315015103986S_5
24211110137815912563014
31181271142136150910453
01211015926801334147511
11015427129561131401138S_6
29141552812370410111316
34321295151011141760813
04112141508133129751061
11301174911014351221586S_7
21411131237141015680592
36111381410795015142312
01328461511110931450127
11151381037412561101492S_8
27114191214206101315358
32814741081315129035611

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

Значение функции f(R_{i-1},k_i) (32бит) получается перестановкой Р, применяемой к 32 битовому блоку B'_1B'_2...B'_8. Перестановка Р задана таблицей 4.

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

167202129122817
11523265183110
282414322739
19133062211425

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

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

Файл:Decode.PNG

Таблица 5.

57494133251791585042342618C_0
10259514335271911360524436
635547393123157625446383022D_0
1466153453729211352820124

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

Таблица 6.

i12345678910111213141516
Число сдвига1122222212222221

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

Таблица 7.

141711241532815621102319124
26816727201324152313747553040
51453348444939563453464250362932

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

Таблица 8.Обратная перестановка IP^{-1}

408481656246432397471555236331
386461454226230375451353216129
364441252206028353431151195927
34242105018582633141949175725

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

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

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

Cхема расшифрования указана как на Рис.5.</br> Ключ k_i, i=1,..15, функция f, перестановка IP и IP^{-1} такие же как и в процессе шифрования.

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

Файл:ECB1.JPG
Файл:CBC.PNG
Файл:CFB2.JPG
Файл:OFB.PNG

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

1.Режим электронной кодовой книги(ЕСВElectronic Code Book): обычное использование DES как блочный шифр (см. Рис.7).

2.Режим сцепления блоков (СВС- Cipher Block Chaining) (см. Рис.8).

Каждый блок C_i i>=1, перед очередным зашифрованием складывается по модулю 2 со следующим блоком открытого текста M_{i+1}. Вектор C_0 - начальный вектор, он меняется ежедневно и хранится в секрете.

3.Режим обратной связи с шифртексту(CFBCipher Feed Back) (см. Рис.9).

В режиме СFB выработывается блочная "гамма" Z_0, Z_1,... Z_i=DES_k(C_{i-1}) C_i = M_i \oplus Z_i. Начальный вектор C_0 сохраняется в секрете.

4.Режим обратной связи по выходу (OFBOutput Feed Back) (см. Рис.10).

В режиме OFB вырабатывается блочная "гамма" Z_0, Z_1,... Z_i=DES_k(Z_{i-1})
C_i = M_i \oplus Z_i , i>=1

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

Режим ECB просто реализуется, но возможно происходить проведение критоанализа. В режимах ECB и OFB искажение при передаче одного 64-битового блока шифртекста  C_i приводит к искажению после расшифрования только соответствующего открытого блока  M_i , поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.

В режимах CBC и CFB искажение при передаче одного блока шифрованного текста Сi приводит к искажению на приемнике не более двух блоков открытого текста M_i,  M_{i+1} . Изменение M_i приводится к изменению всех остальных блоков M_{i+1},  M_{i+2},... Это свойство используется для выработки кода аутентификации сообщения.

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

Нелинейность преобразований в DES только S- блоками, сказали что S-блоки имеют некоторую слабину, позволяющую осуществовать контроль за шифрованной перепиской. Для выбора S- блоков потребуется несколько условия. -Каждая строка каждой блока – перестановка множество{0,1,2,……,15}

-S-блоки не должны являются линейной или афинной функцией своих входов.

-Изменение одного бита входа S-блока должно приводить к изменению по крайней мере двух битов выхода.

-Для кждого S-блока и любого входа х значение S(x) и S(x \oplus 001100_2) должны различаться по крайней мере двумя битами.

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

В алгоритме DES существуют слыбые и полу-слабыми ключи. Слабыми ключами называется ключи k такие что DES_k(DES_k(x)) = x, x блок 64 бит. А полу-слабыми ключи- пары ключа (k_1, k_2) такие что DES_{k1}(DES_{k2}(x)) = x</br> Существует 4 известных DES-слабых ключей,указаные в таблице 9. Для каждого слабого ключа существует 2^{32} "постоянные точки", т.е. такие 64-битовые блоки х, что DES_k(x) = x

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

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

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

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

Таблица 10.Полу-слабые ключи

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

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

Методы атакиData Complexity KnownData Complexity ChosenStorage ComplexityProccessing Complexity
полный поиск1 -Negligible2^{55}
линейный криптоанализ2^{43} (85%) -For texts2^{43}
2^{38} (10%) -Fortextss^{50}
дифферц. криптоанализ -2^{47}For texts2^{47}
2^{55} -For texts2^{55}

Чтобы увеличивать криптостойкость DES появляются методы double DES (2DES), triple DES (3DES).Такие методы основны на DES но увеличивают длину ключи( 2DES – 112бит, 3DES- 168 бит), и поэтому увеличить критостойкость.

Применение Править

DES был нацианальном стандартом США в 1977 - 1980г.Сейчас DES еще испльзуется но чащее используют его более кпритостойчивый вид (3DES, 2DES). 3DES является простой эффективной заменой DES.

be-x-old:DES ca:DES cs:Data Encryption Standard da:Data Encryption Standard de:Data Encryption Standard el:Data Encryption Standard en:Data Encryption Standard eo:DES es:Data Encryption Standard eu:DES fi:DES fr:Data Encryption Standard he:Data Encryption Standard hr:Data Encryption Standard id:Data Encryption Standard it:Data Encryption Standard ja:DES (暗号) ka:DES ko:DES (암호) lt:DES lv:Data Encryption Standard nl:Data Encryption Standard nn:DES no:DES pl:Data Encryption Standard pt:Data Encryption Standard ro:Data Encryption Standard simple:Data Encryption Standard sk:Data Encryption Standard sl:DES sr:DES sv:Data Encryption Standard tg:DES tr:DES uk:Data Encryption Standard vi:DES (mã hóa) zh:DES

Литература Править

А.П.Алферов, А.Ю.Зубов, А.С.Кузьмин, А.В.Черемушкин - Основы криптографии</br> A.Menezes, Pvan Oorschot, S.Vanstone - Handbook of Applied Cruptography</br> Семенов Ю.А.Алгоритм DES</br> Query for DES</br>

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики