Алгоритм шифрования DES

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

  • Режим шифрования электронной кодовой книги (ECB — Electronic Code Book),
  • Режим шифрования сцепления блоков (СВС — Cipher Block Chaining),
  • Режим шифрования обратной связи по шифротексту (CFB — Cipher Feed Back),
  • Режим шифрования обратной связи по выходу (OFB — Output Feed Back),

 



Для шифрования DES принимает 64-битовый открытый текст и порождает 64-битовый зашифрованный текст и наоборот, получив 64 бита зашифрованного текста, он выдает 64 бита расшифрованного. В обоих случаях для шифрования и дешифрования применяется один и тот же 56-битовый ключ.

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

Они подозревали, что S-боксы имеет скрытую лазейку, которая позволит Национальному агентству по безопасности США расшифровывать сообщения без ключа. Впоследствии проектировщики IBM сообщили, что внутренняя структура была доработана, чтобы предотвратить криптоанализ. Федеральный Регистр объявил DES стандартом шифрования и он быстро стал наиболее широко используемым блочным шифром.



Структура шифра DES

Процесс шифрования состоит из двух перестановок, которые называют начальной и финальной (конечной) перестановками, и 16 раундов Фейстеля. Каждый раунд использует различные сгенерированные 48-битовые ключи.

 

Начальная IP и конечная IP-1 перестановки

На вход каждой из них поступает 64 бита, которые затем переставляются в соответствии с заданными таблицами. Эти перестановки взаимно обратны. Другими словами, 58-й бит на входе начальной перестановке переходит в 1-ую позицию на выходе из нее. А финальная перестановка 1-ый входной бит переведет в 58-ую позицию на выходе.

 

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

вход: 0000000000000010000000000000000000000000000000000000000000000 001

выход: 0000000000000000000000001000000000000000000000000000000000000 010

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

DES создает 16 раундовых ключей i k по 48 битов из ключа k шифра на 56 битов. Однако, чтобы задать ключ шифра надо среди 56 битов ключа дополнительно вписать 8 битов в позиции 8,16,…,64 для проверки четности таким образом, чтобы каждый байт содержал нечетное число единиц. С помощью этой операции выявляют ошибки при обмене и хранении ключей. Ключевое расписание состоит из этапов: 1). Перестановка сжатия для удаления битов проверки – из 64- битового ключа удаляют биты 8,16,24, 32,…,64 и переставляет остальные биты согласно таблице (в ходе перестановки сохраняется нумерация битов расширенного ключа).

 

2) После перестановки 56 битов ключа делятся на два блока C0 и D0 по 28 бит каждый. Далее для генерации раундовых ключей из блоков C0 и D0 с помощью операции циклического сдвига влево на 1-2 бита строятся блоки Ci и Di , i 1,2,…,16 . В раундах 1,2,9 и 16 смещение – на 1 бит, в других раундах — на 2 бита. После определения блоков Ci и Di биты этих блоков объединяются в один ключ на 56 битов.

 

3). Перестановка сжатия (P-бокс, таблица) изменяет 56 битов на 48 битов, которые образуют раундовый ключ.

При расшифровывании – раундовые ключи те же, что и при зашифровывании, но теперь они используются в обратном порядке !

КРИПТОАНАЛИЗ DES

С самого начала использования алгоритма криптоаналитики всего мира прилагали множество усилий для взлома DES. Фактически DES
дал невиданный доселе толчок развитию криптоанализа. Вышли сотни трудов, посвященных различным методам криптоанализа именно в
приложении к алгоритму DES, а также деталям самого алгоритма и их влиянию на криптостойкость. Можно утверждать, что именно благодаря

DES появились целые направления криптоанализа, такие как:

  • – линейный криптоанализ – анализ зависимостей между открытым текстом и шифротекстом;
  • – дифференциальный криптоанализ – анализ зависимостей между соотношениями двух или более открытых текстов и
    соответствующих им шифротекстов;
  • – криптоанализ на связанных ключах – поиск и анализ зависимостей между шифротекстами, полученными на искомом ключе и ключах, связанных предполагаемым соотношением с искомым ключом;

Однако DES оказался неуязвим к данному виду атак, так как по ключовому расписанию циклический сдвиг битов ключа выполняется на
различное число позиций в разных раундах. DES стойко выдержал 20 лет массового всемирного криптоанализа
– десятилетия криптоанализа не привели к обнаружению серьезных уязвимостей в алгоритме.

Основными результатами усилий по взлому DES можно считать следующие:

  • 1. Японский специалист Мицуру Мацуи (Mitsuru Matsui), изобретатель линейного криптоанализа, в 1993 году показал, что
    вычислить ключ шифра можно методом линейного криптоанализа при наличии у атакующего 247 пар «открытый текст – шифротекст».
  • 2. Криптологи из Израиля, изобретатели дифференциального криптоанализа Эли Бихам (Eli Biham) и Ади Шамир (Adi Shamir) в 1991
    году представили атаку, в которой ключ шифрования вычислялся методом дифференциального криптоанализа при условии, что атакующий имеет 2 специально выбранных пар «открытый текст – шифротекст».

В дальнейшем эти атаки были несколько усилены (например, атака линейным криптоанализом при наличии 243 пар вместо 247), появлялись
также новые виды атак на DES (например, атака, позволяющая вычислить ключ высокоточным облучением аппаратного шифратора и последующим анализом ошибок шифрования).

Однако, все эти атаки требуют наличия огромного количества пар «открытый текст – шифротекст», получение которых на практике является настолько трудоемкой операцией, что наиболее простой атакой на DES все еще можно считать полный перебор ключей.

Заключение

В течение всего того времени, когда алгоритм DES являлся стандартом шифрования США (и наиболее часто используемым во всем мире алгоритмом шифрования), криптологи изобретали различные варианты данного алгоритма. Этот процесс продолжается и сейчас. И хотя многие из этих вариантов имеют чисто историческое значение, есть такие, которые способны продлить жизнь алгоритму DES – прежде всего, совсем новые варианты DESL и DESXL, которых, судя по всему, ожидает достаточно активное использование в их специфичной нише. Стоит предположить, что это не последние варианты алгоритма DES.

RuCoreNET - лучшее для вас!


Поделись статьей с друзьями


70 просмотров


0 0 vote
Рейтинг статьи
Подписаться
Уведомление о
guest
0 Комментарий
Inline Feedbacks
View all comments


Do NOT follow this link or you will be banned from the site!
0
Would love your thoughts, please comment.x
()
x

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: