Оценка характеристик нелинейности композиций функций векторных пространств с помощью матрично-графового подхода

doi:10.17223/2226308X/12/37

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Оценка характеристик нелинейности композиций функций векторных пространств с помощью матрично-графового подхода	524 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/2226308X/12/37

#матрица нелинейности отображения

#показатель полной нелинейности

#экспонента матрицы

#орграфы

#матрично-графовый подход

Title: Оценка характеристик нелинейности композиций функций векторных пространств с помощью матрично-графового подхода
Creator: Сапегина, Марина Дмитриевна
Date: 2019
DOI: 10.17223/2226308X/12/37
Description: Развивается разработанный В. М. Фомичевым матрично-графовый подход к оценке характеристик нелинейности преобразований векторных пространств с помощью троичных матриц над мультипликативной полугруппой {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 соответственно.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. Приложение. 2019. № 12. С. 126-129
Language: rus