On characteristics of local primitive matrices and digraphs.pdf 1. Новые характеристики Обозначим: n - множество натуральных чисел; n Е n; = {1,... , n}; VW - множество n-мерных двоичных векторов; I, J С Nn, где 0 = I = {i1,... , }, 0 = J = = {j1,... , jr}. Матрица M называется I х J-примитивной ((i,j)-примитивной при I = {i}, J = {j}) [1], если существует 7 Е n, такое, что матрица M*(I х J), полученная из матрицы M* удалением строк с номерами i = i1,... , ik и столбцов с номерами j = j1,... , jr, положительная при любом t ^ 7. Наименьшее такое число 7 называется I х J-экспо-нентом матрицы M и обозначается I х J-expM или 7/,j. Элементарным экспонентом матрицы (орграфа) называется I х J-экспонент при I = {i}, J = {j}, где (i, j) Е N, записывается как (i, ^')-экспонент и обозначается (i, j)-expM или 7^. Если матрица M не (i, j)-примитивная, то положим (i, j)-expM = то. В развитие математического аппарата локальной примитивности неотрицательных матриц и орграфов [1, 2], используемого для оценки перемешивающих свойств преобразований множества n-мерных векторов, введём новые характеристики: матэкс, определяющий все локальные экспоненты, k, r-экспорадиус, k, r-экспоцентр, k,r Е Nn. Из множества всех элементарных экспонентов матрицы M (орграфа Г) составим квадратную матрицу M(M) = ((i,j)-expM) (матрицу М(Г) = ((i,j)-exp Г)) порядка n, которую назовём матрицей элементарных экспонентов, кратко матэксом, матрицы M (орграфа Г). Любой локальный экспонент матрицы M можно вычислить по матэксу M(M): 7/ j = I х J-expM = max (i, j)-expM, где I, J С Nra. (ij)e/xJ Если M ^ M', то (i, j)-expM ^ (i, j)-expM' для любой пары (i, j) Е N2 и M(M) ^ ^ M(M'). Определим в Г характеристики, связанные с локальными экспонентами. Назовём k, r-экспорадиусом орграфа Г величину, обозначаемую exrdk,rГ: exrdk,rГ = = min 7/,j . I xJ:|I|=fc,|J|=r При |11 = k, |J| = r множество I х J назовем k, r-экспоцентром графа Г, если yi,j = exrdfc,rГ. При любых фиксированных k,r в примитивном орграфе Г существует k, r-экспоцентр, в общем случае не единственный. Если орграф Г локально примитивный, то k, r-экспоцентр существует, если орграф Г имеет конечный k, r-экспорадиус. 2. К задаче построения s-боксов Покажем прикладное значение введённых характеристик, приведём пример расчёта. Важным элементом блочных алгоритмов шифрования являются нелинейные отображения Vk ^ VT, называемые s-боксами размера k х r и используемые при построении раундовых подстановок блочных шифров (в DES, ГОСТ 28147-89 и «Кузнечике» s-боксы имеют размеры 6 х 4, 4 х 4 и 8 х 8 соответственно). При разработке к свойствам s-боксов предъявляется ряд требований: биективность (при k = r), совершенность (то есть существенная зависимость каждой координатной булевой функции от всех входных переменных), простота программной и/или аппаратной реализации и др. При небольших размерах (r ^ 8) s-боксы обычно реализуют с помощью таблиц. Однако чем больше r, тем более ресурсоёмкой является табличная реализация как по размеру памяти, так и по времени. Значит, актуальна разработка быстрых алгоритмов реализации s-бокса. Изложим идею одного подхода. Совершенные s-боксы размера k х r, в том числе при больших k и r, можно реализовать на основе итераций преобразования g множества Vn, где п > max(k, r). Обозначим X = {x1,... , xn}; {g1(X),..., gn(X)} - система координатных функций преобразования g; G* = {g1 (X),... , gn(X)} - система координатных функций преобразования g*, t = 1, 2,...; Г - перемешивающий орграф преобразования g; M - матрица смежности вершин орграфа Г; GJ - бесповторная упорядоченная выборка размера r из множества G*, такая, что gj (X) Е GJ ^ j Е J; xi - бесповторная упорядоченная выборка размера k из множества X, такая, что x Е xi ^ i Е I. Выборкам xi и GJ при любой фиксации а переменных из X\xi соответствует система координатных функций отображения st( max(k, r) преобразований g множества Vn, таких, что, используя их степени, можно построить отображения Vk ^ V с заданным набором свойств. лей: 8 7 6 9 8 7 8 7 6 8 7 6 9 8 7 10 9 8 11 10 9 7 6 5 М(Г)

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