Стандарт шифрования данных DES

В январе 1977 году правительство Соединенных Штатов приняло продукцион­ный шифр, разработанный фирмой IBM, в качестве официального стандарта для несекретных сведений. Этот шифр, получивший название DES (Data Encryption Standard — стандарт шифрования данных), получил широкое распространение в промышленности для защиты информации. В своем исходном виде он уже боль­ше не является надежным, но в модифицированном виде все еще полезен. Сейчас мы объясним принципы его работы.

Схема DES-шифра показана на рис. 8.6, а. Открытый текст шифруется блоками по 64 бита, в результате чего на выходе получаются 64-битные блоки зашифро­ванного текста. Алгоритм, использующий 56-разрядный ключ, состоит из 19 от­дельных этапов. На первом этапе выполняется независимая перестановка 64 раз­рядов открытого текста. Последний представляет собой обратную перестановку. Предпоследний этап меняет местами левые и правые 32 разряда. Остальные 16 эта­пов функционально идентичны, но управляются разными функциями входного ключа. Алгоритм был разработан так, чтобы дешифрация выполнялась тем же ключом, что и шифрование. Это обеспечивает соответствие алгоритма принципу симметричных ключей. Этапы при расшифровке просто выполняются в обрат­ном порядке.

Операция, выполняемая на одном из промежуточных этапов, показана на рис. 8.6, 6. На каждом этапе из двух порций по 32 разряда на входе формируются две порции по 32 разряда на выходе. Правая половина входа просто копируется в левые разряды выхода. Правые 32 выходных разряда представляют собой сум­му по модулю 2 левой части входа и функции правой части входа и ключа данно­го этапа Kv Вся сложность шифра заключается в этой функции.

Функция состоит из четырех последовательно выполняемых шагов. Сначала из 32 разрядов правой части Rhl с помощью фиксированной перестановки и дуб­лирования формируется 48-разрядное число Е. На втором шаге число Е и ключ Kt складываются по модулю 2. Затем выход разделяется на восемь групп по шесть разрядов, каждая из которых преобразуется независимым S-блоком в 4-раз­рядные группы. Наконец, эти 8 • 4 разряда пропускаются через Р-блок.

На каждом из 16 этапов используются различные функции исходного ключа. Перед началом работы алгоритма к ключу применяется 56-разрядная переста­новка. Перед каждым этапом ключ разделяется на две группы по 28 разрядов, каж­
дая из которых вращается влево на число разрядов, зависящее от номера этапа. Ключ К{ получается из результата этой операции при помощи еще одной пере­становки 56 разрядов. На каждом этапе из 56 разрядов ключа выбираются 48 раз­рядов, которые также переставляются местами.

 

L,-

64-разрядный открытый текст j j | У Ц У У

1-1

illlllll UUUU

Стандарт шифрования данных DES" title="Стандарт шифрования данных DES" border=0 width=194 height=197 src="http://s55.radikal.ru/i147/1007/25/e1da771fc25d.png">

ы *

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

У V У У У У У

Итерация 1

У У У У У У У У

Итерация 2

Итерация 16

У У У X У У

Перестановка 32 битов

у у у у у у уу

Инверсная перестановка

 

ttfттттУ

32 бита L,

32 бита Я/

64-разрядный зашифрованный текст а

 

Рис. 8.6. Стандарт шифрования данных DES: общий вид (а); детализация одного из этапов (б)

Иногда для повышения надежности DES используется метод, называемый побелкой. Он заключается в том, что перед передачей шифра каждый блок от­крытого текста складывается по модулю 2 с произвольным 64-битным ключом, затем отправляется в устройство DES, после чего получившийся шифр склады­вается по модулю 2 со вторым 64-битным ключом. На приемном конце побелка легко устраняется путем выполнения обратных операций (это возможно, если у получателя есть два побелочных ключа). Поскольку применение этого метода увеличивает длину ключа, полный перебор в пространстве значений ключа ста­новится еще более длительным. Обратите внимание: для побелки каждого блока применяется один и тот же ключ (то есть для каждого сообщения имеется толь­ко один побелочный ключ).

Стандарт шифрования данных DES был полон противоречий с самого мо­мента его создания. Он основывался на шифре Люцифер (Lucifer), разработан­ном и запатентованном корпорацией IBM, с той разницей, что IBM использова­ла 128-разрядный, а не 56-разрядный ключ. Когда федеральное правительство

Соединенных Штатов пожелало стандартизировать какой-то шифр для несек­ретного применения, оно «пригласило» IBM на «обсуждение» этого вопроса с Агентством национальной безопасности, NSA (National Security Agency), являю­щимся самым крупным в мире работодателем в области математики и крипто­анализа. Агентство национальной безопасности США настолько секретно, что существует даже такая популярная шутка:

Вопрос: Что означает аббревиатура NSA?

Ответ: No Such Agency — такого агентства нет.

После этих обсуждений корпорация IBM уменьшила длину ключа со 128 до 56 бит и решила держать в секрете процедуру разработки стандарта DES. Мно­гие полагали, что длина ключа была уменьшена, чтобы гарантировать, что NSA сможет взломать DES, но организациям с более низким финансированием это будет не по силам. Вероятно, цель засекречивания проекта состояла в сокрытии потайного хода, позволяющего Агентству национальной безопасности еще легче взламывать шифр DES. Когда сотрудник этого управления предложил Институ­ту инженеров по электротехнике и электронике (IEEE) отменить планирую­щуюся конференцию по криптографии, ощущения комфорта это не прибавило. Агентство национальной безопасности всегда препятствовало всему.

В 1977 году ученые Стэнфордского университета, занимающиеся исследова­ниями в области криптографии, Диффи (Diffie) и Хеллман (Hellman), разрабо­тали машину для взлома кода DES и оценили стоимость ее создания в 20 млн долларов. По небольшому участку открытого текста и соответствующего ему за­шифрованному тексту эта машина путем полного перебора 256 вариантов за один день могла найти 56-разрядный ключ. На сегодняшний день такая машина могла бы стоить около 1 млн долларов.