Введение
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
