Mixing properties of 2-cascade generators.pdf Введение Важным свойством генератора гаммы является зависимость знаков гаммы Yi от всех знаков начального состояния при i > io, где io определяет длину холостого хода генератора. Для этого свойства необходима примитивность (локальная примитивность) перемешивающего графа преобразования множества состояний генератора. Пусть Nn = {1,..., n}; I, J С Nn, I = 0, J = 0; M - 0,1-матрица порядка n>1; M(I х J) -её подматрица размера |I| х | J|, полученная из M удалением строк с номерами i Е/ I и столбцов с номерами j Е/ J. Матрица M называется примитивной (I х J-примитивной), если существует такое натуральное число Y, что M* > 0 (M*(I х J) > 0) при любом t ^ y. Наименьшее такое y называется экспонентом (I х J-экспонентом) матрицы M, обозначается exp M (I х J-exp M). Матрица M называется I х J-квазипримитивной, если при некотором натуральном 8 подматрица M*(I х J) не имеет нулевых строк для любого t ^ 8. Наименьшее такое 8 называется I х J-квазиэкспонентом матрицы M, обозначается I х J-qexp M. Под примитивностью (I х J-примитивностью, I х J-квазипримитивностью) орграфа Г понимается соответствующее свойство его матрицы смежности M, при этом соответствующие экспоненты и локальные экспоненты орграфа Г и матрицы M равны. Цель работы - применить ранее полученные условия примитивности [1, с. 226] и локальной примитивности [2] орграфов для оценки перемешивающих свойств некоторых двухкаскадных генераторов. Обозначим: V -множество двоичных r-мерных векторов; S(/) -множество номеров существенных переменных функции /; s - сумма длин регистров генератора, (x1,...,xs) - начальное состояние регистров, m,n,r -длины регистров (m - управляющего, n, r - генерирующих), m,n,r > 1; h - преобразование множества Vs состояний генератора; h\ - i-я координатная функция преобразования h*, i = 1,...,s; r(h) -перемешивающий s-вершинный орграф преобразования h; Yt - t-й знак гаммы, t = 1,2,... 1. Последовательное соединение регистров сдвига Пусть генератор построен на основе последовательного соединения двоичных регистров правого сдвига длины m и n с булевыми функциями обратной связи /1(х1,... ,xm) и /2 (xm+1,... , xm+n) соответственно. Положим S (/1) = {b1,...,bv}, S(/2) = {c1,..., cM}, где 1 ^ b1 < ... < bv = m, m +1 ^ c1 < ... < = m + n, НОД(&1,..., bv) = d1, НОД(С1 - m,..., cM - m) = Уравнения гаммообразования: Yt = hm+n(x1,... ,xm+n). Таким образом, для анализа свойств гаммы генератора представляет интерес величина Nm+n х {m + n}-exp r(h). Утверждение 1. Орграф r(h) является Nm+n х {m + n}-примитивным, если и только если d2 = 1, в этом случае Nm+n х {m + n}-exp r(h) ^ n + max{m, p2} + g(c1 - m,..., cM - m), где p2 = max {c - Q-J; Co = m. l=1,...;Ju Следствие 1. Если c1 = m + 1, то r(h) является Nm+n х {m + п}-примитивным и Nm+n х {m + n}-exp r(h) = n - 1 + max{m, p2}. Утверждение 2. Орграф r(h) является Nm х {m+nj-примитивным, если и только если (d1, d2) = 1, в этом случае Nm х {m + n}-exp r(h) ^ p1 + m + n + g(b1,...,bv, c1 - m,..., cM - m), где p1 = max {b - fy-1}; bo = 1. l=1,...,v Следствие 2. Если c1 = m + 1, то r(h) является Nm х {m + n}-примитивным и Nm х {m + n}-exp r(h) = m + n - 1. 2. Генератор 1-2 шага Генератор 1-2 шага построен на основе управляющего и генерирующего линейных регистров сдвига (ЛРС) длины m и n. Преобразование h нелинейное в силу неравномерности движения генерирующего регистра, определяемого управляющей функцией u(x1, . . . , xm). Пусть управляющий и генерирующий регистры правого сдвига имеют соответственно длины m> 2 и n> 2 и функции обратной связи /y(x1,... ,xm) и /r(xm+1, ... ,xm+n). Положим S(/у) = {b1,... ,bv}, S(/г) = {c1,... ,cM}, где 1 ^ b1 < ... < bv = m, m +1 ^ c1 < ... < cM = m + n. Уравнения гаммообразования имеют вид Yt = hm+n(x1,... ,xm+n). Оценим величину Nm+n х {m + n}-exp r(h), важную для анализа гаммы генератора. Утверждение 3. Граф r(h) является Nm+n х {m + n}-примитивным и Nm+n х {m + n}-exp r(h) = max{m, p} + A(A - 1) + |~n/2], (1) где A = |"(C1 - m)/2]; p = max{|"(c2 - c^/2],... , [(cM - cM-1)/2]}. Следствие 3. Граф r(h) является Nm х {m + n}-примитивным и Nm х {m + n}-exp r(h) = m + A(A - 1) + [n/2]. (2) Приведём числовые примеры. Пусть m = 7, n = 20, S(u) = {m}. При S(/г) = {m + n - 1, m + n} выполнено A = |~(n - 1)/2] =10, p = 1. Тогда из (1) и (2) следует: N7 х {27}-exp r(h) = N27 х {27}-exp r(h) = 107. При S(/г) = {m + 2, m + n} выполнено A = 1, p = |~(n - 2)/2] = 9. Тогда из (1) и (2) следует: N7 х {27}-exp r(h) = 17, N27 х {27}-exp r(h) = 19. 3. Генератор с перемежающимся шагом Генератор с перемежающимся шагом построен на базе двоичных ЛРС: управляющего ЛРС длины m и двух генерирующих ЛРС длины n и r с функциями обратной связи fy(xi,..., Xm), f i (xm+i,... , xm+n) и /2 (xm+n+i,... , xm+n+r) соответственно. В зависимости от знака управления сдвигается информация либо в первом, либо во втором генерирующем ЛРС, в силу чего преобразование h генератора нелинейное. Пусть Ji = {m + 1,...,m + n}, J2 = {m + n + 1,..., m + n + r}, S(/у) = {bi,..., bv}, S (/i) = {ci,...,cM}, S (/2) = {di,...,dCT}, где 1 ^ bi < ... < bv = m, m + 1 ^ ci < ... <

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