Контроль Разума
Advertisement
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Файл:Code.PNG

Рис.4 Подровная cхема шифрования алгоритма DES

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

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

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

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

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

левая и правая половины 64-битового блока

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

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

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

Таблица 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 входного блока. Дальше 64-битовой блок IP(T) участвует в 16-циклах преобразования Фейстеля.

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

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

Пусть результат (i-1) итерации, тогда результат i-ой интерации определяется:



Левая половина равна правой половине предыдущего вектора . А правая половина - это битовое сложение и по модулю 2.

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

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

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

Функция Е расширяется 32 битовой вектор до 48 битовой вектор путем дублирования некоторых битов из при этом порядок битов вектора указан в таблице 2.

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

Первые три бита вектора являются битами 32, 1, 2 вектора . По таблице 2 видно что биты 1,4,5,8,9,12,13,16,17,20,21,24,25,28,29,32 дублируются. Последние 3 биты вектора - это биты 31,32,1 вектора . Полученный после перестановки блок складывается по модулю 2 с ключами и затем представляются в виде восьми последовательных блоков .

. Каждый является 6-битовым блоком. Далее каждый из блоков трансформируется в 4 битовой блок с помощью преобразований . Преобразования определяется таблицей 3.

Файл:FuncF.JPEG

Рис.5 Cхема работы функции f

Таблица 3.Преобразования ,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 4 8 13 6 2 11 15 12 9 7 3 10 5 0
3 1 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 11 13 1 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 8 14 7 4 10 8 13 15 12 9 0 3 5 6 11

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

Значение функции (32бит) получается перестановкой Р, применяемой к 32 битовому блоку . Перестановка Р задана таблицей 4.

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


Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f - это бита 16,7,20,21 вектора

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

Файл:Decode.PNG

Рис.6 Cхема расшифрования алгоритма DES

Таблица 5.

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 исходного ключа k.А первые три бита есть биты 63, 55, 47 ключа k. i=1,2,3...получаются из одним или двумя левыми циклическими сдвигами согласно таблице 6.

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

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

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

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

Таблица 8.Обратная перестановка

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 помощью прямого преобразования сетью Фейстеля, здесь используется обратное преобразование сетью Фейстеля.


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

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

Файл:ECB1.JPG

Рис.7 Режим электронной кодовой книги- ECB

Файл:CBC.PNG

Рис.8 Режим сцепления блоков- СВС

Файл:CFB2.JPG

Рис.9 Режим обратной связи с шифртексту- CFB

Файл:OFB.PNG

Рис.10 Режим обратной связи по выходу- OFB

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

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

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

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

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

В режиме СFB выработывается блочная "гамма" . Начальный вектор сохраняется в секрете.

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

В режиме OFB вырабатывается блочная "гамма" , i>=1

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

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

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

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

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

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

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

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

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

В алгоритме DES существуют слыбые и полу-слабыми ключи. Слабыми ключами называется ключи k такие что , x блок 64 бит. А полу-слабыми ключи- пары ключа такие что
Существует 4 известных DES-слабых ключей,указаные в таблице 9. Для каждого слабого ключа существует "постоянные точки", т.е. такие 64-битовые блоки х, что

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

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

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

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

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

Пары полу-слабых ключей
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

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

Методы атаки Data Complexity Known Data Complexity Chosen Storage Complexity Proccessing Complexity
полный поиск 1 - Negligible
линейный криптоанализ - For texts
- Fortexts
дифферц. криптоанализ - For texts
- For texts

Чтобы увеличивать криптостойкость 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

Литература[]

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

Advertisement