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

Так, например, алгоритм поточного шифрования Trivium [67] по­строен с использованием трех нелинейных регистров сдвига, суммарнаядлина которых составляет 288 бит. Авторы полагают, что после достаточ­но большого количества итераций свойства алгоритма совпадают со свой­ствами случайной перестановки, и потому все возможные длины цикловдо 2 2 8 8 являются равновозможными.

В таком случае вероятность попада­ния в цикл длины менее 2 8 0 при случайном начальном состоянии равнаничтожному значению 2~ 2 0 8 .В алгоритме Grain [35] используются два регистра: по одному с ли­нейными и нелинейными обратными связями. Выход линейного регистрасдвига «подмешивается» к значению булевой функции д, используемой дляопределения очередного символа нелинейного регистра (см. рис.

1.5).Регистр сдвига 1••i^ii^^$-1Регистр сдвига 211 1^ ^ ^ \ > ^ " " ^ ^Рис. 1.5. Структура поточного шифра Grain (/ — линейная функция об­ратной связи, р — нелинейная функция обратной связи, h —нелинейная фильтрующая функция выхода)-521.2.7. Г Е Н Е Р А Т О Р Ы НА ОСНОВЕ К Л Е Т О Ч Н Ы Х АВТОМАТОВГенераторы на основе клеточных автоматов редко выделяются в от­дельный класс. Тем не менее, такая классификация в данном случае оправ­дана, поскольку дальнейшие исследования будут посвящены применениюклеточных автоматов при построении высокоскоростных генераторов псев­дослучайных последовательностей с хорошими статистическими свойства­ми.Понятие клеточного автомата было введено Джоном фон Нейма­ном [78] для описания самоорганизующихся и самовоспроизводящихся си­стем. Наибольший объем исследований в области клеточных автоматовпришелся на 1980-е гг.

[24,66,81,82]; при этом отметим, что значительныйвклад в систематическое исследование клеточных автоматов внес СтефанВольфрам.В этом разделе мы ограничимся кратким описанием генераторов псев­дослучайных последовательностей на основе одномерных клеточных авто­матов. Свойства клеточных автоматов будут подробно рассмотрены в гла­ве 2, а генераторы на их основе — в главе 3.Стоит отметить, что из-за низкой эффективности программной реали­зации генераторы на основе клеточных автоматов к настоящему моментуне получили широкого распространения и, насколько известно автору, ис­пользуются в качестве генераторов псевдослучайных последовательностейтолько в математическом пакете Wolfram Mathematica [69].1.2.7.1.

Г Е Н Е Р А Т О Р Ы НА О С Н О В Е О Д Н О М Е Р Н Ы Х К Л Е Т О Ч Н Ы Х АВТОМА­ТОВПрименение одномерных клеточных автоматов в качестве генерато­ров псевдослучайных последовательностей (точнее, в качестве генераторовгаммы поточного шифрования) было предложено Стефаном Вольфрамомв 1986 г. [82] (см. также [40]).РассматриваемыйляетсобойнаборВольфрамомизqклеточныйциклическиавтоматсоединенныхячеекпредстав­памятиs = [mo, m i , . .

. ,m g _i], каждая из которых может принимать значенияиз двоичного множества Z2. В процессе функционирования клеточного-53автомата все ячейки меняют свой значение синхронно и одновременно.Значение г-ой ячейки на (£+1)-ом такте работы определяется зависимостьютц+i = rrii-ij Ф rni>t © mi+1j0 mi)tmi+lit,0 < г < q, t = О,1,...,где вычисления индексов осуществляются по модулю q. Вектором инициа­лизации генератора является набор so = [тпо.о, "2i,o5 • • •, i^q-ifi] начальныхзначений ячеек памяти регистра.Для формирования выходной последовательности а генератора ис­пользуется значение одной из ячеек клеточного автомата (с фиксирован­ным индексом к):Oit+i = mk,t+i,t = 0,1,Таким образом, генератор вырабатывает выходную последовательность соскоростью 1 бит за такт работы.Вольфрам рассматривал клеточные автоматы ^различными значени­ями длины набора и, основываясь на эмпирических данных, пришел к вы­воду, что при больших значениях q подавляющее число состояний автоматалежит на едином большом цикле.К достоинствам генераторов псевдослучайных чисел на основе од­номерных клеточных автоматов можно отнести хорошие статистическиесвойства и эффективную аппаратную реализацию.

Тем не менее, такие ге­нераторы обладают и рядом существенных недостатков, таких как:- недостаточная изученность свойств клеточных автоматов;- неэффективная программная реализация.1.3.М Е Т О Д Ы УЛУЧШЕНИЯ СВОЙСТВ ГЕНЕРАТОРОВ ПСЕВ­ДОСЛУЧАЙНЫХЧИСЕЛОдной из важных задач при построении генераторов псевдослучайныхпоследовательностей является обеспечение высокого качества вырабатыва­емой последовательности. Особый интерес представляют методы улучше­ния качества выходных последовательностей уже имеющихся генераторов,поскольку это позволяет основываться на ранее полученных результатах.В этой области можно выделить два основных подхода:-54- использование фильтрующих функций, осуществляющих преобразо­вание выходной последовательности единственного генератора;- построение комбинированных генераторов, объединяющих в себенесколько элементарных генераторов.Поскольку существует достаточно много различных методов улучшениякачества псевдослучайных последовательностей, мы ограничимся рассмот­рением наиболее распространенных.1.3.1.

П Р И М Е Н Е Н И Е Ф И Л Ь Т Р У Ю Щ Е Й ФУНКЦИИПрименение фильтрующих функций уже затрагивалось при рассмот­рении вихря Мерсенна (см. раздел 1.2.6.5), в котором для улучшениясвойств выходной последовательности использовалась перемешивающаяматрица Т.Пусть последовательность а = {at G С1а} вырабатывается некоторымгенератором псевдослучайных чисел. Тогда последовательностьр = {pt = f{at) е ар]получается из последовательности а при помощи применения фильтрую­щей функции / : О а —>• О/зОдним из распространенных вариантов фильтрующей функции явля­ется «отбрасывание» младших или старших битов членов выходной по­следовательности генератора. Функция / : Ъ\ —> 1/2) «отбрасывающая» Iмладших и h старших битов (q — I — h = г) может быть описана в виде.f(a) = (amod2q-h- amod2*)/2*.1.3.1.1.

Л И Н Е Й Н Ы Е Р Е Г И С Т Р Ы СДВИГА С Ф И Л Ь Т Р У Ю Щ Е Й ФУНКЦИЕЙФильтрующие функции часто входят в состав генераторов псевдослу­чайных чисел на основе регистров сдвига с линейными обратными связя­ми [58,59]. В частности, используется вариант генератора, приведенный нарис. 1.6.Вкачестве выходнойсматриваетсяпоследовательностипоследовательностьегорегистравнутреннихсдвига рас­состояний s=-55a,,1st4St-2St-lj',,i,LSt-3JrJMJr"©Р и с .

1.6. Генератор на основе PC Л ОС с фильтрующей функцией{(si_i,s t _2,... iSt-ь)G F^}. Выходная последовательностьгенератораформируется путем применения нелинейной булевой функции/ : F^ —> ^ 2 :at =f(st-l,St-2,---,St-L).Максимальный период выходной последовательности РСЛОС с ф и л ь т р у ­ющей функцией равен периоду самого регистра и составляет Ттах — 2L — 1Нелинейная фильтрующая функция позволяет избавиться от г л а в н о г онедостатка регистров сдвига с линейными обратными связями — н и з к о йлинейной сложности выходной последовательности: в [42] показано, ч т олинейная сложность для таких генераторов ограничена сверху з н а ч е н и е мi=lгде L — длина регистра, d — deg(f) — степень многочлена /.

Более т о г о ,доля фильтрующих булевых функций степени d, для которых д о с т и г а е т с ямаксимально возможное значение линейной сложности выходной п о с л е д о ­вательности £тах, составляет приблизительноexp(-Cmax/(LLl L• 2 )) > e~ '^1,т. е. при больших значениях длины регистра верхняя граница д о с т и г а е т с ядля подавляющего большинства функций / [59].-561.3.2. К О М Б И Н А Ц И Я П О С Л Е Д О В А Т Е Л Ь Н О С Т Е ЙПусть а^\ а^2\ . .

. , а^ — выходные последовательности некоторых ге­нераторов псевдослучайных чисел. Тогда результирующая последователь­ность /3 = /?i,/?25 • • • может быть получена из исходных путем примененияперемешивающей функции /:где щ' — £-ый член последовательности б№. Основным недостатком такогоподхода является очевидное снижение скорости выработки псевдослучай­ной последовательности при программной реализации в к раз по сравнениюс быстродействием исходных генераторов.Если каждая исходная последовательность eft' обладает линейнойсложностью Ci, а функция / представлена в алгебраической нормальнойформе, то линейная сложность результирующей последовательности со­ставляетгде все вычисления производятся в Z [59].1.3.2.1. К О М Б И Н А Ц И Я П О С Л Е Д О В А Т Е Л Ь Н О С Т Е Й П Р И ПОМОЩИ Б И Н А Р ­НОЙ ОПЕРАЦИИВ составном генераторе с бинарной комбинирующей операцией исполь­зуются две элементарные последовательности а^и с№ для выработкирезультирующей последовательности /3 при помощи следующего соотно­шения:pt = a(?)®a?\* = 1,2,...,где в качестве операции 0 может использоваться +, —, • (умножение), ф(«исключающее или»).Составные генераторы с бинарной комбинирующей операцией позво­ляют улучшить статистические свойства выходной последовательности исделать ее менее предсказуемой.Рассмотрим случайную дискретную величину х Е П.

со значениями из-57множества D. = {LOI,LJ2, ... ,OJN}, имеющую распределение вероятностейР=(PUP2,---,PN),где pi = Prja; = uij\. В качестве меры «близости» распределения х к равно­мерному введем расстояниеN5{х) = ]Г1i=\Тогда можно показать [12], что если а^ и а^ —две независимые слу­чайные величины со значениями из О и операция 0 на множестве О за­дается латинским квадратом (что выполняется, если (П, 0 ) образует ква­зигруппу), то5(Р) = д(а{1) 0 а ( 2 ) ) ^ m i n ( % ( 1 ) ) , £(а ( 2 ) )).Кроме того, если последовательности а^периодами Т^и а^строго периодичны си Т^соответственно, то период выходной последователь­ности (3 = с^1) 0 а^составного генератора равен наименьшему общемукратному чисел Т^и Т^Т = ЬСМ(Т ( 1 ) ,Г ( 2 ) )и достигает максимального значения Ттах = Т^ • Т^в случае, когда Т^и Т"(2) взаимнопросты.1.3.2.2.

Г Е Н Е Р А Т О Р Г Е Ф Ф ЕПримером составного генератора, использующего комбинацию после­довательностей, является генератор Геффе [2,4]. В состав генератора вхо­дят (см. рис. 1.7): ,- три двоичных регистра сдвига с линейными обратными связями R\, R2и i?3> каждый из которых является М-генератором (т. е. вырабатываетвыходную последовательность максимально возможного периода);- нелинейная перемешивающая функция F(x, у, z) = xzV yz, принима­ющая значение аргумента х или у в зависимости от входа z.-58X,РСЛОСЯ,\ .а.1ytРСЛОСЯ2^-<LZtРСЛОСЯзРис. 1.7.