The properties of external control sequences.pdf Свойства выходной гаммы и преобразований состояний генератора с внешнимуправлением неравномерным движением существенным образом определяются свойствамиуправляющей гаммы. Например, в генераторах «$-т-шагов» и в генераторахс перемежающимся шагом, построенных на основе линейных регистров сдвига (ЛРС)с максимальными длинами периодов, порядок линейной подгруппы циклической группыпреобразований состояний генератора определяется длиной периода t управляющейгаммы [1,разд. 18.4.2, 2]: линейные уравнения гаммообразования соответствуют всемтактам работы генератора, номера которых кратны t.Показано, что в генераторах с внешним управлением доля линейных уравненийгаммообразования тем больше, чем меньше h-период управляющей последовательности,где h - функция, отображающая отрезки управляющей последовательности в подходящеемножество. Свойства h-периодов последовательностей над No для конкретнойфункции h суммирования членов последовательности, полученные в [3], в работе обобщены.Для аддитивных функций h доказано, что длина h-периода периодической последовательностиделит длину периода, для некоторых h исследованы длины h-периодовпоследовательностей де Брёйна и линейных рекуррентных последовательностей надконечными полями.Для широкого класса генераторов гаммы с внешним управлением неравномернымдвижением показано, что доля линейных уравнений относительно знаков промежуточногосостояния среди уравнений гаммообразования, соответствующих знакам периодагаммы, равна 1/ т , где т - длина h-периода управляющей гаммы и h - аддитивнаяфункция маркировки слов.Пусть N - множество натуральных чисел; No = N U {0}; X ^ = {x 0,x 1, . . . } - последовательностьнад множеством X ; X * = У X s -множество всех слов натуральнойдлины в алфавите X ; (t, т ) -наибольший общий делитель чисел t, т Е N.Множество X * образует полугруппу относительно операции конкатенации. Результатконкатенации слова u длины ( и слова п' длины (' есть слово uu' длины (+ ( '. Слово,x v+1,. .. , xv+s -1 длины s в алфавите X (обозначим его X(v,s)) называют s-граммойпоследовательности X ^, где t Е N, v Е N0.Обозначим t = t(X ^ ) и v = v(X^) -длины периода и предпериода последовательностиX ^. Период последовательности X ^ есть слово +i, xv+i+1, ... , xv+i+t-1 прилюбом i ^ 0, а предпериод - слово x0,x 1, ... , -1 при v ^ 0. Если v(X^) = 0, то X ^предпериода не имеет и называется чисто периодической последовательностью.Рассмотрим функцию h : X * ^ Y , где Y - некоторое множество. Функцию h можнорассматривать как обобщение хеш-функции. Через hs обозначим ограничение функцииh на множество X s, то есть hs : X s ^ Y , s ^ 1.При натуральном s и при ^ Е N0 последовательности X ^ поставим в соответствиепоследовательность X е ё s-грамм: X = {(x(M+ks>s)), k = 0 ,1 ,...}, которой такжесоответствует последовательность h(X^;s) над Y : h(X^s) = {hs(x(M+kS)S)), k = 0, 1,. ..} .Последовательность X ^ назовем h-периодической, если при некоторых s Е N и^ Е N0h(x(Ju+ks,s)) h(x(^+(k+1)s,s)), k ° 1 ; (1)равенство (1) будем интерпретировать так: в X ^ имеются ^-совпадения с начальнымномером ^. Наименьшее из таких s назовем длиной h-периода последовательностиX ^ (обозначается th(X^), кратко th), и если th - длина h-периода, то наименьшийиз начальных номеров совпадения ^ назовем длиной h-предпериода последовательностиX ^ (обозначается vh(X^), кратко vh). Если (1) выполняется при ^ = 0, топоследовательность X ^ назовем чисто h-периодической. Для последовательности X ^назовем h-периодом слово .(M+ks,s) и h-предпериодом - слово x0, x 1, . . . , xM-1, где s = thи ^ = vh, k = 0, 1,...Заметим, если в периодической последовательности имеются ^-совпадения с начальнымномером ^, то не обязательно th делит s и vh равно ^. Это подтверждаетсяпримером чисто периодической последовательности X ^ над N0 приhs(Xi,Xi+1, ... ,Xi+s-1) = Xi + Xi+1 + ... + Xi+s-1, где s > 0, i Е N0, a Е N:X ^ = {a, 2a, 0,0, 2a, a, a, 2a, 0,0, 2a, a, a, 2a, 0 ...} . (2)Длинапериода последовательности X ^ равна 6, в X ^ имеются ^-совпадения с начальнымномером 0 и h2-совпадения с начальным номером 1, но нет ^-совпадений.Следовательно, th(X^) = 2, vh(X^) = 1.Отметим элементарные свойства h-периодических последовательностей.1) Периодическая последовательность X ^ с длиной предпериода v и длиной периодаt является h-периодической для любой функции h : X * ^ Y , при этомth ^ t, vh ^ v (в X ^ имеются ^-совпадения с начальным номером v).2) Подпоследовательность {x j,x j+ i,. . . } h-периодической последовательности X ^с длиной h-периода th и длиной h-предпериода vh является чисто h-периодической,если и только если (i - Vh) кратно th.3) Не всякая h-периодическая последовательность является периодической, чтопоказывается примером последовательности хаотически чередующихся s-граммu и w в алфавите X , где hs(u) = hs(w):X ^ = {u ,w ,w ,u ,u ,w ,u ,w ,w ,u ,u ,w ,u ,w ,u ,w ,w ,u ...}.В чисто h-периодической последовательности X ^ имеются ^-совпадения, значит,Х ^ имеет длину h-периода не более s, но не является периодической, таккак построена как апериодическая последовательность s-грамм u и w.Пусть Y - аддитивная полугруппа. Функцию h : X * ^ Y назовем аддитивной,если для любого слова w длины s > 1 из того, что w = uu', где u G X^, u' G X r,€ + r = s, следует, чтоhs(w) = h^(u) + hr (u').Пример 1 (аддитивные функции).1) Длина слова u, то есть функция L : X * ^ N, определенная для u = x 1x2 ... X GG X . формулой L(u) = €.2) Частота символа а в слове u, где a G X ; обозначим эту функцию ma(u).3) Пусть X = {a 1, a2, . . . , ak}, m,(u) -частота символа a в слове u, i = 1 ,..., k.Функцией маркировки слов назовем функцию m : X * ^ Nk, определеннуюформулой m(u) = (m1(u ),... ,mk(u)).4) Пусть X = N0 или X = GF(k), где k - простое, и u = x 1x2 ... x G X^. Функциейвеса слов из X * назовем функцию wt : X * ^ N0, определенную формулойwt(u) = wt(x1) + ... + wt(x^), где wt(xj) = x для любого x G X .Теорема 1. Пусть X ^ = {ж0,ж1, . . . } -чисто периодическая последовательностьс длиной периода t и длиной h-периода th, где h - аддитивная функция. Тогда thделит t.Следствие 1. Пусть t - простое, тогда th = 1 , если h(x0) = ... = h(xt-1), и th = tв остальных случаях.Обозначим через ЛРПтах-п линейную рекуррентную последовательность порядкап над произвольным полем P порядка k с максимальной длиной периода, то естьt = kn - 1.Теорема 2. Для ЛРПтах-n в каждом из следующих случаев th = kn - 1:а) h = ma(u), где а отлично от нуля поля P ;б) h = m(u) ;в) h = wt(u), где P = GF(2) или P = GF(3).Если P = GF(k), где k > 3 - простое, то twt = (kn - 1)/d, где d делит (k - 1)/2.Чисто периодическую рекуррентную последовательность порядка n над множествомX , где |X| = k, называют нормальной рекуррентной последовательностью, еслидлина ее периода равна kn, и обозначают НРП(^п). Генерируются НРП(^п) полноцикловымирегистрами сдвига длины п над множеством X . НРП(2,п) называютпоследовательностями де Брёйна. Обзор свойств НРП(^п) дан в [4].Теорема 3. В любой НРП(2,п) имеются h-совпадения на расстоянии 2n 1 прип > 0 и при всех функциях h из {m0(u), m1(u), m(u), wt(u)}.Следствие 2. Длина h-периода последовательности де Брёйна порядка п равна2r, где r < п, при всех функциях h G {m0(u),m1(u),m(u), wt(u)}.При анализе линейности уравнений гаммообразования, связанных с генераторамигаммы с внешним управлением неравномерным движением, важным свойством являетсяh-периодичность управляющей гаммы.Рассмотрим класс генераторов, включающий генераторы «$-т-шагов» и генераторыс перемежающимся шагом. Пусть X ^ -последовательность над простым полемX = GF(k), управляющая движением информации в линейных регистрах сдвигаЛРС-0, ... , ЛРС-^ - 1) над полем P , которые реализуют линейные подстановкиg0, ... ,gk-1 векторных пространств определенных размерностей. В i-м такте подстановкаg(i) пространства Pn состояний набора ЛРС-0, . . . , ЛРС-^ - 1) определяетсязнаком Xj управляющей гаммы, схемой движения регистров, задаваемой матрицейА = (.(i, j )) над N0 размера k х k (строки матрицы различны), и набором подстановокg = (g0, . . . , gk-1). Пусть в i-м такте состояние всех ЛРС генератора естьy(i) = (У0(i),. .. ,yk-1(i)), где у,-(i) - состояние ЛРС- j , j = 0 ,..., k - 1,i ^ 0. Тогдаy j(i + 1) = g ?Xi,j)(y j(i)).Знак Yj выходной гаммы генератора есть сумма битов, записанных в i-м такте в крайнихячейках всех ЛРС (как в генераторе с перемежающимся шагом).Пусть mj(i, т ) -частота символа j в слове X(j;T) и G(i, т ) = g(i) "g(i+1) .. .^ (i+ т-1).Тогдас ( ; , т ) = (g0° (j'T ),...,»k --11(iT)).где Zj(i,T) = m0(i,T) .(0, j ) + ... + mk-1 (i,T) .(k - 1,j) -суммарная продвижкаЛРС-j при управляющем слове X(j)T ) ,j = 0 ,...,k - 1. Заметим, что G(i,T) и G(€, т )суть одинаковые линейные подстановки пространства Pn, если одинаковы наборывеличин (z0(i,T) , . . . , zk-1 (i,T)) и (z0 (€, т ) , . . . , zk-1(€, т )). Отсюда если m - функциямаркировки слов и X(j;T) есть m-период управляющей гаммы, то наборы величин(z0(i + гт, т ) , . . . , zk-1(i + гт, т )) одинаковы при любом r = 0 ,1,. .. Следовательно,если длина m-периода неизвестной чисто m-периодической управляющей последовательностиравна т , то линейные подстановки G(i + гт, т ) однозначно определены принекотором i G {0 ,... , т - 1} и при r = 0 ,1 ,..., поэтому знаки Yj+rT гаммы линейновыражаются через знаки состояния y(i) генератора.Выводы1) Для криптографических приложений важным свойством является h-периодичностьпоследовательностей при различных функциях h.2) Наилучшие криптографические свойства ряда генераторов с неравномернымдвижением, связанные с нелинейностью уравнений гаммообразования, достигаютсяв схемах с управляющей гаммой, имеющей большие длины периода иm-периода, где m - функция маркировки слов.

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