On primitivity of some sets of shift registers mixing digraphs.pdf Введение Основные обозначения: np = {1,... ,p}, p G n; НОД(а1,... , an) - наибольший общий делитель натуральных чисел a1,...,an; (i,j) -дуга в орграфе Г, инцидентная вершинам i и j; (X) -подполугруппа, порождённая подмножеством X мультипликативной полугруппы. Свойство примитивности перемешивающего графа криптографического преобразования, необходимое для перемешивания данных, важно для приложений в области анализа и синтеза итеративных блочных шифров и генераторов гаммы. Критерий примитивности и универсальные оценки экспонента орграфа известны [1, гл. 11]. Понятия примитивности и экспонента орграфа естественным образом распространены на множества орграфов [2, § 10.2]. Пусть Г = {Г1,... , Гр} -множество орграфов. Слову w = w1... ws в алфавите np соответствует произведение орграфов T(w) = ■ ... ■ TWs. Слово ... TWs в алфавите Г называется положительным (примитивным), если орграф T(w) полный (примитивный). Множество Г называется примитивным, если полугруппа (Г) содержит полный орграф, наименьшая длина положительного слова называется экспонентом множества Г, обозначается exp Г. Критерий примитивности множества орграфов получен автором [3], универсальная оценка экспонента примитивного множества неизвестна. Проблема распознавания примитивности множества орграфов алгоритмически разрешима, но в общем задача трудоёмкая из-за необходимости проверять примитивность большого количества слов полугруппы (Г). В частных случаях (например, когда орграфы Г^ ... , Гр имеют общие части) получены и условия примитивности, и оценки экспонентов. Работа посвящена исследованию примитивности множеств перемешивающих орграфов регистровых преобразований, особенностью орграфов является наличие общего гамильтонова контура. Выбор объекта исследования обоснован широким применением регистров сдвига в современных криптосистемах. 1. Множество перемешивающих орграфов регистров правого сдвига Получены условия примитивности множества орграфов Г = {Го,..., Гп-1} с вершинами 0,... , n - 1 и оценка экспонента множества Г. Случай множества перемешивающих орграфов регистров левого сдвига рассматривается симметрично. Теорема 1. Пусть орграф Г из множества Г имеет гамильтонов контур (0,... , n-1) идугу (i, (i+/)mod n), n ^ l > 1, i = 0,... , n- 1. Тогда множество Г примитивное, если и только если НОД(п, I - 1) = 1, при этом n - 1 ^ exp Г ^ 2n - 2. Пусть d = НОД(п,/) и T(d) = {Г G Г : i = 0mod d}, тогда множество T(d) примитивное, если НОД(п, I - 1) = 1, и exp T(d) ^ 2n - 2. Заметим, что множество Г теоремы 1 содержит орграфы Виландта. Теорема 2. Пусть орграф Г из множества Г имеет гамильтонов контур (0,... , n - 1) и дуги (i, (i + /) mod n) и (i, (i + Л) mod n), n ^ Л > / > 1, i = 0,... , n - 1. Тогда: а) множество Г примитивное, если и только если НОД(п, / - 1,Л -1) = 1, при этом exp Г ^ (V8n+I - 3)/2; б) если НОД(п, / - 1) = 1, то exp Г ^ n - 1 + max{b, n - b +1}, где b = (Л - 1)(/ - 1)^(n)-1 mod n. В табл. 1 и 2 даны оценки экспонентов множеств графов в условиях теорем 1 и 2 соответственно при некоторых значениях n, / и Л. Таблица 1 Оценки экспонентов множеств графов (теорема 1) n 1 Полный орграф exp Г, i = 0,..., n - 1 exp Г 5 2 Г2Г4Г1Г3Г0Г2Г4Г1 17 4 < exp Г < 8 6 2 Г2Г4Г0Г2Г4Г0Г2Г4Г0Г2 26 5 < exp Г < 10 7 2 Г2Г4Г6Г1Г3Г5Г0Г2Г4Г6Г1Г3 37 6 < exp Г < 12 8 4 (Г4Г0)7 38 7 < exp Г < 14 Таблица 2 Оценки экспонентов множеств графов (теорема 2, б) n l Л b r = max{b, n - b +1} Полный орграф exp Г,, i = 0,.. . ,n - 1 exp Г 5 2 4 3 r = max{3, 3} = 3 Г2Г4Г1Г3Г0Г2Г4 9 exp Г < 7 6 2 4 3 r = max{3,4} = 4 Г2Г4Г0Г2Г4Г0Г2Г4Г0 14 exp Г < 9 7 2 5 4 r = max{4,4} = 4 Г2Г4Г6 Г1Г3Г5Г0Г2Г4Г6 19 exp Г < 10 8 4 5 4 r = max{4, 5} = 5 Г4Г0Г4Г0 Г4Г0Г4Г0Г4Г0Г4Г0 22 exp Г < 12 2. Множество орграфов регистров с разнонаправленными сдвигами Теорема 3. Пусть n чётное, орграф Г* при чётных i имеет контур (0,... , n - 1) и дугу (i, (i+l) mod n), при нечётных i - контур (n-1,... , 0) и дугу (i, (i+A) mod n). Если НОД(п, I -1) = 1 или НОД(п, A+1) = 1, то множество Г примитивное и exp Г ^ 2n - 2. Полученные оценки экспонентов множеств графов имеют порядок O(n). В то же время экспонент отдельного орграфа множества в ряде случаев имеет порядок O(n2) и достигает максимального значения n2 - 2n + 2.

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