On nonabelian key addition groups and markovian block ciphers.pdf Пусть (X, *) -произвольная группа на множестве X с бинарной операцией * и единичным элементом e; ab = ab = b(a) -образ элемента а е X при действии на него подстановкой b е S(X). Рассмотрим /-раундовый алгоритм блочного шифрования Q(*,b), у которого раундовая функция g : X2 ^ X, определяемая подстановкой b е S (X), задана условием g : (x, k) ^ (x * k)b для всех (x, k) е X2. Раундовой функции g соответствуют частичные функции gk : X ^ X, где g(x, k) = = gk(x) для каждых (x, k) е X2. Заметим, что к данному классу относятся XSL-алгоритмы блочного шифрования, у которых b = sh, где s - преобразование слоя перемешивания (s-боксы); h - преобразование линейного слоя. Неабелевость группы наложения ключа позволяет в некоторых случаях повышать стойкость алгоритмов блочного шифрования относительно линейного и разностного методов. Пусть K - множество всех раундовых ключей итерационного алгоритма блочного шифрования (в данной работе K = X). Для в,е е X положим 1 Зафиксируем произвольное нетривиальное разбиение W = {W0,... , Wr-1} множества X, e е W0. Положим Pe,wc(b)= E Po,o>(b), в е X, с е {0,... ,r - 1}. e'ewc В [1] введено понятие *-марковского алгоритма блочного шифрования, а в [2] - *^-марковского алгоритма блочного шифрования и *w-марковского преобразования. Определение 1. Преобразование b е S(X) называется *W-марковским для разбиения W = {W0,..., Wr-1}, |X| ^ r ^ 2, если pe,wc (b) = aj;C для каждых (j, с) е е {0,..., r - 1}2, в е Wj и некоторых aj,c, 0 ^ aj,c ^ 1. Условие *w-марковости алгоритма Ci(*,b) равносильно *w-марковости подстановки b. Рассмотрим преобразование ak е S (X), заданное условием ak : x ^ x * k для каждого k е X, и группу X * = (ak |k е X). Пусть р : X ^ S (X) - правое регулярное представление группы (X, *). Очевидно, что p(X) = X* и p(k) = ak для каждого k е X; gk = akb для каждого k е X. Будем говорить, что раундовая функция g сохраняет разбиение W справа, если Wgk G W для всех (W, k) G W х X. Получены ограничения на группы (X, *), G = (b,X*), а также на блоки W0,... , Wr-1, вытекающие из условия сохранения раундовой функцией нетривиального разбиения W. Доказано, что W - система импримитивности группы G. Кроме того, показано, что (W0, *) -подгруппа группы (X, *), причём Wj - j-й правый смежный класс группы (X, *) по (W0, *) для j = 0,... , r - 1. Из импримитивности группы G следуют включения b G IGw, (gk|k G X) ^ IGw, где IGw - максимальная подгруппа группы S(X), сохраняющая разбиение W. Если группа G = (b, X* ) импримитивна с системой импримитивности W, то существует естественный гомоморфизм : G ^ S({0,... , r - 1}), 1 = (e). Доказано, что если (Wo, *) нормальна в (X, *) ((Wo, *) < (X, *) ), W - множество всех смежных классов группы (X, *) по (W0, *), то условие *w-марковости алгоритма Q(*,b) эквивалентно существованию у него гомоморфизма, задаваемого отображением

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

Lai X., Massey J. L., and Murphy S. Markov ciphers and differential cryptanalysis // EUROCRYPT 1991. LNCS. 1991. V. 547. P. 17-38.

Погорелов Б. А., Пудовкина М. А. Разбиения на биграммах и марковость алгоритмов блочного шифрования // Математические вопросы криптографии. 2017. Т. 8. №1. С. 107142.

Холл М. Теория групп. М.: ИЛ, 1962. 468с.