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

В 1974 г. Национальное бюро стандартов США (NBS) поставило перед промышленностью вопрос о создании криптосистемы, которая могла бы стать стандартом для использования правительством в несекретных приложениях. В ответ на это компанией IBM была создана система LUCIFER. После некоторого видоизменения и упрощения в 1977 г. эта система стала стандартом шифрования данных (Data Encryption Standard или, сокращенно, DES).

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

DES представляет собой блочный шифр с длиной блока 64 бита (см. рис. 4.6).

Рис. 4.6. Стандарт шифрования данных (DES)

Ключ состоит из восьми групп по 8 битов. Один бит в каждой из групп — это бит проверки на четность и выбирается так, чтобы количество ненулевых битов в блоке было нечетно. Таким образом, хотя формально длина ключа 64 бита, реально используется 56-битовый ключ.

Работа алгоритма DES состоит из 16 одинаковых раундов. Входной 64-битовый блок разбивается на две части: 32 левых бита составляют, а 32 правых бита составляют.

В каждом раунде новые и вычисляются так:

где через обозначен внутренний ключ, т.е. последовательность битов, однозначно определяемая ключом.

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

Значение функции покоординатно складывается с. Левой половиной просто становится предшествующая правая половина. (См. приведенный ниже рис. 4.7.)

Выход DES образуется из и.

Рис. 4.7. Стандартный раунд DES.

На рис. 4.7 можно увидеть, что процесс, обратный алгоритму DES, происходит по той же схеме, только снизу вверх. Действительно, из формул (4.2) следует, что для всех, выполняются равенства

Многие критично отнеслись к решению сделать DES стандартом. Для этого есть две объективные причины:

i) Эффективная длина ключа (56 битов) слишком мала для организаций с достаточно большими ресурсами. Это делает возможным, по крайней мере, в принципе, выполнение исчерпывающего перебора ключей.

ii) Критерии создания таблиц, использующихся в определении функции, неизвестны. Статистические тесты показывают, что эти таблицы нельзя считать совершенно случайными. Возможно, в их структуре скрыта какая-либо секретная лазейка.

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

Однако, в 1998 году DES впервые был взломан с помощью более или менее лобовой атаки.

□ Тройной DES

Когда стало ясно, что DES более не пригоден для защиты конфиденциальной информации, появилась его модификация, называемая тройной DES. Он состоит из трех последовательных выполнений алгоритма DES, с той лишь особенностью, что на втором шаге выполняется обратный алгоритм. Т.е. сначала DES, затем DES^←, и наконец, снова DES. (См. приведенный ниже рис. 4.8.)

Рис. 4.8. Тройной DES.

Отметим пару особенностей этой схемы.

Во-первых, третий ключ совпадает с первым. Тем самым реальная длина ключа составляет. Считается, что это обеспечит безопасность системы на несколько лет.

Во-вторых, на среднем шаге вместо DES применяется DES^←.

Две эти особенности позволяют сделать системы, в которых используется тройной DES, совместимыми с системами, в которых используется обычный DES. В самом деле, взяв одинаковые ключи 1 и 2, можно превратить описанную выше систему в обычный DES.

Дата добавления: 2013-12-12