On combinatorial properties of the group generated by XL-layers.pdf Алгоритмы блочного шифрования реализуются итеративным применением болеепростых преобразований, которые должны обеспечивать свойства перемешивания,рассеивания и усложнения. Для получения данных свойств обычно используются слоипреобразований трёх типов: наложение ключа (X-слой), преобразования над отдель-ными частями блока текста (слой s-боксов) и линейное преобразование (линейныйслой, или L-слой). Блочные шифрсистемы с таким построением раундовых преобра-зований и побитным подмешиванием раундового ключа в каждом раунде называютXSL-сетями. Ряд линейных преобразований, используемых в линейном слое в алго-ритмах шифрования и обеспечивающих хорошее рассеивание, являются приводимы-ми. Естественно, приводимыми являются и характеристические многочлены подста-новочных матриц, используемых в SP-сетях. Это приводит к импримитивности под-группы C(g) аффинной группы AGLn(2), порождённой слоем наложения раундовогоключа (т.е. всеми сдвигами) и приводимой невырожденной матрицей g Е GLn(2).В данной работе рассматриваются свойства графов орбиталов группы C(g).Пусть N - множество всех натуральных чисел; Vn - векторное пространство раз-мерности n над GF(2); Xх = X \ { 0 } ; g - матрица линейного преобразования g в стан-дартном базисе е 0 , . . . , e n - 1 , где ej = (0,..., 0,1, 0,..., 0) Е Vn, i Е { 0 , . . . , n - 1} ; GLn -jполная линейная группа; (x) - характеристический многочлен линейного преобра-зования g Е GLn(2); mY,g (x) -минимальный многочлен вектора 7 Е VX относительнопреобразования g.Напомним, что орбиталами группы G, действующей на множестве X, называютсяорбиты группы G при её действии на множестве X2 . Действие группы G на множе-стве X2 задано как (а, в ) f = (af , в^) для всех (а, в) Е X2 и f Е G.Лемма 1. Для произвольного преобразования g Е GLn и векторов а, в, а', в ' Е ^ ,а = в, а' = в', тогда и только тогда (а', в') Е (а, в ) C ( g ) , когда а' 0 в' Е (а 0 в) .Таким образом, различными нетривиальными графами орбиталов группы C(g) яв-ляются Г(o,71)(g),... , Г(0,7d_ 1)(g), где 7^>,... , 71 -попарно различные орбиты груп-пы (g) на VX. Среди графов орбиталов группы C(g) могут встречаться изоморфные.Существует тесная связь между строением характеристического многочлена (x)преобразования g, примитивностью (2-транзитивностью) и связностью графов орби-талов группы C(g). Так, группа C(g) примитивна тогда и только тогда, когда много-1 Работа выполнена при поддержке гранта Президента РФ НШ №6260.2012.10eчлен (x) неприводим. Кроме того, группа C(g) 2-транзитивна тогда и только тогда,когда многочлен xg (x) примитивен.Утверждение 1. Для произвольных вектора 7 . V.x, преобразования g . GLnс характеристическим многочленом xg (x) граф Г(0>7) (g) связен для всех векторов7.V.x тогда и только тогда, когда характеристический многочлен xg (x) неприводим.Утверждение 2. Для вектора 7 . V.x граф Г(0,Y)(g) связен тогда и только тогда,когда m7 ; g (x) = xg (x). Если группа C(g) примитивна, то все её графы орбиталовизоморфны.В алгебраической теории графов наибольший интерес представляют следующиеклассы графов: вершинно-транзитивные, рёберно-транзитивные, дистанционно-регу-лярные, дистанционно-транзитивные [1].Утверждение 3. Пусть n ^ 2, i . { 1 , . . . , d - 1} , Г (0,Yi)(g) -нетривиальныйсвязный граф диаметра b ^ 2. Тогда: а) Г(0,Yi)(g) -рёберно-транзитивный граф; б) ес-ли Y,-^ является базисом V., то граф Г(0>7.)(g) является дистанционно-транзитивными А^Г(0,7 i)(g) « S2 Т S..Графом Хемминга на V. будем называть граф с множеством вершин V. и мно-жеством рёбер {(а, в) . V. : х . ( а , в) = 1} . Очевидно, что если граф изоморфен гра-фу Хемминга, то его метрика изоморфна метрике Хемминга. Отметим, если множе-ство Y,-^ является базисом V., то граф Г(0,Yi)(g) изоморфен графу Хемминга и являетсядистанционно-регулярным.Теорема 1. Пусть n ^ 2, преобразование g . GLn и вектор 7 . V. такие, чтоm7 ; f l(x) = xr ( q - 1 ) 0 x r ( q - 2 ) 0 . . . 0 xr 0 1 = ( x ; _ 1 ,где rq = m = |Y^| . Граф Г(0,Y)(g) дистанционно-регулярный тогда и только тогда,когда выполняется одно из условий: а) r = 1 ; б) r ^ 2 и q = 3.

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