E-catalog        

Библиогр.: 4 назв.

Развивается разработанный В. М. Фомичевым матрично-графовый подход к оценке характеристик нелинейности преобразований векторных пространств с помощью троичных матриц над мультипликативной полугруппой {0,1,2} или орграфов, дуги которых помечены числами из {0,1,2}. Орграф Г с множеством вершин {1,...,п} называется (2)-примитивным, если при некотором натуральном t для любых i,j G {1, . . . , n} найдётся путь из i в j длины t, проходящий через дугу с меткой «2», наименьшее такое t называется (2)-экспонентом орграфа Г (обозначается (2)-ехрГ). Преобразованию g(xi,...,xn) множества Vn с координатными функциями gi(xi,..., xn),...,gn(xi,..., xn) соответствует n-вершинный орграф Г@(д), где дуга (i, j) помечена числом 0, 1 или 2 тогда и только тогда, когда gj зависит от Xi соответственно фиктивно, линейно или нелинейно, 1 i,j п. Преобразование g называют вполне нелинейным, если метка каждой дуги орграфа есть «2». Преобразование g называется (2)-перфективным, если при некотором натуральном t все дуги орграфа Ге(gt) помечены числом «2», наименьшее такое t называется показателем полной нелинейности преобразования g (обозначается (2)-nlg). Доказано: если в помеченном примитивном орграфе Г метка каждого простого контура содержит число «2» и exp Г = п, то орграф Г является (2)- примитивным и (2)-ехрГ = exp Г. Получена оценка (2)-экспонента матрицы нелинейности M порядка 2п раундовой функции блочных алгоритмов на основе сети Фейстеля с помощью (2)-экспонента матрицы нелинейности Ф порядка п функции усложнения: (2)-expM (2)-ехрФ + 2. Эти результаты позволяют снизить сложность вычисления показателя полной нелинейности для некоторых преобразований g. Представлены алгоритмы распознавания полной нелинейности преобразования g и оценки показателя (2)-nlg. Для случайных преобразований средняя сложность не превышает 2y(y + 1) log8n, где (2)-nlg = y и элементарная операция есть вычисление любой функции на любом входном наборе. Алгоритм применён для получения точных значений (2)-nlg раундовых подстановок g алгоритмов DES и Магма, получены значения 5 и 6 соответственно.