Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей, страница 13

Л А В И Н Н Ы Й Э Ф Ф Е К ТПонятие лавинного эффекта было введено Хорстом Фейстелем в1973 г. в работе [25]. Под лавинным эффектом в криптографии понимает­ся такое свойство преобразований (чаще всего блочных шифров или хешфункций), при котором небольшое изменение входных данных приводитк значительному изменению результата. «Хорошим» считается лавинныйэффект, при котором изменение одного бита входа ведет к изменению всреднем половины битов выхода.Исследование лавинного эффекта в клеточных автоматах позволяетпоказать, что при определенном выборе окрестностей такие автоматы об­ладают свойством размножения изменений, и в дальнейшем использоватьэто свойство для построения генераторов псевдослучайных последователь­ностей с контролируемым периодом.Более формально, преобразование ip : {0,1} п —> {0,1} п удовлетворяеткритерию лавинного эффекта, если для всех г £ { 1 , 2 , .

. . , п} выполняетсяравенствогде вг G Щ — двоичный вектор, г-ый элемент которого равен единице, авсе остальные — нулю, ||Ь|| — вес некоторого двоичного вектора 6, © — опе­рация побитового сложения.Для описания характеристик лавинного эффекта рассмотрим два пол­ностью идентичных булевых клеточных автомата С^. . . х Xd,Wr,f)и С(2)= C(Z2,Xiх Х2 х . . . х Xd,Wr,f)= C(Z2,Xiх Х2 хс одинаковымиразмерами d-мерной решетки Х\ х Х2 х . . . х Xj, задающими окрестностьотображениями Wr и локальными функциями связи /.

Для определенно­сти при рассмотрении лавинного эффекта мы будем считать, что линейныеразмеры решетки упорядочены по возрастанию: Xi ^ Х2 ^ . . . ^ Хд (впротивном случае достаточно переобозначить координаты ячеек).Обозначим через т,Г•> , и т,{Xi,X2,...,Xd),t„. w значения ячеек с коорди-{Xi,X2, —,Bd),t^1^-85натами (жх, Х2,.. •, ха) клеточных автоматов С^> и С^ в момент времени tсоответственно.Поскольку автоматы являются идентичными, изначально значения со­ответствующих ячеек первого и второго клеточных автоматов совпадают,т. е.

автоматы находятся в одинаковых начальных состояниях. Внесем еди­ничное изменение в начальное состояние второго клеточного автомата^ 2 ),для чего сменим значение ячейки TTILQ « 6 Z2 В момент временив = 0 напротивоположное:т(2)(0,0,...,0),0 <~л1__т(2)(0,0 > ...,0),0Т. к.

все ячейки одинаковы по своим свойствам, выбор конкретной ячейкине ограничивает общности результатов; тем не менее, использование ячей­ки с нулевыми координатами позволяет упростить запись ряда выражений.После внесения изменений совпадают значения всех ячеек с соответ­ствующими координатами клеточных автоматов С^ и С^2\ кроме одной:mSJ „т 1 п(Xi,X2,...,Xd),0^ mi J „I„, ч п ФФ> Х\ = Х2 — . . . = Xd — 0 .{Xi,X2,...,Xd),01taЛавинный эффект отражает изменения, вызванные во втором клеточ­ном автомате С^2' сменой значения одной ячейки памяти в начальный мо­мент времени. Поскольку в силу свойства локальности классических кле­точных автоматов лавинный эффект проявляется не мгновенно (т.

е. наследующем такте работы), а постепенно, целесообразно изучать его харак­теристики во времени.Оптимальным лавинным эффектом в клеточных автоматах мы будемсчитать такой лавинный эффект, при котором изменения распространя­ются по решетке клеточного автомата равномерно во всех направлениях смаксимально возможной скоростью, и при этом значение каждой ячейкиизменяется с вероятностью | .Для описания лавинного эффекта мы вводим две числовые характе­ристики: интегральную и пространственную.-862.1.4.1. И Н Т Е Г Р А Л Ь Н А Я Х А Р А К Т Е Р И С Т И К А ЛАВИННОГО ЭФФЕКТАИнтегральной характеристикой лавинного эффекта в клеточных ав­томатах будем называть временную зависимость rj(t) отношения числа из­менившихся ячеек к общему количеству ячеек решетки:v(t)=£m(xuX2,...,Xd),t(xi,X2,...,Xd)Ф(xi,X2,-,Xd),tХ\ • Х2 • ..

• • Xdгде сумма ^2 вычисляется как обычное арифметическое сложение по всемвозможным наборам координат (х\,Х2, • • •,ccd),аоперация 0 — как сложе­ние по модулю 2.Утверждение 2. Интегральная характеристика оптимального лавинногоэффекта в классическом d-мерном клеточном автомате с радиусом локаль­ности г имеет вид:{2rt + 1)7(2 • Х1 • ... • Xd),(2rt + 1 ) ^ 7 ( 2 -X2-...-Xd),Vopt(t)(2rt + l ) d " V ( 2 • Xk+11/2,2rt + 1 ^X1<2rt• . . . • Xd),+Xk<2rtXd<2rtХиl^X2,+ 1^(2.2)Xk+U+ 1.Доказательство. По определению оптимального лавинного эффекта изме­нения распространяются по решетке классического клеточного автомата смаксимально возможной скоростью. Это означает, что на£-ом шаге работыкаждая ячейка функционально влияет на все ячейки, удаленные от нее нарасстояние не более rt.Будем рассматривать изменения в заполнении ячеек решетки, которыевызывает смена значения некоторой ячейки т в начальный момент време­ни t = 0.

Обозначим через n(t) количество ячеек, находящихся на рассто­янии не более rt от т и отметим, что величина n(t) ограничена сверхуразмером клеточного автомата. Тогда с учетом отождествления противо--87положных краев решетки имеем:2rt+l(2rt + l ) d ,Хг • (2rt + 1)d - 1n(t) = <ХъXi < 2rt + 1 ^XiX2 • • • Xk • (2rt d-k+ 1) Xk<2rtX1X2^+ 1^X2,X,k+1,Xd <2rt + \• • • Xd,(напомним, что X\ ^ X2 ^ . . . Xd).По определению оптимального лавинного эффекта значение каждойячейки изменяется с вероятностью ^ (т.

е. в среднем изменяется половинавсех ячеек); кроме того, интегральная характеристика лавинного эффектаявляется нормированной по размеру клеточного автомата величиной. Та­ким образом, интегральная характеристика оптимального лавинного эф­фекта может быть записана в видеVopt(t)n(t)2 • XiX2• • • Xd•что при подстановке значения n(t) и дает выражение 2.2.Для частного случая двумерных булевых клеточных автоматов с раз­мерами решетки X х Y (X ^ Y) и радиусом локальности г — 1 выраже­ние (2.2) может быть записано как{2t+l)2/{2-X-Y),VoPt{t) = < ( 2 i + l ) / ( 2 - X ) ,1/2,2£ + 1 < У ,Y <2t +X<2t+ 1.l^X,(2.3)-882.1.4.2. П Р О С Т Р А Н С Т В Е Н Н А Я Х А Р А К Т Е Р И С Т И К А Л А В И Н Н О Г О ЭФФЕК­ТАПоказателем, отражающим линейную скорость распространения изме­нений по решетке клеточного автомата, является пространственная харак­теристика лавинного эффекта /i(£).

Эта характеристика равна отношениюмаксимального расстояния от' начальной ячейки, на котором проявляетсялавинный эффект на t-ом такте работы (т. е. существуют ячейки автома­тов С^1' и С' 2 ' с одинаковыми координатами, но разными значениями), кмаксимально возможному расстоянию между двумя ячейками (которое всоответствии с (2.1) равно 6тах = \{Хд — 1) /2]):(сЛа\) {(mS.*т- ) .

* 0 m(*L....^),t) •6(mm...,o),rnixuX2_Xd))}Г № - 1 ) /21~'где максимум берется по всем возможным векторам (х\,Х2, •.. ,Xd), Ф ~операция сложения по модулю 2, а остальные действия выполняются какобычно (над полем действительных чисел Ж).Утверждение 3. Пространственная характеристика оптимального лавин­ного эффекта описывается соотношением,opl(t)Jw^nv[l,*<№-!)/*].rt>\{Xd-l)/2\..(2 4)Доказательство.

Поскольку по определению оптимального лавинного эф­фекта изменения распространяются по решетке классического клеточногоавтомата с максимально возможной скоростью, на t-ou шаге работы каж­дая ячейка функционально влияет на все ячейки, удаленные от нее нарасстояние не более rt.Будем рассматривать изменения в заполнении ячеек решетки, кото­рые вызывает смена значения некоторой ячейки т в начальный моментвремени t = 0.

Обозначим через p(t) максимальное расстояние от ячейкит, на котором проявляются изменения на t-ом такте работы и отметим,что значение p(t) ограничено сверху величиной 5тах. Тогда с учетом отож--89дествления противоположных краев решетки имеем:,, NI ft,Tt <OmaxiI VmaxiТЪ ^Omax-P{t) = \Пространственная характеристика лавинного эффекта нормируетсяпо 6тах, поэтомуp(t)Hopt\t) — 7Отах)что при подстановке значений p(t) и 5тах дает выражение 2.4.•Для частного случая двумерных клеточных автоматов с размерамирешетки X х Y (X ^ Y) и радиусом локальности г = 1 пространственнаяхарактеристика лавинного эффекта принимает вид**Ю-М»*' *<Г<*-Ч/*1.\lt>\(X-l)/2-\.,( 5)Как видно из (2.4), пространственная характеристика оптимальноголавинного эффекта не зависит от размерности клеточного автомата и пол­ностью определяется двумя параметрами: радиусом локальности г и наи­большим (по всем значениям Х\, Хч,.

•., Х^) линейным размером решетки.2.1.4.3. З А В И С И М О С Т Ь Х А Р А К Т Е Р И С Т И К Л А В И Н Н О Г О ЭФФЕКТАОТВЫБОРА ОКРЕСТНОСТИХарактеристики лавинного эффекта в клеточных автоматах зависятот структуры связей между ячейками решетки, т. е. от выбора окрестностиЧг и локальной функции связи / (напомним, что ячейки из окрестностиWr соответствуют существенным аргументам функции / ) .На рис. 2.8 и 2.9 приведены графики .характеристик лавинного эф­фекта в двумерных булевых клеточных автоматах С{Ъ2,Х х Y,4/i,/) сразличными типами окрестности, указанными на рис.

2.3 (стр. 77).Из графиков (см. рис. 2.8, 2.9) видно, что характеристики лавинно­го эффекта приближаются к оптимальным по мере увеличения мощностиокрестности "Ч/i, причем различия между характеристиками лавинного эф--90-SO102030405060Номер такта t708090100Р и с . 2.8. Интегральная характеристика лавинного эффекта в двумерныхбулевых клеточных автоматах C(Z2, 37 х 11, Ч^, /)оптимальный лавинный эффектполная окрестностьквазиполная окрестностьнеполная окрестность, |"4^i | = 5неполная окрестность, l^i] = 42030405060Номер такта t708090100Р и с . 2.9.

Пространственная характеристика лавинного эффекта в дву­мерных булевых клеточных автоматах C(Z2,37 х 11,^i, /)-91фекта в клеточных автоматах с квазиполными и полными окрестностямиявляется несущественным.Для каждого типа окрестности графики отражают усреднение экс­периментальных результатов по 1000 различных клеточных автоматов сразмерами решетки 37 х 11 и радиусом локальности 1. В каждом экспе­рименте вектор функции / выбирался случайным образом из множестваравновесных булевых функций с заданным количеством аргументов.Графики характеристик оптимального лавинного эффекта отражаюттеоретические зависимости (2.3) и (2.5).Следует отметить, что проявления лавинного эффекта в конкретномклеточном автомате существенно зависит не только от выбора окрестностии функции локальной связи, но и от начального состояния автомата, и внекоторых случаях лавинный эффект от изменения одиночной ячейки вконкретном клеточном автомате может быть выражен более слабо или непроявиться вовсе.

Именно этой особенностью объясняется тот факт, чтона графиках для клеточных автоматов с неполными окрестностями харак­теристики лавинного эффекта не достигают ожидаемого максимальногозначения ( | для интегральной характеристики и 1 для пространственной).Таким образом, лавинный эффект должен рассматриваться как неко­торый обобщенный показатель, отражающий характерные черты целогокласса автоматов с одинаковой структурой связей между ячейками.2.1.5. С В О Й С Т В А П Е Р И О Д И Ч Н О С Т ИПоследовательность внутренних состояний клеточных автоматов, каки любых других автономных конечных автоматов, обладает некоторым пе­риодом.