Estimation of local nonlinearity characteristics of vector space transformation iteration using matrix-graph approach.pdf Введение В некоторых приложениях, в том числе криптографических, важно определить множество переменных, от которых нелинейно зависит каждая функция из заданного подмножества координатных функций преобразования векторного пространства. Эта информация может быть использована для оценки эффективности некоторых методов линеаризации при получении оценки стойкости криптографических алгоритмов. Представленные результаты направлены на получение оценок множеств переменных, по которым нелинейны те или иные координатные функции преобразования векторного пространства, построенного по итеративному принципу. Приведём ряд определений [1]. Преобразованию g (xi,... , xn) множества V„ двоичных n-мерных векторов с координатными функциями gi (xi,... , xn) ,..., gn (xi,... , xn) соответствует n-вершинный орграф Г (g), где дуга (i, j) помечена числом 0, 1 или 2 тогда и только тогда, когда gj (xi,... , жп) зависит от ж соответственно фиктивно, линейно или нелинейно, 1 ^ i, j ^ n. Преобразование g (xi,... , xn) называется I х J- (2)-нелинейным, если любая дуга (i, j) G 1х J в орграфе Г (g) помечена символом «2». Преобразование g (xi,... , жп) называется Iх J- (2)-перфективным, если при некотором натуральном t преобразование g* является 1х J-нелинейным, наименьшее такое t называется показателем полной 1х J- (2)-нелинейности преобразования g (xi,..., жп) (обозначается ^J- (2)-nlg). Характеристики орграфа re (g*) можно оценить с помощью матрицы меток орграфа Г (g), обозначаемой Me (g), что следует из неравенства для любых преобразований g(i),..., g(t) множества Vra [1]: Me (g(i),... ,g(t)) ^ Me (g(i)) ... Me (g(t)). Проекция этого неравенства на подмножества 1 х J даёт следующую оценку: Me (g(i),... ,g(t)) (1 х J) ^ Me (g(i)) (I х J) ...Me (g(t)) (I х J), I, J С {1,..., n} . Таким образом, локальные характеристики матрицы нелинейности Me )g(i),... ,g(t)) можно оценить с помощью локальных характеристик матрицы Me (g(i)) ... Me (g(^). В частности, локальные характеристики матрицы нелинейности Me (g*) можно оценить с помощью локальных характеристик t-й степени матрицы нелинейности Me (g). 1. Локальная а-примитивность троичных матриц и помеченных орграфов Троичная матрица называется особенной, если она имеет нулевую строку или нулевой столбец. Обозначим: Mn - множество квадратных неособенных троичных матриц порядка n; M (1х J) -подматрица матрицы M G Mn (называемая 1х J-подматрицей), полученная вычеркиванием из M строк с номерами из 1 и столбцов с номерами из J, где I, J С {1,... , n}. Неособенная матрица называется: - (2с)-матрицей, если каждый столбец матрицы содержит элемент 2; - (2з)-матрицей, если каждая строка матрицы содержит элемент 2; - (2зс)-матрицей, если она является (2с)-матрицей и (2з)-матрицей; - (2)-матрицей, если каждый элемент матрицы равен 2. Для a G П (2) обозначим M^ (1 х J) множество всех матриц M G Mn, чьи 1 х J-под-матрицы являются a-матрицами. Матрицу M назовём 1 х J-a-примитивной, если существует y G N, такое, что M* G G Mn (1 х J) при всех натуральных t ^ y, a G П(2). Наименьшее из таких чисел y обозначим 1 х J-a-exp M и назовём 1 х J-a-экспонентом матрицы M. Обобщённо назовём свойства 1 х J-a-примитивности матриц в случае 1 и J, не равных {1,... , n}, свойством локальной a-примитивности матриц для всех a G П (2). Случай 1 = J = {1,... , n} называется a-примитивностью и исследован в [1]. В случае a-примитивности наименьшее t G N, такое, что M* G M^, равно a-экспо-ненту, в то время как для локальной a-примитивности в общем случае это не верно. Обозначим Qs (1 х J) , Qc (1 х J) множества матриц M G Mn, чьи 1 х J-подматрицы не имеют нулевых строк и столбцов соответственно; Qsc (1 х J) = Qs (I х J) П Qc (I х J). Для случая I = J обозначим эти множества Qs (12), Qc (12), Qsc (12). Если M* G Mraa (1 х J), то в соответствии с определением этого недостаточно для того, чтобы выполнялось равенство t = 1 х J-a-exp M. Укажем условие, когда наименьшее t G N, при котором M* G M^ (1 х J), равно 1 х J-a-экспоненту матрицы. Теорема 1 (обобщение утверждения 1,а [2]). Пусть t G N - наименьшее натуральное число, при котором A* G Ma (1 х J), a G П(2), тогда A является 1 х J-a-примитивной и t = 1 х J-a-exp A, если a = (2s), A g Qs (12) U Qs (J2); a = (2c) , A G Qc (12) U Qc (J2)) ; a = (2sc), A е Qsc (I2) U Qsc J ; a = (2), A е Qs (12) U Qc (J2) . При n > 1 троичной матрице M = (mi,j) порядка n биективно соответствует помеченный n-вершинный орграф Г, у которого дуга (i, j) имеет метку mi,j, 0 ^ i, j < n, где метка «0» равносильна отсутствию дуги в орграфе [1]. Неособенной матрице соответствует орграф, каждая вершина которого имеет ненулевые полустепени исхода и захода, такие орграфы назовём также неособенными. Помеченный орграф называется I х J-a-примитивным, если I х J-a-примитивна его матрица меток (mi,j). На множестве Гп неособенных помеченных орграфов порядка n определена полугрупповая операция умножения орграфов Г и Г': если в Г имеется дуга (i,mi,r, r), а в Г' имеется дуга (r,^r,i,j), то в орграфе ГГ' имеется дуга (i,mi,r^r,j, j), где операция умножения меток выполняется в полугруппе G. Доказано [1, следствие 1], что в орграфе Г* дуга (i, j) имеет метку «0», если и только если в Г вершина j недостижима из вершины i за t шагов; «1», если и только если в Г любой путь из i в j длины t состоит только из дуг с меткой «1»; «2», если и только если в Г имеется путь из i в j длины t, содержащий дугу с меткой «2». 2. Оценки локальных a-экспонентов некоторых классов орграфов В случае I = {i} , J = {j} свойства IxJ-a-примитивности для любого a е П (2) одинаковы. Назовём этот случай ixj- (2)-примитивностью, а соответствующий экспонент орграфа Г обозначим i х j - (2)exp Г. Сильносвязный подграф Г' с множеством вершин V орграфа Г называется i,j-связывающим, если в Г существует путь из i в j, проходящий через некоторую вершину множества V С {1,... , n}. Теорема 2. а) Орграф Г I х J- (2)-примитивный, если и только если Г i х j - (2)-примитивный для всех (i, j) е I х J; в этом случае I х J- (2)exp Г = max {i х j - (2)exp Г}. (i,j)eixJ б) Орграф Г Iх J- (2в)-примитивный, если и только если Г ix J- (2s)-примитивный для всех i е I; в этом случае I х J- (2s)exp Г = max {i х J- (2s)exp Г}. iei в) Орграф Г I х J- (2с)-примитивный, если и только если Г I xj- (2c)-примитивный для всех j е J; в этом случае I х J- (2с) exp Г = max {I х j - (2с) exp Г}. jJ Обозначим р (i,V) -наименьшее расстояние от вершины i до подмножества вершин V; р (V, j) -расстояние от подмножества вершин V до вершины j; U (i,V) (U (V, j)) -длина кратчайшего пути из i до V (от V до j), содержащего дугу с меткой «2». Теорема 3 (обобщение теоремы 2, а [2]). Если связный помеченный орграф Г содержит примитивный i, j-связывающий подграф Г' с множеством вершин V, |V| = n, то Г является i х j - (2)-примитивным, если выполняется хотя бы одно из следующих условий: а) в подграфе Г' есть дуга с меткой «2», тогда i х j - (2)exp Г ^ р (i, V) + n + exp Г' + р (V,j); б) в кратчайшем пути из i до множества вершин подграфа V или от множества вершин подграфа V до вершины j есть дуга с меткой «2», тогда i х j-(2)exp Г ^ р (i, V) + exp Г' + р (V, j); в) существует путь из i до множества вершин подграфа V, содержащий дугу с меткой «2», тогда i х j-(2)exp Г ^ U (i, V) + exp Г' + р (V, j); г) существует путь от множества вершин подграфа V до вершины j, содержащий дугу с меткой «2», тогда i х j-(2)exp Г ^ р (i, V) + exp Г' + U (V,j). Пример 1. Рассмотрим преобразование регистра левого сдвига длины 6 с функцией обратной связи f (x0, Xi, Ж2, Хз, £4, £5) = Хо Ф Х2Ж4 ф Х5. Орграф Г этого преобразования представлен на рис. 1, матрица M - на рис. 2. Определим оценку значения 1х3-(2)-экспонента для этого орграфа. Вершины 5 и 4 образуют 1,3-связывающий подграф Г', где n = |V| = 2, exp Г' = 1, р (1, V) = 2, р (V, 3) = 1, U (1, V) = 4, U (V, 3) = 3. Оценки 1 х 3-(2)-экспонента графа Г приведены в таблице. Рис. 1. Орграф нелинейности преобразования регистра сдвига /0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 0 0 0 0 1 0 2 0 0 0 0 1 1 Рис. 2. Матрица нелинейности преобразования регистра сдвига Сравнение оценок 1 X 3-(2)-экспонента графа Г Значение оценки i xj-(2)-экспонента Формула оценки ixj-(2)-экспонента 6 i х j-(2)exp Г < р (i, V) + n + exp Г' + р (V,j) 6 i xj-(2) exp Г < d (i,V) + exp Г' + р (V,j) 6 i x j - (2) exp Г < р (i, V) + exp Г' + d (V, j) При возведении матрицы M в степень получаем, что 1 х 3-(2) -exp Г = 6, что соответствует полученным оценкам.

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