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

К Л А С С И Ч Е С К И Й Г Е Н Е Р А Т О Р Ф И Б О Н А Ч Ч ИКлассический генератор Фибоначчи (см. [6]) является генераторомФибоначчи с параметрами F(2,1,+)и описывается соотношениемat = {a.t-i + oct-2) mod N,t = 1,2,Очевидно, что выходная последовательность такого генератора при на­чальных значениях a_i = 0 и ао = 1 совпадает с последовательностьюФибоначчи, все члены которой взяты по модулю N (этим и обусловленоназвание генератора).В отличие от конгруэнтных генераторов, период выходной последова­тельности классического генератора Фибоначчи обычно превосходит вели­чину модуля N. Тем не менее, такой генератор обладает плохими стати­стическими свойствами.-391.2.5.2. А Д Д И Т И В Н Ы Е Г Е Н Е Р А Т О Р Ы Ф И Б О Н А Ч Ч ИАддитивный генератор Фибоначчи F(r, s, + ) описывается соотноше­ниемat = {oit-r + oct-а) mod N,£ = 1,2,Такой генератор является чрезвычайно быстрым за счет использованияединственной операции сложения, а также при правильном выборе пара­метров способен обеспечить относительно хорошие статистические свой­ства выходной последовательности [49].Один из вариантов аддитивного генератора Фибоначчи был предло­жен Д ж .

Митчеллом и Д. Муром в 1958 г. (работа не опубликована, см. [6]).Функционирование генератора Митчелла и Мура описывается рекуррептойoct = {at-55+ at-24)modN,£ = 1,2,...,(1.5)где модуль Л7" —четное число, а ао, а - ъ . • •, а_54 ~ произвольные целые невсе четные числа. Задержки г = 55 и s = 24 выбраны таким образом, чтобыобеспечить период младшего бита членов последовательности се, равный2 5 5 - 1.МаксимальныйТщах = 2q~l(217JP(17,— 1),периодвыходнойтакжедостигаетсяпоследовательности,длягенераторовравныйФибоначчи5, + ) и F ( 1 7 , 5 , —), построенных по модулю 2q [12].1.2.5.3.

М У Л Ь Т И П Л И К А Т И В Н Ы Е Г Е Н Е Р А Т О Р Ы Ф И Б О Н А Ч Ч ИВыходные последовательности мультипликативных генераторов Фи­боначчи F(r, s, •) описываются рекуррентным соотношениемat = (at-r• oct-s) mod N,£=1,2,Один из вариантов мультипликативного генератора Фибоначчи былразработан Д ж . Марсалья [48], предложившим заменить в выражении (1.5)операцию сложения умножением:at = (af_55 • oet-24) mod JV,£=1,2,...,агде модуль N кратен 4, а начальные значения ао, с*-ъ • • • •> -54 нечетны и-40сравнимы с 1 по модулю 4.Мультипликативные генераторы Фибоначчи по своим статистическимсвойствам превосходят аддитивный вариант, однако в ряде случаев усту­пают ему в быстродействии, что обусловлено более медленной реализациейумножения по сравнению со сложением в некоторых архитектурах ЭВМ.1.2.5.4.

Г Е Н Е Р А Т О Р Ы Ф И Б О Н А Ч Ч И С О П Е Р А Ц И Е Й « И С К Л Ю Ч А Ю Щ Е Еили»В случае генератора Фибоначчи типа F(r, s, ф) выходная последова­тельность а представляет собой последовательность двоичных д-разрядных векторов сх\, сс2,.. • € Z | и описывается выражениема* = ( а 4 _ г 0 а * _ в ) ,t = 1,2,...,(1.6)где операция ф обозначает покомпонентное сложение двоичных векторовпо модулю 2 («исключающее или»).Генераторы такого типа являются достаточно быстрыми (быстродей­ствие определяется разрядностью машинного слова ЭВМ). Как отмечаетсяв [51], выходные последовательности генераторов Фибоначчи F(r, s, ф) об­ладают удовлетворительными статистическими свойствами (успешно про­ходят набор тестов DIEHARD) только при больших значениях задержкиг > 600; при меньших значениях задержки использовать генераторы тако­го типа не рекомендуется.

Кроме того, они обладают и другими существен­ными недостатками (более подробно см. раздел 1.2.6.3).1.2.6. Г Е Н Е Р А Т О Р Ы НА О С Н О В Е Р Е Г И С Т Р О В СДВИГА1.2.6.1. Р Е Г И С Т Р Ы СДВИГА С Л И Н Е Й Н Ы М И О Б Р А Т Н Ы М И С В Я З Я М И НАДП Р О И З В О Л Ь Н Ы М К О Н Е Ч Н Ы М ПОЛЕМРегистры сдвига с линейными обратными связями (РСЛОС, linearfeedback shift registers, LFSR), также часто называемые линейными ре­гистрами сдвига (ЛPC), нашли широкое применение в построении генера­торов псевдослучайных последовательностей [10,14,15,59].Пусть a i , .

. . , ах, — элементы конечного поля ¥q. Тогда рекуррентная-41последовательность L-ro порядка, задаваемая соотношениемat = a\OLt-\ + a2at-2 + • • • + aLat-L,t = 1 , 2 , aL Ф 0,(1.7)над полем Fq может быть получена при помощи регистра сдвига длины Lс линейными обратными связями.Регистр сдвига с линейными обратными связями включает в себя дваосновных компонента (см. рис.

1.3):- последовательно соединенный набор из L ячеек памяти, каждая изкоторых может хранить элемент поля ¥q\- линейные обратные связи, причем если коэффициент обратной связиаг- = 0, то съем с г'-ой ячейки не осуществляется.В качестве выхода регистра используется значение ячейки с номером L.Lat«мO-t-2Щ-ъO-t-La-t-i<'©Рис. 1.3. Регистр сдвига с линейными обратными связямиХарактеристики линейных регистров сдвига определяются структу­рой обратных связей, т. е. набором ячеек, с которых осуществляется съемзначений, и коэффициентами обратной связи а\, а2,..., а^. Исследованиехарактеристик РСЛОС обычно проводят с использованием методов тео­рии полей (и, в частности, теории рекуррент над конечными полями). Дляэтого каждому регистру (точнее, рекуррентной последовательности (1.7))сопоставляется характеристический многочлен над полем ¥q:f(x) =xL - aixL~l - а2ж„L-2 -aL G Fq[x],(1.8)где a i , .

. . , az, — коэффициенты обратной связи (см. рис. 1.3). Максималь­но возможный период выходной последовательности линейного регистраLсдвига составляет Ттах = q — 1 и достигается в том и только том случае,когда характеристический многочлен (1.8), является примитивным над по--42лем F g .Последовательность максимальной длины, порождаемую регистромсдвига с линейными обратными связями, принято также называть М-последовательностью, а соответствующий регистр — генератором М-последовательности.Диаграмма состояний генератора М-последовательности, описываю­щая переходы между состояниями РСЛОС, содержит два цикла: первыйцикл включает единственное состояние, соответствующее нулевому запол­нению ячеек памяти, а второй — все остальные возможные состояния.

От­сюда следует, что для генерации выходной последовательности в качественачального заполнения ao,o;_i,... ,a-L+i ячеек памяти регистра сдвигаможно выбирать любой набор значений, кроме нулевого.1.2.6.2. Р Е Г И С Т Р Ы СДВИГА С Л И Н Е Й Н Ы М И О Б Р А Т Н Ы М И С В Я З Я М И НАДПОЛЕМ F 2Наибольшее распространение в 50-80-х гг.

прошлого века получилилинейные регистры сдвига над полем F 2 (также называемые двоичнымиРСЛОС), то есть регистры, в которых аг, a f £ F 2 . В качестве операции сло­жения в двоичных РСЛОС используется «исключающее или» (сложениепо модулю 2), а в качестве умножения — логическое «и». Таким образом,выражение 1.7 для двоичных регистров сдвига с линейными обратнымисвязями имеет видat = (aiat-i + a2at-2 + . .

. + aL-iott-L+i + аЬ-ь) mod 2,£ = 1,2,Максимально возможный период выходной последовательности двоично­Lго РСЛОС составляет Ттах = 2 — 1. При этом, поскольку все операциипроводятся в поле F 2 , характеристический многочлен для рекуррентногосоотношения (1.7) немного упрощается:LLlL2f(x) = x + aiX ~ + a2x ~+ . . . + aL-ix +le¥2[x],где коэффициенты аг-, 1 ^ i ^ L — 1, могут принимать значение либо 1,либо 0.Одним из основных достоинств, обеспечивших широкое использование-43двоичных линейных регистров сдвига, является существование примитив­ных трехчленов вида/О) =xL + akxL~k + 1над полем F2 (правда, не для всех значений L), что позволяет строить быст­рые и легкие в реализации регистры максимального периода всего с двумясъемами: для аппаратной реализации такого двоичного регистра с перио­дом 2 — 1 необходимо, очевидно, L триггеров и один элемент сложения помодулю 2.В табл.

1 приведены примитивные многочлены с наименьшим числомслагаемых для некоторых часто используемых значений длины регистраL (таблица составлена на основании [7,80]). Следует отметить, что еслимногочлен f(x) = xL -Ь a\xL~l + a2xL~2 + . . . + 1 является примитивнымнад F2, то и двойственный ему многочлен f*(x) = 1 + а\х + а2х2 + . . . + xLтакже является примитивным над F2, поэтому двойственные многочленыв таблице не приводятся.Таблица 1.Некоторые примитивные многочлены степени L над F 2Степень LПримитивныймногочлен789X +X +18432X +X +X +X +1151617X15 + X + 1Ж16 + ХЪ + X3 + х2 + 13X17 + X + 1313233х31 + х3 + 11532ХЪ2 + X + X + X + х+ ж1 + 1474849X47 + х + 172+ Ж + X5 + X4 + я + х1 + 15Z 49 + X6 + Ж + X4 + 163646571хд + х4 + 116Ж33 + Ж + X4 + X15X48ж 63 + ж1 + 1ж 64 + ж4 + х3 + я 1 + 1ж 65 + ж4 + х3 + ж1 + 1-44Основным недостатком регистров сдвига с линейными обратными свя­зями, препятствующим их использованию в криптографических приложе­ниях, является низкая линейная сложность вырабатываемой ими выходнойпоследовательности.

Линейной сложностью последовательности а называ­ется число С(а), определяемое следующим образом:- если а = 0,0,..., т.е. все члены последовательности нулевые, то£(&) = 0;- если последовательности а не порождается никаким РСЛОС (такоевозможно, например, для бесконечных апериодических последователь­ностей), то £>{а) = со;- во всех остальных случаях линейная сложность последовательности£{&) равна минимально возможной длине РСЛОС, порождающего этупоследовательность.Следует отметить, что любая конечная последовательность порожда­ется каким-либо регистром сдвига с линейными обратными связями (дляэтого достаточно положить длину регистра равной длине последователь­ности и использовать члены последовательности в качестве начального за­полнения ячеек регистра), и, таким образом, имеет конечную линейнуюсложность.

С другой стороны, если последовательность а порождена РС­ЛОС длины L, то линейная сложность такой последовательности не пре­восходит длины регистра: С(а) ^ L.В 1968 г. Элвин Берлекэмп разработал эффективный алгоритм длянахождения минимального многочлена линейной рекуррентной последова­тельности в качестве элемента алгоритма декодирования БЧХ-кодов [1,31].Годом позже Джеймс Мэсси адаптировал [53] алгоритм Берлекэмпа и пред­ложил использовать его для нахождения минимального линейного реги­стра сдвига, порождающего заданную последовательность а длины п вкачестве п первых выходных значений РСЛОС. Указанный алгоритм, по­лучивший название алгоритма Берлекэмпа-Мэсси, может использоватьсяне только для двоичных регистров, но и для произвольных.регистров надполем F g . Следует отметить, что если линейная сложность некоторой по­следовательности равна С{а) = L (т. е.