Содержание к диссертации
Введение
1. Обзор методов генерации псевдослучайных последовательностей 19
1.1. Общие сведения 19
1.1.1. Случайные последовательности и их свойства 19
1.1.2. Подходы к получению равномерно распределенных случайных последовательностей 21
1.2. Генераторы псевдослучайных последовательностей 22
1.2.1. Формальное определение генератора псевдослучайных последовательностей 22
1.2.2. Классификация генераторов псевдослучайных последовательностей 25
1.2.3. Линейный конгруэнтный метод 26
1.2.4. Нелинейные конгруэнтные методы 32
1.2.4.1. Метод «середины квадрата» 32
1.2.4.2. Метод умножения с переносом 33
1.2.4.3. Квадратичный конгруэнтный метод 34
1.2.4.4. Инверсивный (обратный) конгруэнтный метод 36
1.2.5. Генераторы Фибоначчи 37
1.2.5.1. Классический генератор Фибоначчи 38
1.2.5.2. Аддитивные генераторы Фибоначчи 39
1.2.5.3. Мультипликативные генераторы Фибоначчи 39
1.2.5.4. Генераторы Фибоначчи с операцией «исключающее или» . 40
1.2.6. Генераторы на основе регистров сдвига 40
1.2.6.1. Регистры сдвига с линейными обратными связями над произвольным конечным полем 40
1.2.6.2. Регистры сдвига с линейными обратными связями над полем F2 42
1.2.6.3. Обобщенные регистры сдвига 45
1.2.6.4. Обобщенные регистры сдвига с закручиванием 46
1.2.6.5. Вихрь Мерсенна 47
1.2.6.6. Регистры сдвига с нелинейными обратными связями . 50
1.2.7. Генераторы на основе клеточных автоматов 52
1.2.7.1. Генераторы на основе одномерных клеточных автоматов . 52
1.3. Методы улучшения свойств генераторов псевдослучайных чисел 53
1.3.1. Применение фильтрующей функции 54
1.3.1.1. Линейные регистры сдвига с фильтрующей функцией . 54
1.3.2. Комбинация последовательностей 56
1.3.2.1. Комбинация последовательностей при помощи бинарной операции 56
1.3.2.2. Генератор Геффе 57
1.3.3. Прореживание последовательностей 59
1.3.3.1. Схема Ниффелера 59
1.3.3.2. Сжимающий генератор 60
1.4. О криптографически качественных генераторах псевдослучайных последовательностей 61
1.5. Выводы 62
2. Исследование свойств клеточных автоматов 68
2.1. Классические клеточные автоматы 68
2.1.1. Основные понятия и определения 68
2.1.1.1. Одномерные булевы клеточные автоматы 74
2.1.1.2. Двумерные булевы клеточные автоматы 75
2.1.2. Обзор имеющихся результатов для классических одномерных булевых клеточных автоматов 77
2.1.3. Локальная функция связи и равновероятность значений ячеек решетки 79
2.1.4. Лавинный эффект 84
2.1.4.1. Интегральная характеристика лавинного эффекта 86
2.1.4.2. Пространственная характеристика лавинного эффекта . 88
2.1.4.3. Зависимость характеристик лавинного эффекта от выбора окрестности 89
2.1.5. Свойства периодичности 91
2.1.5.1. Временная периодичность клеточных автоматов 92
2.1.5.2. Пространственная периодичность клеточных автоматов . 93
2.1.5.3. Иные проявления периодичности 96
2.2. Неоднородные клеточные автоматы 97
2.2.1. Основные понятия и определения 97
2.2.2. Локальная функция связи и равновероятность заполнения набора ячеек памяти 99
2.2.3. Лавинный эффект 103
2.2.3.1. Интегральная характеристика лавинного эффекта 104
2.2.3.2. Зависимость характеристик лавинного эффекта от выбора окрестности 105
2.2.4. Свойства периодичности 107
2.3. Выводы 108
3. Разработка генераторов псевдослучайных последовательностей 110
3.1. О параметрах клеточных автоматов и эффективности их реализации ПО
3.2. Базовые генераторы 111
3.2.1. Базовый генератор на основе классических клеточных автоматов 112
3.2.1.1. Обоснование выбора размерности решетки и типа окрестности 112
3.2.1.2. Обоснование выбор размера решетки и способа формирования выходной последовательности 113
3.2.1.3. Обоснование выбора локальной функции связи 116
3.2.1.4. Обоснование выбора параметров РСЛОС и периода выходной последовательности 116
3.2.2. Базовый генератор на основе неоднородных клеточных автоматов 118
3.2.2.1. Обоснование выбора окрестности 118
3.2.2.2. Обоснование выбора размера клеточного автомата и способа формирования выходной последовательности 119
3.2.2.3. Обоснование выбора локальной функции связи 120
3.2.2.4. Обоснование выбора параметров РСЛОС и периода выходной последовательности 120
3.2.3. Параметры и начальные значения генератора 121
3.2.4. Алгоритм работы 122
3.2.5. Достоинства и недостатки базовых генераторов 123
3.3. Комбинированные генераторы 124
3.3.1. Параметры и начальные значения генератора 126
3.3.2. Детализированная структура и алгоритм работы 127
3.3.3. Достоинства и недостатки 129
3.4. Выводы 130
4. Исследование статистических свойств выходных последовательностей генераторов 131
4.1. Общие сведения 132
4.1.1. Формальное описание процесса статистического тестирования 134
4.2. Набор статистических тестов NIST 134
4.2.1. Краткое описание статистических тестов 135
4.2.2. Реализация набора статистических тестов NIST 140
4.3. Методика проведения и результаты статистического тестирования 142
4.4. Выводы 147
5. Высокоскоростная аппаратная реализация разработанных генераторов 149
5.1. Общие сведения 149
5.2. Описание реализации 151
5.2.1. Блок Generator — реализация генератора 153
5.3. Характеристики прототипов аппаратной реализации . 154
5.4. Сравнение быстродействия и эффективности разработанной аппаратной реализации и существующих аналогов 156
5.5. Выводы 158
Выводы и заключение 161
Литература 164
- Формальное определение генератора псевдослучайных последовательностей
- Локальная функция связи и равновероятность значений ячеек решетки
- Обоснование выбор размера решетки и способа формирования выходной последовательности
- Методика проведения и результаты статистического тестирования
Введение к работе
Диссертационная работа посвящена разработке новых методов генерации псевдослучайных равномерно распределенных двоичных последовательностей, основанных на использовании клеточных автоматов. К основным достоинствам разработанных методов относятся контролируемый период и хорошие статистические свойства псевдослучайных последовательностей, эффективность и высокое быстродействие аппаратной реализации генераторов.
Актуальность проблемы. Актуальность обусловлена широким применением псевдослучайных последовательностей в имитационном моделировании, методах Монте-Карло, криптографии, программировании и иных областях. Свой вклад в исследование псевдослучайных последовательностей и их генераторов внесли такие известные ученые, как А. Н. Колмогоров, Р. фон Мизес, Дж. фон Нейман, Дж. Марсалья, Д. Кнут, П. Лекваер, С. Вольфрам и др. Вопросы генерации псевдослучайных последовательностей широко обсуждаются на отечественных и зарубежных научных конференциях, таких как MCQMC, The Winter Simulation Conference, Crypto, EuroCrypt, FSE, CHES, Sibecrypt, РусКрипто и т.д.
По мере развития возможностей вычислительной техники разрыв между предъявляемыми требованиями и возможностями существующих генераторов неуклонно возрастает. Проведенный в рамках диссертационного исследования обзор показал, что основной проблемой при разработке генераторов псевдослучайных последовательностей является сочетание высокого быстродействия, эффективности реализации и хороших статистических свойств.
К перспективным направлениям исследований относится разработка новых методов генерации псевдослучайных последовательностей, рассчитанных на реализацию на параллельных вычислительных устройствах, что связано со сменой парадигмы вычислительного процесса и переходом от последовательных вычислений к параллельным. При этом задача генерации случайной последовательности с заданным законом распределения может быть сведена к задаче генерации случайной равномерно распределенной двоичной последовательности.
Цель и задачи. Целью исследований являлась разработка новых генераторов псевдослучайных равномерно распределенных двоичных последовательностей, отвечающих следующим требованиям:
выходные последовательности генераторов на длине периода должны быть статистически неотличимы от случайных равномерно распределенных двоичных последовательностей, что должно подтверждаться успешным прохождением соответствующих специализированных тестов;
период выходных последовательностей генераторов должен превосходить требуемые на практике значения;
- быстродействие и эффективность реализации генераторов на параллель
ных вычислительных устройствах, таких как ПЛИС, должны быть не ни
же, чем у известных аналогов.
При этом исследования были изначально ограничены рассмотрением генераторов, основанных на использовании клеточных автоматов.
Для достижения поставленной цели были решены следующие задачи:
проведен обзор наиболее распространенных генераторов псевдослучайных последовательностей, выявлены их основные достоинства и недостатки, рассмотрены методы улучшения статистических свойств выходных последовательностей;
исследованы свойства клеточных автоматов;
осуществлен синтез структуры и обоснован выбор параметров генераторов псевдослучайных последовательностей на основе клеточных автоматов;
экспериментально исследованы статистические свойства выходных последовательностей разработанных генераторов и подтверждено их соответствие предъявленным требованиям;
разработана аппаратная реализация предложенных генераторов псевдослучайных последовательностей и продемонстрировано ее превосходство над существующими аналогами как по быстродействию, так и по эффективности.
Методы исследований. Теоретические методы исследований включали применение теории конечных автоматов, теории графов, теории вероятности; эмпирические — проведение компьютерного моделирования и применение методов математической статистики для оценки свойств двоичных последовательностей. Для программной реализации был использован язык С# и платформа Microsoft .NET; разработка аппаратной реализации осуществлялась на языке описания цифровых схем VHDL, в качестве аппаратной платформы применялась ПЛИС Altera Cyclone II.
Достоверность результатов. Достоверность теоретических результатов обеспечивается строгим математическим обоснованием утверждений и подкрепляется их согласованностью с данными компьютерного моделирования. Достоверность эмпирических результатов достигается за счет применения стандартных общепринятых инструментов статистического анализа. Корректность аппаратной реализации подтверждается соответствием ее выходных последовательностей и последовательностей, полученных при помощи программной реализации.
Научная новизна. Научная новизна работы заключается в следующем:
- исследовано влияние веса локальной функции связи на распределение зна
чений ячеек памяти клеточных автоматов; сформулирован, доказан и под
твержден экспериментально критерий сохранения равномерности распре
деления;
впервые сформулировано понятие лавинного эффекта для клеточных автоматов; получено теоретическое описание характеристик оптимального лавинного эффекта и эмпирические зависимости характеристик лавинного эффекта от выбора окрестностей ячеек; показано, что клеточные автоматы обладают свойством размножения изменений;
впервые введено и исследовано понятие пространственного периода в классических клеточных автоматах; сформулировано и доказано необходимое условие существования пространственного периода; показано, что нетривиальный пространственный период существенно снижает верхнюю границу периода последовательности внутренних состояний;
разработаны новые методы генерации псевдослучайных последовательностей; на основании свойств клеточных автоматов осуществлен синтез структуры генератора и обоснован выбор его параметров; эмпирически подтверждено соответствие статистических свойств выходных последовательностей современным требованиям.
Практическая ценность. Практическая ценность исследований обусловлена превосходством разработанных генераторов над существующими аналогами как по быстродействию, так и по эффективности реализации. Полученные результаты могут быть использованы в широком спектре различных областей, включая имитационное моделирование, численное решение математических задач методами Монте-Карло, криптографическую защиту информации и др. Внедрение предложенных генераторов в прикладные системы позволит увеличить их быстродействие, а также повысить эффективность за счет хороших статистических свойств и контролируемого периода вырабатываемых псевдослучайных последовательностей.
Положения, выносимые на защиту. На защиту выносятся следующие основные положения и результаты диссертационного исследования:
критерий сохранения равномерности распределения значений ячеек памяти клеточных автоматов;
понятие лавинного эффекта в клеточных автоматах и его характеристики; законы, описывающие характеристики оптимального лавинного эффекта для классических и неоднородных клеточных автоматов;
понятие пространственного периода в классических клеточных автоматах и необходимое условие его существования;
разработанная структура и параметры генераторов псевдослучайных последовательностей на основе клеточных автоматов; обоснование периода выходной последовательности генераторов;
результаты экспериментального исследования статистических свойств выходных последовательностей предложенных генераторов;
разработанная аппаратная реализация генераторов псевдослучайных последовательностей и ее характеристики в сравнении с существующими аналогами.
Публикации. Результаты исследований опубликованы в тринадцати научных работах, из них шесть —в изданиях, рекомендованных ВАК Мин-обрнауки РФ. Все публикации без соавторов.
Апробация. Основные результаты исследований докладывались и обсуждались на 9-ой (2007 г.) и 12-ой (2010 г.) ежегодных международных конференциях РусКрипто (г. Москва), научно-исследовательском семинаре «Защита информации: аспекты теории и вопросы практических приложений» МГТУ им. Н. Э. Баумана (г. Москва, 2010 г.), 9-ой сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография» (г. Тюмень, 2010 г.), всероссийской научно-технической конференции «Безопасные информационные технологии» (г. Москва, 2010 г.), научном семинаре кафедры Криптологии и дискретной математики НИЯУ «МИФИ» (г. Москва, 2011 г.).
Результаты исследований внедрены в учебный процесс кафедры «Информационная безопасность» Московского государственного технического университета им. Н.Э. Баумана и кафедры «Комплексная защита информации» Омского государственного технического университета, а также использованы в научно-производственной деятельности ЗАО «Научно-производственное предприятие «Безопасные информационные технологии».
Структура и объем работы. Рукопись диссертации состоит из введения, пяти глав, заключения и шести приложений. Диссертация изложена на 221 странице (из них основная часть —155 страниц, приложения — 49 страниц), содержит 34 иллюстрации и 18 таблиц. Библиографический список включает 85 наименований.
Формальное определение генератора псевдослучайных последовательностей
В диссертационной работе ставится задача разработать и реализовать (в т. ч. на аппаратном уровне) алгоритмы, реализующие отображение Q и отвечающие следующим требованиям: 1) выходные ПСП должны обладать большим периодом, превосходящим требуемое на практике значение; 2) выходные ПСП должны быть статистически неотличимы от случайных равномерно распределенных двоичных последовательностей, что должно подтверждаться успешным прохождением наборов специализированных статистических тестов. При этом: 1) алгоритмы должны быть основаны на использовании клеточных автоматов; 2) реализация алгоритмов на параллельных вычислительных устройствах (например, аппаратная) должна обладать высоким быстродействием, превосходящем известные аналоги.
Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и шести приложений.
Первая глава посвящена обзору основных существующих алгоритмов генерации псевдослучайных последовательностей с равномерным распределением и анализу их достоинств и недостатков. По результатам аналитического обзора делается вывод, что существующие алгоритмы не в полной мере соответствуют современным требованиям, к которым относятся, в первую очередь, большой период, хорошие статистические свойства и непредсказуемость выходной последовательности, а также высокое быстродействие реализации генератора.
Во второй главе приводится формальное определение классических и неоднородных клеточных автоматов и исследуются различные их свойства, такие как распределение значений ячеек, характеристики лавинного эффекта, пространственная и временная периодичность. В этой главе содержатся основные теоретические результаты диссертации: формулируются и доказываются критерий сохранения равномерного распределения значений ячеек в классических и неоднородных клеточных автоматах, необходимое условие существования пространственного периода в классических клеточных автоматах; исследуются эмпирические зависимости характеристик лавинного эффекта от параметров клеточных автоматов и приводятся их теоретические оценки для оптимального лавинного эффекта. Корректность полученных теоретических результатов подтверждается их согласованностью с данными компьютерного моделирования.
Третья глава посвящена разработке новых методов генерации псевдослучайных последовательностей. В ней приводится структура базовых и комбинированных генераторов псевдослучайных последовательностей, в составе которых могут использоваться как классические, так и неоднородные клеточные автоматы. Выбор параметров клеточных автоматов осуществляется на основании результатов, полученных во второй главе.
В четвертой главе проводится экспериментальное исследование статистических свойств выходных последовательностей разработанных генераторов при помощи специализированного набора статистических тестов Национального института стандартов и технологии США. По результатам тестов выбираются конкретные параметры клеточных автоматов, используемых в структуре генераторов, а также делается заключение о возможности применения разработанных алгоритмов.
Пятая глава посвящена построению высокоскоростной аппаратной реализации разработанных алгоритмов. В частности, описывается структура такой реализации и приводятся ее характеристики для двух комбинированных генераторов, выходные последовательности которых обладают наилучшими статистическими свойствами. Также в этой главе проводится сравнение разработанной аппаратной реализации с современными аналогами и делается вывод о существенном превосходстве предложенных генераторов на основе клеточных автоматов.
В приложениях приводятся дополнительные сведения, включение которых в основной текст диссертации автор счел нецелесообразным.
Локальная функция связи и равновероятность значений ячеек решетки
Отметим, что корректность подобного допущения подтверждается согласованностью теоретических результатов с эмпирическими данными. Если принять допущение 1, то можно сформулировать и доказать критерий сохранения равномерного распределения значений ячеек классического клеточного автомата в следующем виде. Утверждение 1. Равновесность локальной функции связи является необходимым и достаточным условием сохранения равномерного распределения значений ячеек классического клеточного автомата с бесконечным размером решетки. Доказательство. Доказательство проведем по индуктивной схеме. Предположим, что в момент времени t значения ячеек распределены по решетке независимо и равновероятно (Vm : Pv[mt = 1] = Pr[mt = 0] = ). Поскольку по условию решетка имеет бесконечный размер (ХІ — оо, 1 г d), для произвольного подмножества {гп -1\тР \ ... ,т } мощности и 0 ячеек автомата и любого двоичного набора а = [ai,a2,..., au] Є Щ в момент времени t выполняется равенство (такое заполнение соответствует условию утверждения и может быть выбрано, например, в качестве начального). Отсюда следует, что каждый набор Wr(mt) значений ячеек из окрестности т в момент времени t будет встречаться с равной вероятностью На (i -f 1)-ом шаге значение ячейки т определяется зависимостью mt+i = f(Wr(rnt)). Вероятности того, что произвольная ячейка т клеточного автомата принимает единичное или нулевое значение, составляют соответственно (в соответствии с принятым допущением 1 мы рассматриваем значения ячеек как независимые случайные величины). Равномерному распределению значений ячеек клеточного автомата в момент времени i + 1 соответствует равенство Pr[mt+i = 1] = Pr[mi+i = 0], которое, очевидно, достигается тогда и только тогда, когда Таким образом, равновесность локальной функции связи является необходимым и достаточным условием сохранения равномерного распределения значений ячеек классического клеточного автомата. Использование же в качестве ЛФС неравновесных булевых функций будет приводить отклонениям от равномерного распределения, что является нежелательным при использовании клеточных автоматов для генерации псевдослучайных последовательностей. Несмотря на то, что критерий сформулирован для классических клеточных автоматов с решеткой бесконечного размера, на практике он выполняется и для классических клеточных автоматов с достаточно большими Отношение количества единичных значений к общему числу ячеек решетки классического клеточного автомата при различных вариантах нормированного весагио локальной функции связи размерами решетки, что подтверждается эмпирическими данными.
На рис. 2.7 изображены графики временной зависимости отношения количества единичных значений в заполнении решетки клеточного автомата к общему числу ячеек для локальных функций связи с различными нормированными весами WQ. ДЛЯ каждого значения нормированного веса и о данные отражают усреднение экспериментальных результатов по 1000 различных клеточных автоматов с размерами решетки 37 х 11 ячеек, радиусом локальности 1 и полной окрестностью W . В каждом эксперименте вектор значений функции / выбирался случайным образом из множества всех булевых функций заданного веса.
На графиках хорошо видно, что каждому значению нормированного веса WQ соответствует быстрое приближение к некоторому стационарному значению числа единичных ячеек решетки клеточного автомата, причем равенство между количеством единичных и нулевых ячеек достигается только при WQ = , что соответствует равновесным функциям и согласуется с теоретическими результатами.
Понятие лавинного эффекта было введено Хорстом Фейстелем в 1973 г. в работе [25]. Под лавинным эффектом в криптографии понимается такое свойство преобразований (чаще всего блочных шифров или хеш-функций), при котором небольшое изменение входных данных приводит к значительному изменению результата. «Хорошим» считается лавинный эффект, при котором изменение одного бита входа ведет к изменению в среднем половины битов выхода.
Исследование лавинного эффекта в клеточных автоматах позволяет показать, что при определенном выборе окрестностей такие автоматы обладают свойством размножения изменений, и в дальнейшем использовать это свойство для построения генераторов псевдослучайных последовательностей с контролируемым периодом.
Обоснование выбор размера решетки и способа формирования выходной последовательности
Процесс выбора параметров клеточных автоматов является поиском компромисса между эффективностью реализации и обеспечением хороших свойств выходной последовательности.
При аппаратной реализации каждая ячейка клеточного автомата представляется в виде триггера и булевой функции, определяющей его значение на следующем такте работы, причем для каждой ячейки функция реализуется отдельно, что позволяет осуществлять параллельные вычисления. Для задания булевых функций используются таблицы сопоставления набора аргументов и значений функции. Таким образом, объем требуемых ресурсов напрямую зависит от длины вектора значений локальной функции связи, которая, в свою очередь, экспоненциально зависит от числа ее аргументов.
При программной реализации длина вектора не играет существенной роли, поскольку значения ячеек вычисляются последовательно и может использоваться единственная таблица сопоставления. Тем не менее, время вычисления индекса в таблице сопоставления линейно зависит от количества аргументов локальной функции связи, т. е. от мощности окрестности ячейки: чем меньше аргументов, тем быстрее может быть вычислен индекс.
В предлагаемых генераторах на выход клеточного автомата подаются значения некоторого подмножества его ячеек. Увеличение числа.ячеек памяти позволяет повысить быстродействие аппаратной реализации (за счет параллельности вычислений) ценой линейного увеличения объема требуемых ресурсов. При программной реализации-увеличение количества ячеек не оказывает влияния на быстродействие, а возрастание требований к объему памяти является несущественным. Также следует учитывать, что увеличение числа ячеек оказывает негативное влияние на лавинный эффект в клеточных автоматах.
Таким образом, можно сделать вывод, что наиболее эффективной-реализацией обладают клеточные автоматы с локальной функцией связи от небольшого числа аргументов, а количество ячеек в автомате должно определяться заданным быстродействием и требуемыми характеристиками лавинного эффекта.
В структуру базового генератора на основе клеточных автоматов входят (см. рис. 3.1): - двоичный клеточный автомат С; - регистр сдвига с линейными обратными связями R длины 63. Выходная последовательность (3 регистра сдвига прибавляется по мо дулю 2 к значению одной из ячеек клеточного автомата и, таким образом, обеспечивает заданный период последовательности внутренних состояни автомата. «Подмешивание» выхода РСЛОС сдвига к внутреннему состоянию генератора является достаточно распространенным приемом обеспечения заданного периода выходной последовательности и также использовалось, например, авторами поточного шифра Grain [35].
Каждый член выходной последовательности а базового генератора является 256-разрядным двоичным набором (т.е. элементом множестваZ 56) и формируется из значений определенного подмножества ячеек клеточного автомата С.
В базовом генераторе на основе классических клеточных автоматов С имеет вид С( 2,37 х ll,Wi,f), т.е. является двумерным булевым клеточным автоматом с решеткой размера 37 х 11 и квазиполной окрестностью радиуса 1. Для формирования выходной последовательности а генератора используются значения ячеек, лежащих в определенной области решетки.
В качестве основного элемента базового генератора псевдослучайных последовательностей используется двумерный клеточный автомат с квазиполной окрестностью W радиуса г — 1.
Одномерные клеточные автоматы были исследованы Стефаном Вольфрамом (см. разделы 2.1.1.1 и 2.1.2, а также [81-85]), не представляют серьезного практического интереса и потому не рассматриваются. При увеличении размерности решетки мощность окрестности Шг и, соответственно, число аргументов локальной функции связи / растет экспоненциально. Из табл. 4 видно, что длина вектора значений в клеточных автоматах с трехмерной решеткой превосходит 60 000 000 и не подходит для аппаратной реализации, поэтому наибольший интерес представляют двумерные клеточные автоматы.
Значения.количества аргументов и длины вектора значений локальной функции / в двумерных клеточных автоматах в зависимости от радиуса г и типа окрестности также приведены в табл. 4. При г 1 длина вектора значений / превышает 10000000, что делает реализацию клеточного автомата непрактичной.
Как было показано в разделах 2.1.4 и 2.1.5, клеточные автоматы с неполными окрестностями обладают существенными недостатками, такими как слабо выраженный лавинный эффект и повышенная вероятность возникновения пространственных периодов. Свойства же автоматов с квазиполными и полными окрестностями практически не различаются, поэтому в целях повышения эффективности реализации используются квазиполные окрестности W.
Таким образом, использование клеточных автоматов с двумерными решетками ячеек памяти и квазиполными окрестностями "4/ радиуса г = 1 является, на наш взгляд, наиболее предпочтительным.
Методика проведения и результаты статистического тестирования
Объектом исследования является ранг двоичных матриц, образованных непересекающимися подпоследовательностями последовательности є. Тест направлен на выявление линейной зависимости между подпоследовательностями фиксированной длины. Отметим, что он также входит в набор DIEHARD [51].
Длина последовательности є должна быть не менее 38 912 бит. Discrete Fourier Transform (Spectral) Test.
Объектом исследования является спектр последовательности, полученный при помощи дискретного преобразования Фурье. В частности, определяется отклонение числа спектральных компонентов, амплитуда которых превышает 95% барьер, от ожидаемого результата 5%. Целью теста является выявление периодичности (т.е. повторяющихся шаблонов).
Рекомендуется использовать последовательности є длиной не менее 1000 бит. Non-overlapping Template Matching Test.
Объектом исследования является количество повторений определенной фиксированной подпоследовательности (шаблона) в исходной последовательности. Целью теста является выявление генераторов псевдослучайных чисел, порождающих последовательности со слишком часто встречающимися апериодическими шаблонами.
Для поиска шаблона длины т используется скользящее ш-битное окно. Если шаблон не обнаружен, окно перемещается на одну позицию; в противном случае осуществляется сдвиг окна на т позиций. Процедура тестирования осуществляется для каждого апериодического шаблона указанной длины (в реализации тестов NIST шаблоны задаются в текстовых файлах). Таким образом, в результате теста получается набор р-значений — по одному для каждого шаблона (при т = 9 возможно получение до 148 значений, при т = 10 —до 284). Overlapping Template Matching Test. Объектом исследования является количество повторений определенной фиксированной подпоследовательности (шаблона) в исходной последовательности. Целью теста является выявление генераторов псевдослучайных чисел, порождающих последовательности со слишком часто встречающимися апериодическими шаблонами. Для поиска шаблона длины т используется скользящее m-битное окно. В отличие от теста Non-overlapping Template Matching Test, окно всегда сдвигается на одну позицию независимо от того, был обнаружен шаблон или нет. Длина исследуемой последовательности должна составлять не менее 106 бит. Размер шаблона т рекомендуется выбирать равным 9 или 10. Maurer s Universal Statistical Test. Тест был разработан Ули Маурером [57] в начале 1990-х гг. Объектом исследования является количество бит, находящихся между повторяющимися шаблонами в последовательности. Тест позволяет оценить, насколько может быть сжата последовательность без потерь информации. Последовательности, допускающие значительное сжатие, признаются неслучайными. Длина исследуемой последовательности должна составлять не менее 387840 бит. Linear Complexity Test. Объектом исследования является линейная сложность последовательности, т.е. наименьшая длина регистра сдвига с линейными обратными связями, порождающего последовательность. Тест позволяет определить, соответствует ли линейная сложность ожидаемому для случайных последовательностей значению. Последовательности, обладающие слишком низкой линейной сложностью, признаются неслучайными. Объектом исследования является количество вхождений всех возможных m-битных пересекающихся шаблонов в последовательность. Тест позволяет определить, соответствует ли наблюдаемое число вхождений каждого из 2т шаблонов ожидаемому. Для случайных последовательностей ожидается, что все шаблоны являются равновероятными, т.е. встречаются с равной частотой. Как и в тесте Overlapping Template Matching Test, для поиска: вхождений; шаблонов в последовательность используется скользящее окно, на . .каждом; шаге сдвигающееся на одну позицию. Длина исследуемой последовательности п и размер шаблона т долж- .. ны выбираться таким образом, чтобы выполнялось соотношение m -2, Approximate Entropy Test. Объектом исследования является числом вхождений-всех возможных m-битных пересекающихся шаблонов, в последовательность. Целью теста является сравнение разницы количества вхождений; шаблонов длины т и . гаН- 1с ожидаемым:для случайных последовательностей.значением Длина последовательности п и размер шаблонам должны выбираться таким образом, чтобы.выполнялось соотношение m—5. Cumulative Sums (Cusum) Test. . Объектом исследования являются-максимальные отклонения от нулевого значения частичных сумм преобразованных членов последовательности полученных из исходных членов путем замены 0-1- —1, It-» 1. Целью теста является выявление последовательностей; в которых частичные суммы отклоняются от нулевого значениязначительно сильнее, чем ожидается для случайной последовательности; В результате теста вычисляются два.р-значения: одно при проходе по последовательности от начала к концу, а второе—вобратном направлении. Длина исследуемой последовательности должна быть не менее 100 бит. Random Excursions Test. В данном тесте последовательность частичных сумм рассматривается как маршрут случайных блужданий по неориентированному графу. Значение частичной суммы рассматривается в качестве номера вершины графа. Объектом исследования является количество циклов, содержащих определенные вершины ровно К раз (под циклом в тесте понимается последовательность вершин маршрута, первый и последний элементы которой равны нулю, а все остальные являются ненулевыми). Целью теста является выявление последовательностей, в которых количество вхождений вершин в циклы значительно отличается от ожидаемого для случайной последовательности значения В результате теста вычисляется восемь значений достигаемого уровня значимости.
