О перемешивающих графах нелинейных подстановок двоичных регистров сдвига | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/1

О перемешивающих графах нелинейных подстановок двоичных регистров сдвига

Исследован класс R(n, т) подстановок n-мерного векторного пространства, реализуемых двоичными регистрами левого сдвига длины n c одной обратной связью f (xi,...,xn) = x1 ф ф(х2,... ,xn), зависящей существенно от m переменных, 3 ^ m ^ n. Получена двусторонняя оценка экспонента перемешивающих орграфов Г (д) с множеством вершин V = {1, 2,...,п} нелинейных подстановок д £ R(n, т): где D(g) = {ii,... ,im} - множество номеров существенных переменных функции обратной связи (ячеек съёма на регистре сдвига), 1 = i1 < ... < im ^ n, т ^ n; A(D) - наибольшее расстояние между соседними ячейками съёма на регистре сдвига: A(D) = max{i2 - i1,..., im - im-1,n - im}. Получены верхние оценки суммы и отношения экспонентов перемешивающих орграфов подстановки g из класса R(n,m) и обратной к ней подстановки д-1: т1

On mixing digraphs of nonlinear substitutions for binary shift registers.pdf Введение Положительным свойством преобразований векторных пространств, используемых в системах криптографической защиты информации, является полное перемешивание входных данных, то есть зависимость каждого бита выходного вектора от всех входных битов. Такие преобразования называются совершенными. При большой размерности пространства реализация совершенных преобразований затруднена в силу необходимости реализации большого количества связей между элементами входа и выхода. Поэтому полное перемешивание входных данных часто реализуется с помощью определённого количества итераций несовершенного преобразования. В связи с этим для различных преобразований векторных пространств возникает задача оценки числа итераций, необходимого для достижения полного перемешивания. Пусть подстановка g(x\,... , xn) задается системой булевых координатных функций g(xi,...,xn) = {gi(xi,...,xn),...,gn(xi,...,xn)}, где функция gj вычисляет j-й бит выходного вектора, j = 1, 2,... , n. Перемешивающим орграфом r(g) подстановки g называется n-вершинный орграф, в котором существует дуга (i,j) тогда и только тогда, когда i G S(gj), i,j G {1, 2,...,n}, где S(gj) -множество номеров существенных переменных функции gj. Орграф r(g) называется примитивным, если при некотором натуральном t ^ 1 орграф r*(g) полный. Наименьшее натуральное y, при котором орграф Г7(g) полный, называется экспонентом орграфа и обозначается expT(g). Для полного перемешивания входов с помощью преобразования g необходима примитивность перемешивающего орграфа r(g). Для оценки соответствующего количества итераций преобразования используется матрично-графовый подход, направленный на распознавание свойства примитивности перемешивающего орграфа преобразования и определение его экспонента. Свойство примитивности и значения экспонентов для разных классов матриц и орграфов изучались многими авторами [1-3]. Получены как универсальные оценки экспонентов [4, 5], так и оценки для частных классов орграфов. Для приложений представляет интерес исследование взаимосвязи экспонентов перемешивающих орграфов прямой и обратной подстановок векторного пространства. Эти вопросы изучены мало. В общем случае экспоненты прямой и обратной подстановок не совпадают. Первые результаты были получены для регистровых подстановок. В [2, с. 12] установлено, что орграф r(g) подстановки g примитивный тогда и только тогда, когда примитивен орграф r(g-1). При этом expr(g) = expr(g-1), если ik + im+2-k = n + 2, k = 2,..., m. Работа посвящена классу нелинейных регистровых подстановок векторных пространств, широко используемому в системах защиты информации. Получены оценки экспонентов перемешивающих орграфов регистровых подстановок через числа множества D(g), а также новые результаты о взаимосвязи экспонентов прямой и обратной подстановок. 1. Двусторонняя оценка экспонента Через g(x1,...,xn) G R(n,m) обозначим подстановку двоичного регистра левого сдвига длины n с обратной связью f (x1,... , xn) = x1 ф ^(x2,... , xn): g(xi, ...,xn) = (x2, ...,xn ,x1 ф ф(x2,..., xn)) = (y1,.. .,yn). (1) Преобразование g-1 (x1,... ,xn) реализуется двоичным регистром правого сдвига длины n с обратной связью yn ф ^(y1,... , yn-1): g-1(y1,...,yn) = (Уп ф ^(y1 ,...,Уп-1),У1,...,Уп-1) = (x1,...,xn), (2) где ф(x2,... ,xn) Ф ^(У1,... ,Уп-1 ) = ф(x2,... ,xn) Ф ^(x2,...,xn) = 0. Обозначим D'(g) = D(g-1) = {j1,...,jm} = {i2 - 1,...,im - 1,n} -множество номеров существенных переменных функции обратной связи преобразования g-1, где 1 ^ < ... < jm = n. Для нелинейной подстановки m = |D| ^ 3. Действительно, если функция обратной связи f (x1,...,xn) = x1 ф "0(x2,... ,xn) нелинейная, то функция усложнения ф(х2,... , xn) содержит хотя бы один моном степени не меньше 2. Следовательно, функция обратной связи имеет, кроме Х\, ещё не менее двух существенных переменных. В соответствии с (1) множество дуг n-вершинного перемешивающего орграфа Г(g) подстановки g состоит из дуг гамильтонова контура (n,... , 2,1) и дуг (i2,n),... , (im, n). Следовательно, орграф T(g) содержит m простых контуров с длинами из множества L = [l\,..., lm} = {n - im + 1,... ,n - i2 + 1, n}, где 1 ^ l1 < ... < lm = n и НОД{/! ,...,lm} =1. В соответствии с (2) множество дуг n-вершинного перемешивающего орграфа r(g-1) подстановки g-1 состоит из гамильтонова контура (1, 2,..., n) и дуг (i2 - 1,1), ... , (im - 1,1). Следовательно, орграф T(g-1) содержит m простых контуров с длинами из множества L' = {l'1,..., l'm} = {n - lm-1,... ,n - l1,n} = {i2 - 1,... ,im - 1, n}. Заметим, что НОД{11, ... , lm} = 1, если и только если НОД{1^ ,... , l'm} = 1. В соответствии с универсальным критерием орграф T(g) примитивный, если и только если он сильносвязный и НОД{11, ... , lm} = 1. Через Ф^) обозначим функцию Фробениуса для множества L натуральных аргументов: Ф^) = max{t G N : t $ {L}}, где {L} - аддитивная полугруппа, порождённая множеством L. Для получения верхней оценки экспонента T(g) используем оценку [5, с. 645] expT(g) ^ max p(i,n,j) + Ф(L) + 1, где p(i,n,j) -длина кратчайшего пути в орграфе T(g) из вершины i в вершину j, проходящего через вершину n (общую вершину всех m контуров). Для локального экспонента примитивного орграфа T(g) справедлива оценка [6, с. 104] (i,j) - exp r(g) ^ p(i,n,j) + Ф(L) + 1, где p(i, n,j) = i - y + 1 + n - j; 7 - индекс ближайшей слева ячейки съёма к ячейке j. В соответствии с (1) для примитивного орграфа T(g) max p(i, n, j) = max p(i, n, 1) = A(D) + n - 1. Отсюда получаем expr(g) ^ A(D) + n + Ф(L). (3) Технических трудностей при подсчёте оценки (3) можно избежать, воспользовавшись оценкой числа Ф^). В соответствии с [7, с. 62] Ф(11, ..., lm-1, n) ^ Ф(п - 2, n - 1, n) = = |_(n - 2)2/2j - 1. Следовательно, exp r(g) ^ A(D) + n + [(n - 2)2/2j - 1 ^ n2/2. (4) Нижняя оценка экспонента равна длине кратчайшего пути из i в j, проходящего через вершину n в орграфе T(g), в случае, когда точки съёма примерно равноудалены друг от друга на регистре: n - 1 m - 1 - 1. (5) exp r(g) ^ n + 2. Оценки суммы и отношения экспонентов перемешивающих орграфов прямой и обратной подстановок На основе оценок чисел Фробениуса [8, с. 49-50] получена верхняя оценка экспонентов перемешивающих орграфов прямой и обратной подстановок. Теорема 1. Для любой подстановки g Е R(n,m) справедлива оценка n2 m 2n2 + im ^ - + 3n - 7. expГ(д) + expr(g-1) ^ 2 ^A(D) + (6) Из полученной двусторонней оценки следует оценка отношения экспонентов: A(D) + n + (n - - 2)2 2 _ -1 n + n - 1 ■ -1 m - 1 n Заключение Для примитивных перемешивающих орграфов Г(д) нелинейных подстановок g из класса R(n, m) получена двусторонняя оценка экспонентов. Верхняя оценка (4) не превосходит n2/2, что улучшает абсолютную оценку Виландта [3, c. 102], а также при l > n/2 - оценку [9, c. 227], использующую длину l кратчайшего простого контура. Нижняя оценка (5) экспонентов уменьшается от 3n/2 - 1 до n, когда значения m пробегают от 3 до n. В (6) показано, что сумма оценок экспонентов для прямой и обратной подстановок не превосходит 2n2/3+3n-7. Отношение оценок (7) экспонентов для прямого и обратного преобразований не превосходит n/2.

Ключевые слова

Frobenius number, shift register, exponent of graph, primitive digraph, mixing digraph approach, число Фробе-ниуса, регистр сдвига, экспонент орграфа, примитивный граф, перемешивающий граф преобразования, матрично-графовый подход

Авторы

ФИООрганизацияДополнительноE-mail
Григорьев Виталий СергеевичФинансовый университет при Правительстве РФ; АО «Позитив Текнолоджиз»аспирант; специалист отдела безопасности сетевых приложенийVit.link420@gmail.com
Всего: 1

Ссылки

Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000. exPr(g) exp r(g-1)
Alfonsin R. J. The Diophantine Frobenius Problem. Oxford University Press, 2005. 260 p.
Lewin M. A bound for a solution of a linear Diophantine problem //J. London Math. Soc. 1972. No. 6. P. 61-69.
Фомичев В. М., Кяжин С. Н. Локальная примитивность матриц и орграфов // Дискретный анализ и исследование операций. 2017. Т. 24. №1. С. 97-119.
Dulmage A. L. and Mendelsohn N. S. Gaps in the exponent set of primitive matrices // Illinois J. Math. 1964. V.8. Iss.4. P. 642-656.
Фомичев В. М. Новая универсальная оценка экспонентов графов // Прикладная дискретная математика. 2014. №3(33). С. 78-84.
Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(12). С. 101-112.
Григорьев В. С., Фомичев В. М. О примитивности перемешивающих подстановок регистров сдвига // Прикладная дискретная математика. Приложение. 2017. №10. С. 14-16.
Когос К. Г., Фомичев В. М. Положительные свойства неотрицательных матриц // Прикладная дискретная математика. 2012. №4(18). С. 5-13.
 О перемешивающих графах нелинейных подстановок двоичных регистров сдвига | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/1

О перемешивающих графах нелинейных подстановок двоичных регистров сдвига | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/1