On complexity of formal coding method for analysis of generator withmonocycle substitutional transition function.pdf Обозначим: Mn - множество всех мономов, зависящих от переменных x l , .. .,x n;Mn,d - подмножество всех мономов степени -, где 0^ - ^ n. На Mn имеется частичныйпорядок: x^ ... xjd ^ x si ... xSl ^ ( j i , ..., j d} С { s l , ..., s }. Решётка Mnизоморфна решётке Vn двоичных n-мерных векторов, при этом изоморфизме вектору6 = (6l , ..., 6n) . Vn соответствует моном x5 = x i1 ... x^1 . Mn, где x^ = xj при 6j = 1и x5j = 1 при 6j = 0, 1 ^ j ^ n.Систему уравнений f i(x l , . .. , xn) = a^, i = 1 ,...,m , заданную полиномами надG F (2), обозначим Fm,n = a. Левая часть системы определяет отображение Vn ^ Vm,правая часть a = (al , ... , am) . Vm.Обозначим: M ( f ) - множество мономов ненулевой степени полинома f (x l , . .. ,x n),mM (Fm,n) = (J M ( f i (xl , . . . , xn)) - множество мономов ненулевой степени системыi=lвсех координатных полиномов Fm,n. Для полинома f ( x l , . . . , x n) (для системы Fm,n)над G F (2) величину |M(f)| (|M(Fm,n)|) называют весом полинома f (весом системыFm,n), обозначается w p (f) (wp(Fm,n)).При решении системы уравнений Fm,n = a методом формального кодирования каждыйненулевой моном из M (Fm,n) заменяется новой переменной: xt1 . .. xjs = Zj, послечего система уравнений Fm,n = a преобразуется в линейную систему Lm,v = a отпеременных zl , . . . , z v, то есть Lm,v - система m булевых линейных полиномов от vпеременных, где v = wp(Fm,n). Система линейных уравнений Lm,v = a решается известнымиметодами. При решении совместной системы достаточно рассмотреть лишьмаксимальную подсистему из ^ линейно независимых уравнений, где ^ = dim (Fm,n) -размерность линейной оболочки системы полиномов Fm,n (число линейно независимыхстрок матрицы Lm,v). Сложность решения совместной системы уравнений полиномиальнозависит от ^ и v. Например, метод Гаусса решения системы уравнений над полемимеет сложность порядка max{^, v} (min{^, v } )2 операций поля.Рассмотрим генератор двоичной гаммы, моделируемый автономным автоматомA = (Vn, Vi, h, f ), где Vn - множество состояний; Vi - выходной алфавит; f - функциявыходов; h - функция переходов, реализующая полноцикловую подстановку множестваVn.Уравнения гаммообразования автомата A описываются системой уравнений Fm,n == а, где fi(x 1 , . .. , xn) есть i-я выходная функция автомата: f i(x1, . .. , xn) == f (hi(x1, ... , xn)), i = 1 ,..., m. Гамма и последовательность { f i(x1, . . . , жп)} выходныхфункций автомата являются чисто периодическими, длины их периодов совпадают иявляются делителями числа 2n.Пусть длины их периодов равны 2*, где 1 < t ^ n. Оценим сложность определенияначального состояния генератора методом формального кодирования по известномупериоду гаммы, то есть по отрезку длины 2*. Следовательно, требуется определитьdim (^2т,п) и |M(F*T,n)|, где т = 2t-1.Пусть r - натуральное число, W = {w^} - чисто периодическая последовательностьнад Vr с длиной периода 2т = 2*, где т > 1, mw (А) - минимальный многочлен(над G F (2)) последовательности W . Длину периода периодической последовательностиW обозначим per W .Последовательность W компенсированная, если w1 ф ® w2T = ur, где ur - нульпространства V .Теорем а 1. mw (Л)=(Аф1)в, где т+ 1 ^ s ^2т - e (W ) и e (W ) = 1 (= 0), если W -компенсированная (не компенсированная); при этом s = т +1, если Wi ф wi+T = а приа = ur и при всех i= 1 ,... ,т.С л ед стви е 1. dim(F2T,n) ^ т +1.Для автомата A обозначим чисто периодические последовательности: W(h) == {h i(un)} - последовательность состояний при начальном состоянии un; f (W(h)) == { f (hi(un) )} - соответствующая ей выходная последовательность; f (H ) = { f (h1)} -последовательность выходных функций, i = 0, 1, 2, . . .На периоде последовательности W (h) определим порядковый номер вектораY Е Vn (обозначим его n(Y)): n(un) = 0, n(Y) - наименьшее натуральное число t,такое, что h*(un) = y . Для монома X степени d > 0, где 6 Е Vn, определим многочлен(Л) = Av(y) над G F (2), где v (y ) - наименьший неотрицательный вычет числа n(Y)по mod (2т); ^ есть стандартный частичный порядок на Vn. Многочлен ^ (Л ) назовемA-многочленом монома X .Обозначим g = hT. Заметим, подстановка g состоит из т циклов длины 2п/ т .Лемма 1.а) Моном X степени d > 0 не содержится в M ( f (H )) ^ A-многочлен (А) мономаX либо нулевой, либо аннулирующий для последовательности f (H ).б) Если (А) аннулирует последовательность f (H ) и y ^ 6 для y ,6 Е Vn, то иg (Y) ^ 6.Для монома X обозначим: Un(X ) = {. Е Mn: X ^ .}; Un(X ) = Mn\Un(X ). Прилюбом 6 из Vn множество Un(X ) не содержит монома жеп и множество Un(X ) не пустои образует в Mn подрешётку, изоморфную решётке Мга_рц, где ||6|| - вес вектора 6.Обозначим также: Mn(Y ,e ) = (Un(xY) П Un(xe)) U (Un(xe) П Un(xY)), где y , в Е Vn.Теорем а 2. Множество M ( f (H )) содержит M ( f (ж1, . . . , xn)) и все мономы степениd > 0 из U Mn(Y, g(Y)) с ненулевым A-многочленом.YevnТеорем а 3. Если per f (H ) = 2n, то |M(f (H))| ^ 2n_ 1 и при случайном равновероятномвыборе h из класса всех полноцикловых подстановок математическое ожиданиеоценивается как E|M(f (H))| ^ 2n - (1,5)n + (1,25)n.Вы в оды1) Последовательность выходных функций генератора гаммы, построенного на основеполноцикловой подстановки множества состояний Vn, имеет высокую линейнуюсложность Л, а именно 2n-i + 1 ^ Л ^ 2n.2) Для порядка множества мономов на периоде последовательности выходныхфункций генератора верны оценки: 2n-i ^ |M(f(H))| ^ 2n - 1. При n ^ то и прислучайном равновероятном выборе функции переходов h из класса всех полноцикловыхподстановок множества Vn математическое ожидание величины |M(f (H )) |/(2n - 1)стремится к 1.3) Сложность Tn определения начального состояния методом формального кодированияоценивается как TL(2ra_l) < Tn < TL(2n), где TL(m) - сложность решениянад G F (2) системы линейных уравнений размера m х m.

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