Теория проектирования блочного шифра

В раздел 11.1 я описывал принципы Шеннона для смешения и рассеяния. Спустя пятьдесят лет после того, как эти принципы были впервые сформулированы, они остаются краеугольным камнем проектирования хорошего блочного шифра.

Смешение служит для маскировки взаимосвязей между открытым текстом, шифротекстом и ключом. Помните, как даже незначительная зависимость между этими тремя вещами может быть использована при дифференциальном и линейном криптоанализе? Хорошее смешение настолько усложняет статистику взаимосвязей, что не работают даже мощные криптографические средства.

Диффузия распространяет влияние отдельных битов открытого текста на как можно большее количество шифротекста. Это также маскирует статистические взаимосвязи и усложняет криптоанализ.

Для безопасности достаточно одного смешения. Алгоритм, состоящий из единственной зависящей от ключа таблицы соответствия 64 битов открытого текста 64 битам шифротекста был бы достаточно сильным. Проблема в том, что для такой таблицы потребовалось бы слишком много памяти: 1020 байтов. Смысл создания блочного шифра и состоит в создании чего-то похожего на такую таблицу, но предъявляющего к памяти более умеренные требования.

Прием состоит в том, чтобы в одном шифре в различных комбинациях периодически перемежать смешивание (с гораздо меньшими таблицами) и диффузию. Это называется результирующим шифром. Иногда блочный шифр, который включает последовательные перестановки и подстановки, называют сетью перестановок-подстановок (substitution-permutation network), или SP-сетью.

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

На примере DES также можно показать еще несколько принципов проектирования блочного шифра. Первым является идея итеративного блочного шифра. При этом предполагается, что простая функция этапа будет последовательно использована несколько раз. Двухэтапный DES не очень силен, чтобы все биты результата зависели от всех битов ключа и всех битов исходных данных, нужно 5 этапов [1078, 1080]. 16-этапный DES - это сильный алгоритм, 32-этапный DES еще сильнее.