On generalizations of markov's approach to research of block ciphers.pdf В работе [1] введён термин «стохастический метод криптоанализа» как обобщение большого класса методов, основанных на построении некоторых l-раундовых характеристик. Такими методами являются линейный [2], разностный [3] и их обобщения. В стохастическом методе раундовой функции i-го раунда ставится в соответствие матрица p(i) переходов блоков (i-1)-го раунда в блоки i-го раунда, i = 1,... , l. Матрица вероятностей переходов блоков разбиения открытого текста X(0) в блоки разбиения X(l) i шифртекста l-го раунда предполагается равной p[l] = П p(i). Для данного предположеi=1 ния требуется, чтобы последовательность, порождённая промежуточными текстами, являлась цепью Маркова. При этом для применения атак на основе стохастического метода существенным является предположение о независимости раундовых ключей, которое используется в линейном методе и различных обобщениях разностного метода. В данной работе рассматриваются свойства алгоритмов блочного шифрования Маркова при укрупнении состояний цепи Маркова, основанных на таких разбиениях U = (U1,...,Ud) множества Xх (называемых далее U(м)-разбиениями), что разбиение U порождает метрику на X, где Xх = X\{e}, e - единичный элемент абеле-вой группы (X, ®) с бинарной операцией ®. Близкими к таким разбиениям являются W-разбиения, где под W-разбиением понимается разбиение множества X на блоки одинаковой мощности. В частности, если Wo -произвольная подгруппа (X, ®), то рассматриваемым W-разбиением является множество смежных классов группы (X, ®) по подгруппе W0. Заметим, что при рассмотрении разбиения {W0\{e},... , Wr-1} естественным образом получается U(м)-разбиение. Кроме того, W-разбиения позволяют для XSL-алгоритмов блочного шифрования учитывать не только строение слоя наложения ключа, но и строение линейного слоя. Например, это возможно, если W0 - инвариантное подпространство линейного преобразования. Блоки U(м)-разбиения интерпретируются как множества разностей пар открытого текста (шифртекста). Заметим, что разбиение Xх с блоками единичной длины применяется в разностном методе, а усечённые разности естественным образом задают W-разбиение. Показано, что такие укрупнения состояний цепи Маркова, порождённые последовательностями промежуточных шифртекстов i-го раунда, i = 1, 2,..., алгоритмов блочного шифрования, являются цепью Маркова. Для них выполнен перенос ряда результатов работы [4]. В частности, приведены условия, при которых алгоритмы блочного шифрования на основе схем XSL, Фейстеля и Лея - Месси [5] являются марковскими относительно рассматриваемых разбиений.

Скачать электронную версию публикации