?W, _ch-markovian transformations.pdf Пусть (X, 0) - произвольная регулярная абелева группа на конечном множестве X с бинарной операцией 0 и единичным элементом e; а-1 -обратный к а элемент относительно операции 0, а 0 в-1 = а0в для любых а, в Е X; Xх = X\{e}; S(X) - симметрическая группа на X; ag = ag = g(a) -образ элемента а Е X при действии на него подстановкой g Е S(X); K(i) -множество всех раундовых ключей i-го раунда, k(i) Е K(i); g(i) : (x, k(i)) М g(i)(x,k(i)) и g^ : а М gW^fc^) -раундовые функция i-го раунда, где x Е X, k(i) Е K(i); /kt = g^ ■ ... ■ g^) для kt = (k(1),...,k(t)) Е K(1) х ... х K(t); K(i)|-1 ■ |X |-1. В [1] показано, что если |(0) -дискретная случайная величина на множестве Xх, то в /-раундовом 0-марковском алгоритме блочного шифрования с независимыми и равномерно распределёнными раундовыми ключами раундовые разности |(t) = = (0) 0 а fkt0а^, являясь случайными величинами, образуют однородную цепь Маркова. Для W-разбиения W = {W0,..., Wr-1} множества X рассмотрим последовательность таких дискретных случайных величин iW,. .. ,lW на множестве {0,... , r - 1}, что iW = j тогда и только тогда, когда |(t) Е Wj, j Е {0,... , r - 1}, t = 1,... , /. Для W = {W0,..., Wr-1} и i = 1,... , / положим p*,w (g(i)) = E р*,* (g(i)),0 Е xх. tf'eWc Приведём условия, при которых для 0-марковского алгоритма блочного шифрования последовательность случайных величин ^Wr .. ,lW является цепью Маркова. .О) 'k(i) (i) £ agk(i) (i) (а, k(i)) Е X х K(i) : (0 0 а)' (g Р*, Утверждение 1. Пусть для итерационного /-раундового ф-марковского алгоритма блочного шифрования с раундовой функцией i-го раунда g(i) разбиение W = = {W0,... , Wr-1}, r ^ 2, множества X (Xх) таково, что: 1) P {£(0) = в(0)} = P {£(0) = в/(0)} для всех в(0),в/(0) G Wc, c G {0,... ,r - 1}; 2) для каждых (c,j) G {0,...,r - 1}2, (e,i) G Wj х {1,...,/} и некотором jC, 0 ^ j ^ 1, выполняется равенство (#(i)) = j. Тогда последовательность случайных величин CW ,... ,CW над {0,... , r-1} образует цепь Маркова. Если g(1) = g(2) = ... = g(1), то эта цепь Маркова является однородной. Определение 1. Назовём /-раундовый ф-марковский алгоритм блочного шифрования ф^сИ-марковским для разбиения W = {W0,... , Wr-1}, r ^ 2, если последовательность случайных величин CW,... ,CW является цепью Маркова, т.е. раундовая функция g(i) удовлетворяет п. 2 утверждения 1. Определение 2. Назовём преобразование b G S(X) Qw^h-марковским для разбиения W = {W0,..., Wr-1}, r ^ 2, если для каждых (c, j) G {0,..., r - 1}2, в G Wj и некоторых aj,c, 0 ^ aj,c ^ 1, выполняется равенство (b) = aj,c. Отметим, что неявно допущение о Qw^h-марковости алгоритма блочного шифрования для некоторого класса блоков разбиений W и наборов номеров таких блоков используется в методе усечённых разностей - в одном из наиболее распространённых обобщений разностного метода [2-6]. В этом случае неявно полагают, что для! итеративных ф-марковских алгоритмов шифрования вероятность P { (А?(о),... , Am) } набоi-1 ра усечённых разностей (А?(о),... , А?(о) находится как П pj(i)j(i+i) (#(г+1)), где A?(i) - i=0 , блок некоторого разбиения множества Xх; Pj(i),j(i+1) (g(i+1)) -вероятность перехода блока Aj(i) в блок Aj(i+i) под действием раундовой функции g(i+1) в предположении, что раундовый ключ выбирается случайно и равновероятно из множества K(i), i = 0,...,/. В ряде работ (см., например, [3, 5]) при применении метода усечённых разностей происходит проверка корректности равенства i-1 P {(Aj(o),..., А®)} = П Pj(i),j(i+i) (А+1)) (1) i=0 посредством вычислительных экспериментов. Так, в [5] показано, что экспериментальная оценка вероятности P { (А?(о),... , А?(о)} может быть больше найденной по формуле (1). В XSL-алгоритмах блочного шифрования и алгоритмах шифрования Фейсте-ля с XSL-функцией усложнения марковость последовательности случайных величин Wto,... , Wti_ 1 определяется свойствами s-боксов. Поэтому в качестве примеров в данной работе приведены преобразования, основанные на операциях экспоненцирования и логарифмирования в кольце вычетов Zn (с операцией сложения +) и поле GF(n + 1), а также указаны разбиения W, при которых данные преобразования являются +w,ch-марковскими. К этим преобразованиям относятся подстановки s-боксов алгоритма блочного шифрования SAFER [7], экспоненциальные подстановки [8] и логарифмические подстановки. Логарифмические подстановки были предложены первым автором данной работы и М. Е. Масленниковым. Они применяются в семействе функций хеширования MCSSHA, причём первая функция хеширования этого семейства MCSSHA-1 являлась кандидатом для участия в конкурсе SHA-3. Перемешивающие свойства логарифмических подстановок рассматривались, например, в [9]. Пусть Z - множество всех целых чисел, Zn = {0,...,n - 1}. Для a Е Z через a(d) обозначим такой наименьший элемент a(d) Е {0,..., d - 1}, что a(d) = a (mod d). Пусть также n Е N, n +1 -простое число, в - примитивный элемент поля Галуа GF(n + 1) и подстановка ^0,5,c Е S(Zn) задана условием ^*,5,c : x М (вж+с mod (n + 1) + £) (n), c Е Zn. Утверждение 2. Пусть m ^ 1, n = 2т и матрица p(b) вероятностей переходов разностей подстановки b Е S (Zn) такова, что справедливо одно из условий: 1) Pi,j (u) = P2m-i,2m-j (b) для каждых i, j Е Zx 2) Pi,j (b) = P2m-i,j (b) для каждых i, j Е Z^. Тогда подстановка b является +w,ch-марковской для разбиения W = {W0, W1,... , W2m-i}, где _ f{i, 2m - i} , если i Е {1,..., 2m-1 - 1}, i = j {i} , если i Е {0, 2m-1}. Из утверждения 2 следует +w,ch-марковость подстановки ^0,5,0 для W-разбиения, так как для произвольных £, Л Е ZX справедливы равенства Ре,Л (^0,5,0) = Pe,2m-A (^0,5,0) , Ре,Л (^0,5,0) = Р2™-е,Л (^0,5,0) . Из утверждения 2 также следует +w,ch-марковость класса экспоненциальных подстановок : Z2m м GF (2т), заданных условием {0, если а = 0, ва, если а = 0, где в - примитивный элемент поля GF(2m).

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