Роль и место подстановочных преобразований в конструкциях современных шифров.

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

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

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

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

С другой стороны, для блочного шифра пространство открытых текстов P совпадает с пространством зашифрованных текстов C, т.е. , и преобразование зашифрования на случайно выбранном ключе, часто моделируется как случайная подстановка^[1] (перестановка), которая является подстановкой, равновероятно и случайно выбранной из множества всех перестановок пространства открытых текстов P. Главным проектным критерием для (защищенного) блочного шифра является свойство [163]: блочный шифр для каждого ключа должен быть неотличимым от случайной перестановки.

На практике для произвольного n-битового блочного шифра существует возможных перестановок открытого текста, что означает, что количество битов ключа, необходимое для получения всех возможных перестановок, составляет . Обычно размер ключа большинства блочных шифров не превышает небольшого числа, кратного размеру блока. Поэтому такие блочные шифры могут обеспечить лишь небольшую долю от полного количества возможных перестановок: . Например, для DES размер ключа равен k = 56 битов, а размер блока n = 64 битов и, следовательно, из перестановок 64-битовых блоков может быть выбрано только 2⁵⁶ преобразований.

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

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