Проектирование и разработка информационных систем

1.1.2 Стандарт DES
Блочный алгоритмом с закрытым ключом DES использует сеть 
Фейстеля. 
Алгоритм DES широко использовался при хранении и передаче данных 
между различными вычислительными системами; в почтовых системах, в 
электронных системах чертежей и при электронном обмене коммерческой 
информацией. 
DES обладает двумя очень важными качествами блочных шифров: 
лавинностью и полнотой: 

---

20 
- Лавинный эффект или рассеивание означает, что небольшие 
изменения в исходном тексте или ключе вызывают значительные изменения в 
зашифрованном тексте.
- Эффект полноты заключается в том, что каждый бит зашифрованного 
текста должен зависеть от многих битов исходного текста.
При шифровании алгоритмом DES сообщение делится на блоки по 64 
бита. Для каждого раунда происходит генерация ключей из 64-битного 
исходного ключа, в котором значимыми являются только 56 битов (7 байтов 
или 7 символов в ASCII). В процессе работы алгоритма используются таблицы, 
с помощью которых осуществляется шифрование информации. Блок схема 
алгоритма DES представлена на рисунке 1.1. 
Для каждого раунда алгоритма происходит генерация ключей из 
начального ключа. Во время преобразования происходит циклический сдвиг 
влево на один или два бита в зависимости от раунда, затем применяется 
таблица перестановок, после чего для окончательного раундового ключа 
отбираются 48 бит из 56 бит, то есть происходит сжатие ключа. 
К исходному блоку информации применяется начальная перестановка, 
для осуществления которой используется таблица начальной перестановки (в 
реализации des_IP_table). После этого блок информации разбивается на две 
части по 32 бита: левая и правая части, к которым применяется сеть Фейстеля в 
течении 16 раундов, при которых данные объединяются с ключом. На 
заключительном этапе после 16 раунда правая и левая части объединяются, 
выполняется обратная перестановка, для осуществления которой используется 
таблица обратной перестановки (des_invIP_table). 

---

21 
Рисунок 1.1 - Блок-схема алгоритма DES. Шифрование и расшифрование 
На рисунках 1.2 и 1.3 представлена схема преобразований, 
происходящих в одном раунде алгоритма. 
Рисунок 1.2 - Раунд алгоритма DES 

---

22 
Рисунок 1.3 - Представление функции F алгоритма DES 
Функция F описывающая действия в раунде представляет собой 
последовательные преобразования, при которых данные объединяются с 
ключом (формула 1-1).
1. Применение функции расширения E. Одна из двух частей 
информации, например, правая, размером 32 бит расширяется до 48 бит. 
Дублирование бит исходной информации осуществляется в соответствии с 
таблицей расширения.
2. Операция XOR данных, полученных на первом шаге, и ключа. 
Полученный результат представляется в виде 8 блоков по 6 бит. 
3. Применение таблицы преобразования к полученный блокам. Каждый 
из 8 блоков по 6 бит с помощью таблицы преобразования трансформируется в 
блок по 4 бита. 
4. Применение таблицы перестановки. К полученным 32 битам (8 
блоков по 4 бита) применяется таблица перестановки и в результате будет 
получен преобразованный блок 
При переходе к следующему раунду правая и левая 32-битные части 
меняются местами. Шаги с 1 по 4 повторяются. 

---

23 
После окончания всех раундов преобразования, полученные 64 бита 
подвергаются инверсии, для осуществления которой используется таблица 
обратной перестановки (des_invIP_table) и, таким образом, будет получен 
зашифрованный текст.
Раундовые ключи формируются из начально ключа. Добавляются биты 
в позиции 8, 16, 24, 32, 40, 48, 56, 64 ключа k таким образом, чтобы каждый 
байт содержал нечетное число единиц. Далее к ключу применяется таблица 
перестановки, для каждого раунда применяется циклический сдвиг влево, 
после чего из значимых 56 бит ключа выбирается 48 бит в соответствии с 
таблицей. 
Расшифрование происходит в обратном порядке с использованием того 
же ключа. 
С самого начала использования алгоритма криптоаналитики всего мира 
прилагали множество усилий для взлома DES. Фактически DES дал 
разностороннее развитие криптоанализа. Многие труды, посвящены 
различным методам криптоанализа именно в приложении к алгоритму DES, а 
также деталям самого алгоритма и их влиянию на криптостойкость. Можно 
утверждать, что в результате проведенных исследований появились целые 
направления криптоанализа, такие как: 
-линейный криптоанализ 
-дифференциальный криптоанализ 
–анализ зависимостей между открытым текстом и шифротекстом 
–анализ зависимостей между соотношениями двух или более открытых 
текстов и соответствующих им шифротекстов 
-криптоанализ на связанных ключах
–поиск и анализ зависимостей между шифротекстами, полученными на 
искомом ключе и ключах, связанных предполагаемым соотношением с 
искомым ключом; однако DES оказался неуязвим к данному виду атак, так как 
по ключевому расписанию циклический сдвиг битов ключа выполняется на 
различное число позиций в разных раундах 

---

24 
-наличие слабых ключей. 
Усилия по взлому DES предпринимались с 90-х годов прошлого века: 
Японский специалист Мицуру Мацуи (Mitsuru Matsui), изобретатель 
линейного криптоанализа, в 1993 году показал, что вычислить ключ шифра 
можно методом линейного криптоанализа при наличии у атакующего 247 пар 
«открытый текст – шифротекст» [2]. 
Криптологи 
из 
Израиля, 
изобретатели 
дифференциального 
криптоанализа Эли Бихам (Eli Biham) и Ади Шамир (Adi Shamir) в 1991 году 
представили атаку, в которой ключ шифрования вычислялся методом 
дифференциального криптоанализа при условии, что атакующий имеет 247 
специально выбранных пар «открытый текст – шифротекст» [2]. 
В дальнейшем эти атаки были несколько усилены (например, атака 
линейным криптоанализом при наличии 243 пар вместо 247).
Как видно, все атаки требуют наличия огромного количества пар 
«открытый текст – шифротекст» (таблица 1.3), получение которых на практике 
является настолько трудоемкой операцией, что наиболее простой атакой на 
DES все еще можно считать полный перебор.
Таблица 1.3
Данные по способам криптоатак на алгоритм DES 
Способ вскрытия
Результат 
Предпосылка 
Полный перебор
2 ^ 56 
Требуется 2 ^ 55 известных пар текст-шифротекст 
Линейный 
криптоанализ
2 ^ 50 
Требуется 2 ^ 43 известных пар текст-шифротекст 
Дифференциальный 
криптоанализа
2 ^ 55 
Требуется 2 ^ 55 известных пар текст-шифротекст 
В настоящее время используется Triple DES – тройное шифрование, 
которое является более устойчивым к взлому. Для реализации данного подхода 
потребуется 
два 
ключа: 
сообщение 
шифруется 
первым 
ключом, 
расшифровывается вторым ключом и полученный результат шифруется 
первым ключом. Также возможна реализация с использованием трех 

---

25 
различных ключей. Все дальнейшие модификации алгоритма направлены на 
то, чтобы увеличить криптостойкость алгоритма. При этом алгоритм DES 
можно использовать в качестве тестового алгоритма при разработках методов 
криптоанализа.