Properties of X, S-layers.pdf Блочные шифрсистемы, у которых раундовая функция является композицией трёхтипов преобразований: наложения ключа (X-слой), преобразования над отдельнымичастями блока текста (S-слой) и линейного преобразования (L-слой),- называютсяXSL-сетями. В работе [1] для блочных шифрсистем XSL рассмотрены комбинатор-ные свойства группы, порождённой X, L-слоями. В данной работе рассматриваютсясвойства группы, порождённой X, S-слоями.Пусть R - множество всех действительных чисел; N - множество всех натураль-ных чисел; N0 = N U {0}; S(X) -множество всех подстановок на множестве X;Xх = X\{0}; Vm - векторное пространство размерности m над GF(2); R+ = {a Е R :a ^ 0}; n,m,d Е N, n = md; ord(g) -порядок подстановки g Е S(X); s = ( s d - 1 , . . . , s0),si Е S(X); IGw = (Sb I Sr , W) -группа сплетения в её импримитивном действии, гдеW = {W1 , . . . , W r } - фиксированная система импримитивности с r блоками мощно-сти b; p(g) = (g)) -матрица разностей переходов подстановки g Е S(X) на группе(X, +). Для произвольного вектора а Е X зададим преобразование : X ^ X как: в ^ в + a, = {ha : X ^ X | а Е X} . C матрицей а = (a,) над R+ свяжемматрицу а = (aij), у которой1, a , > 0,a - = i j 0.Назовём матрицу p положительной, если все её элементы больше нуля. В этомслучае будем использовать запись p > 0. (Матрица p называется эргодической, еслиpq > 0 для некоторого числа q . N.)Утверждение 1.1) Пусть g - произвольная подстановка из S ( X ) , l = ord(g), t . N, t ^ 2. Группаi ,C(g) является t-транзитивной тогда и только тогда, когда Е (p( t - 1 ) (g)) > 0.,=12) Пусть (p( t - 1 ) ( g ) ) > 0 для некоторого числа b . N. Тогда для любых векто-ров 8, 8' . X с у щ е с т в у е т элемент h^1 g . . . h^, gheb+1 . C (g), в1 , . . . , в ь + 1 . X,удовлетворяющий равенству (8)h^1 g . . . gh^b+1 = 8'.Следствие 1. Если t . N, t ^ 2 и матрица p ( t - 1 ) ( g ) эргодическая, то группа C(g)t-транзитивна.Приведём пример того, что группа C(g) может быть 2-транзитивной, но матри-ца p(g) не являться эргодической. Пусть g - линейное преобразование с примитив-ным характеристическим многочленом. Тогда p(g) -подстановочная матрица поряд-2 m - 1 -ка 2m - 1. Очевидно, что матрица p(g) не является эргодической, но матрица Е p(gj)j=1положительная.Рассмотрим классы подстановок с одинаковыми матрицами p( t )(g_ Для подстанов-ки g . S(X) и t . N положим P( t )(g) = {в . S(X) : p( t )(g) = p( t )(s)_ . Ясно, что длялюбых подстановок g1,g2 . S ( X ) справедливо соотношениеP( t )(g1) П P( t )(g2) . { 0 , P( t ) ( g 1 ) ) .Подстановке g . S ( X ) и векторам 8, Л . X поставим в соответствие такое преобра-зование g(

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