О перемешивающих свойствах нестационарного регистра сдвига | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/25

О перемешивающих свойствах нестационарного регистра сдвига

Для регистра сдвига длины n, функция обратной связи которого зависит от двоичного знака управляющей последовательности (на каждом такте реализуется одно из двух регистровых преобразований), исследовано минимальное число y тактов регистра, после которых достигнуто полное перемешивание, то есть существенная зависимость каждой координатной функции композиции преобразований от всех переменных. Эффект полного перемешивания оценен с помощью множества Г перемешивающих n-вершинных орграфов регистровых преобразований, имеющих общий гамильтонов контур. Дана оценка экспонента exp Г примитивного множества Г, которая позволяет оценить снизу число 7: exp Г < 2n - 2 + £ (f(n - S(pa)) + da + s^) , a=0 ^ ' где S(ipa) = |s®,...,sm(a^ -множество номеров существенных переменных функции обратной связи ^>а0,..., xn-1); n - S(<^a) = {n - sa : j = 1,..., m(a)}; da = НОД{п - S(pa)}; F(n - S(pa)) = d^((n - S((fia))/da); Ф((n - S(^«))/d«) - число Фробениуса. Проведён вычислительный эксперимент при n = 6 и 10 по вычислению точного значения 7 с учётом управляющей последовательности. Установлено, что полное перемешивание возможно за число тактов, превышающее значение экспонента менее чем в 2 раза.

On mixing properties of non-stationary shift register.pdf Введение Принцип перемешивания, описанный К. Шенноном [1], важен при построении криптографических систем, устойчивых к дифференциальному анализу и атакам, основанным на последовательном опробовании элементов ключа. Для хорошего перемешивания необходимо, чтобы преобразование было совершенным, т. е. чтобы каждая координатная функция существенно зависела от всех переменных [2]. Одним из способов построения совершенного преобразования является использование композиции нескольких преобразований, каждое из которых не является совершенным, но допускает относительно несложную реализацию. Объектом исследования является нестационарный регистр сдвига (НРС) над пространством двоичных векторов Vn. Функция обратной связи НРС зависит от знака управляющей двоичной гаммы, за счёт чего на каждом такте реализуется одно из двух преобразований пространства V^. Таким образом, за t тактов работы НРС реализуется композиция преобразований длины t. Актуальной задачей является оценка перемешивающих свойств НРС в зависимости от управляющей последовательности. 1. Определяющие свойства перемешивания с помощью композиции функций Пусть G = {gi,... , gp} -множество преобразований пространства двоичных векторов Vn, где p, n > 1. Преобразованию gT Е G поставим в соответствие орграф r(gT), в котором пара вершин (i,j) является дугой, если и только если переменная x преобразования gT является существенной для координатной функции с номером j. Орграф r(gT) называется перемешивающим графом преобразования gT, т = 1,... ,p. Композиции функций g(w) = gWl ... gWs, где gWl,... , gWs Е G, s > 1, соответствует перемешивающий граф r(g(w)) = r(gw1... gWs). Преобразование g(w) совершенное, если и только если r(g(w)) полный. Пусть Г = {Г1,..., Гр} -множество орграфов, где TT = r(gT), т = 1,...,p. Тогда порождённая множеством Г полугруппа имеет вид (Г) = {r(w): w Е N^}, где r(w) = ГШ1 ... rWs при w = w1... ws; N^ -множество всех слов в алфавите {1,... ,p}; умножение орграфов определяется как умножение бинарных отношений. Множество Г называется примитивным, если полугруппа (Г) содержит полный орграф. Наименьшая длина произведения, соответствующего полному орграфу, называется экспонентом множества Г и обозначается exp Г. Известно [2], что орграф ^g(w)) является частью орграфа Г^). Следовательно, если орграф Г^) не полный, то преобразование g(w) не является совершенным. Таким образом, примитивность множества Г является необходимым условием существования совершенной композиции преобразований из множества G. Если найден экспонент примитивного множества Г, то исключена необходимость проверять совершенность любой композиции, длина которой меньше exp Г. 2. Перемешивающие свойства НРС Нестационарным регистром левого сдвига над Vn с обратной связью ^(ж0,... , xn-1,a) назовём отображение g: Vn+1 ^ Vn, если g(xo,... ,Xn-i, а) = (xi,... ,Xn-i,

Ключевые слова

гамильтонов контур, примитивность множества орграфов, экспонент орграфа, экспонент множества орграфов, primitivity of digraphs set, exponent of digraph, exponent of digraphs set

Авторы

ФИООрганизацияДополнительноE-mail
Авезова Яна ЭдуардовнаАО «Позитив Текнолоджиз»аналитикavezovayana@gmail.com
Всего: 1

Ссылки

Shannon C. E. Communication theory of secrecy systems // Bell System Technical J. 1949. V.28. P. 656-715.
Фомичев В. М., Мельников Д. А. Криптографические методы защиты информации. В 2 ч. Ч. 1. Математические аспекты. М.: Юрайт, 2016. 209 c.
Авезова Я. Э. Свойства примитивных множеств ориентированных графов с общим множеством контуров // Прикладная дискретная математика. 2019. №43, С. 101-114.
 О перемешивающих свойствах нестационарного регистра сдвига | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/25

О перемешивающих свойствах нестационарного регистра сдвига | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/25