Случайные подстановки в криптографии

Исследование дифференциальных свойств случайных подстановок

Блочный шифр является функцией отображения множества текстов и множества ключей в множество шифртекстов. Формально, можно описать блочный шифр как функцию

E: K × P ® C,

где K - комплект ключей, Р - множество открытых текстов и С - набор шифртекстов.

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

E:{0, 1}^K×{0, 1}ⁿ ® {0, 1}ⁿ,

где K - размер ключа и n является размером блока шифра (битовый размер входа в шифр). Общепринятые значения размера ключа K Î {64, 128, 192, 256} и n Î {64, 128}.

Поскольку необходимо иметь возможность восстановить текст из зашифрованного с помощью ключа, требуется, чтобы для всех ключей k Î K функция зашифрования E_k с использованием ключа k, была перестановкой (подстановкой), то есть отображение

"_k Î K, E_k: {0, 1}^N ® {0, 1}^N

должно быть биективным.

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

Интерес и внимание к исследованию и разработке процедур построения криптографически стойкихподстановочных преобразований (названных, начиная с работ Бихама и Шамира, S-блоками) возник в начале 90-х годов прошедшего столетия [131-136 и др.]. Он стал закономерным исходом изучения и исследования специалистами надежности американского стандарта симметричного шифрования DES, завоевавшим к тому времени мировой авторитет и признание (ставшим фактически всемирным стандартом). К этому же времени относится появление работы израильских ученых-криптографов Э.Бихама и А. Шамира [99], предложивших атаку дифференциального криптоанализа на шифр DES, а двумя годами позже работы М. Мацуи [137] посвященной линейному криптоанализу - второму новому типу криптонападения на DES. Эти работы стали заметным стимулом дальнейшего разворачивания исследований, посвященных анализу подстановочных конструкций [130, 138-144 и мн. другие], может быть часто не опирающихся прямо на S-блоки, но, тем не менее, имеющие к ним самое непосредственное отношение. Сегодня эти работы, конечно уже вышли далеко за рамки шифра DES. Появилось множество новых решений по построению алгоритмов шифрования. На смену самого шифра DES в США не так уж и давно принят новый стандарт шифрования AES (FIPS-197). Естественно, что параллельно с развитием техники конструирования шифров происходило и совершенствование методов криптоанализа, направленных на преодоление показателей стойкости, закладываемых в шифр его разработчиками. Остается отметить, что и сегодня вопросы построения более совершенных процедур шифрования и алгоритмов криптографической защиты информации в целом не потеряли своей актуальности и в центре внимания криптографов и математиков продолжают оставаться методы и алгоритмы конструирования новых шифров и в том числе методы (генерации) более совершенных S-блоковых конструкций.