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

Московский государственный технический университет им. Н. Э. БауманаНа правах рукописи04.2.01 1 6 7 4 0 3?•Сухинин Борис МихайловичРАЗРАБОТКА И ИССЛЕДОВАНИЕ ВЫСОКОСКОРОСТНЫХ ГЕНЕРАТОРОВПСЕВДОСЛУЧАЙНЫХ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ ДВОИЧНЫХП О С Л Е Д О В А Т Е Л Ь Н О С Т Е Й НА О С Н О В Е К Л Е Т О Ч Н Ы Х АВТОМАТОВ05.13.17 —Теоретические основы информатикиДиссертация на соискание ученой степеникандидата технических наукНаучный руководитель —кандидат физико-математических наукА. Е. ЖуковМосква - 2011?.-2-ОГЛАВЛБНИЕСтр.Введение9Краткая историческая справка9Общая характеристика работы11Постановка задачи16Структура диссертации171.Обзор методов генерации псевдослучайных последо­вательностей191.1.Общие сведения191.1.1.Случайные последовательности и их свойства191.1.2.Подходы к получению равномерно распределенных случай­ных последовательностей211.2.Генераторы псевдослучайных последовательностей221.2.1.Формальное определение генератора псевдослучайных по­следовательностей1.2.2.22Классификация генераторов псевдослучайных последова­тельностей251.2.3.Линейный конгруэнтный метод261.2.4.Нелинейные конгруэнтные методы321.2.4.1.

Метод «середины квадрата»321.2.4.2. Метод умножения с переносом331.2.4.3. Квадратичный конгруэнтный метод341.2.4.4. Инверсивный (обратный) конгруэнтный метод361.2.5.37Генераторы Фибоначчи-3-Стр.1.2.5.1. Классический генератор Фибоначчи381.2.5.2. Аддитивные генераторы Фибоначчи391.2.5.3. Мультипликативные генераторы Фибоначчи391.2.5.4. Генераторы Фибоначчи с операцией «исключающее или» .

.401.2.6.40Генераторы на основе регистров сдвига1.2.6.1. Регистры сдвига с линейными обратными связями над про­извольным конечным полем401.2.6.2. Регистры сдвига с линейными обратными связями над полемF2421.2.6.3. Обобщенные регистры сдвига451.2.6.4. Обобщенные регистры сдвига с закручиванием461.2.6.5. Вихрь Мерсенна471.2.6.6. Регистры сдвига с нелинейными обратными связями . . . .501.2.7.52Генераторы на основе клеточных автоматов1.2.7.1. Генераторы на основе одномерных клеточных автоматов . .1.3.1.3.1.Методы улучшения свойств генераторов псевдослучайныхчисел53Применение фильтрующей функции541.3.1.1. Линейные регистры сдвига с фильтрующей функцией1.3.2.52...Комбинация последовательностей54561.3.2.1.

Комбинация последовательностей при помощи бинарнойоперации561.3.2.2. Генератор Геффе571.3.3.59Прореживание последовательностей1.3.3.1. Схема Ниффелера591.3.3.2. Сжимающий генератор601.4.О криптографически качественных генераторах псевдослу­чайных последовательностей611.5.Выводы622.Исследование свойств клеточных автоматов682.1.Классические клеточные автоматы68-4-2.1.1.Основные понятия и определения2.1.1.1.Одномерные булевы клеточные автоматыСтр.68742.1.1.2.

Двумерные булевы клеточные автоматы2.1.2.75Обзор имеющихся результатов для классических одномер­ных булевых клеточных автоматов2.1.3.77Локальная функция связи и равновероятность значений яче­ек решетки792.1.4.Лавинный эффект842.1.4.1.Интегральная характеристика лавинного эффекта862.1.4.2. Пространственная характеристика лавинного эффекта . . .882.1.4.3. Зависимость характеристик лавинного эффекта от выбораокрестности892.1.5.Свойства периодичности912.1.5.1.Временная периодичность клеточных автоматов922.1.5.2. Пространственная периодичность клеточных автоматов. .932.1.5.3. Иные проявления периодичности962.2.Неоднородные клеточные автоматы972.2.1.Основные понятия и определения972.2.2.Локальная функция связи и равновероятность заполнениянабора ячеек памяти992.2.3.Лавинный эффект1032.2.3.1.Интегральная характеристика лавинного эффекта1042.2.3.2.

Зависимость характеристик лавинного эффекта от выбораокрестности1052.2.4.Свойства периодичности1072.3.Выводы1083.Разработка генераторов п с е в д о с л у ч а й н ы хпоследо­вательностей3.1.3.2.110О параметрах клеточных автоматов и эффективности их ре­ализацииПОБазовые генераторы111-5Стр.3.2.1.Базовый генератор на основе классических клеточных авто­матов1123.2.1.1. Обоснование выбора размерности решетки и типа окрестности 1123.2.1.2. Обоснование выбор размера решетки и способа формирова­ния выходной последовательности3.2.1.3.

Обоснование выбора локальной функции связи1131163.2.1.4. Обоснование выбора параметров РСЛОС и периода выход­ной последовательности3.2.2.116Базовый генератор на основе неоднородных клеточных ав­томатов3.2.2.1. Обоснование выбора окрестности1181183.2.2.2. Обоснование выбора размера клеточного автомата и способаформирования выходной последовательности3.2.2.3.

Обоснование выбора локальной функции связи1191203.2.2.4. Обоснование выбора параметров РСЛОС и периода выход­ной последовательности1203.2.3.Параметры и начальные значения генератора1213.2.4.Алгоритм работы1223.2.5.Достоинства и недостатки базовых генераторов1233.3.Комбинированные генераторы1243.3.1.Параметры и начальные значения генератора1263.3.2.Детализированная структура и алгоритм работы1273.3.3.Достоинства и недостатки1293.4.Выводы1304.Исследование статистических свойств выходных по­следовательностей генераторов1314.1.4.1.1.Общие сведения132Формальное описание процесса статистического тестирования 1344.2.Набор статистических тестов NIST1344.2.1.Краткое описание статистических тестов1354.2.2.Реализация набора статистических тестов NIST140-6Стр.4.3.Методика проведения и результаты статистического тести­рования1424.4.Выводы1475.Высокоскоростная аппаратная реализация разрабо­танных генераторов1495.1.Общие сведения1495.2.Описание реализации1515.2.1.Блок Generator — реализация генератора1535.3.Характеристики прототипов аппаратной реализации5.4.Сравнение быстродействия и эффективности разработанной.

. . . 154аппаратной реализации и существующих аналогов156Выводы158Выводы и заключение161Литература164Приложения173П.1.Описание статистических тестов NIST173П.1.1.Frequency (Monobit) Test173П.1.2.Frequency Test within a Block .174П.1.З.Runs Test176П.1.4.Test for the Longest Run of Ones in a Block177П.1.5.Binary Matrix Rank Test179П.1.6.Discrete Fourier Transform (Spectral) Test180П.1.7.Non-overlapping Template Matching Test182П.1.8.Overlapping Template Matching Test183П.1.9.Maurer's Universal Statistical Test185П.1.10.Linear Complexity Test1885.5.П.1.11.

Serial Test190П.1.12.191Approximate Entropy TestП.1.13. Cumulative Sums (Cusum) Test193-7Стр.П.1.14.Random Excursions Test194П. 1.15.Random Excursions Variant Test197П.2.Краткое описание программного комплекса автоматизациистатистического тестированияП.З.Формирование параметров генераторов198псевдослучайныхпоследовательностей на основе клеточных автоматов . . . .П.3.1.Алгоритм формирования локальной функции связи задан­ного весаП.3.2.200200Алгоритм формирования начальных значений ячеек памятиклеточного автомата и регистра сдвига с линейными обрат­ными связямиП.3.3.201Алгоритм формирования окрестности неоднородных клеточ­ных автоматов202П.4.Способы задания некоторых параметров клеточных автоматов202П.4.1.Способ задания значений ячеек классических двумерныхклеточных автоматовП.4.2.Способ задания значений ячеек неоднородных клеточных а в ­томатовПАЗ.204Параметры генераторов при осуществлении статистическоготестированияП.5.1.204Способ задания локальной функции связи неоднородных;клеточных автоматовП.5.203Способ задания локальной функции связи классических кле­точных автоматовП.4.5.203Способ задания окрестности ячейки неоднородного клеточ­ного автоматаП.4.4.203205Параметры базовых генераторов на основе классическихдвумерных клеточных автоматов205П.5.1.1.

Параметры клеточного автомата205П.5.1.2. Параметры регистра сдвига с линейными обратными связями 206П.5.2.Параметры базовых генераторов на основе неоднородныхклеточных автоматов206-8Стр.П.5.2.1. Параметры клеточного автомата206П.5.2.2. Параметры регистра сдвига с линейными обратными связями 207П.5.3.Параметры комбинированных генераторов на основе класси­ческих двумерных клеточных автоматов207П.5.3.1. Параметры первого клеточного автомата207П.5.3.2. Параметры второго клеточного автомата208П.5.3.3. Параметры регистра сдвига с линейными обратными связями 209П.5.4.Параметры комбинированных генераторов на основе неодно­родных клеточных автоматов209П.5.4.1.

Параметры первого клеточного автомата209П.5.4.2. Параметры второго клеточного автомата210П.5.4.3. Параметры регистра сдвига с линейными обратными связями 211П.6.Параметры генераторов с хорошими статистическими свой­ствамиП.6.1.211Параметры комбинированного генератора TD12 на основеклассических двумерных клеточных автоматов211П.6.1.1. Параметры первого клеточного автомата212П.6.1.2. Параметры второго клеточного автомата212П.6.2.Параметры комбинированного генератора ND32 на основенеоднородных клеточных автоматов212П.6.2.1.

Параметры первого клеточного автомата213П.6.2.2. Параметры второго клеточного автомата217-9-ВВБДЕНИЕКРАТКАЯ ИСТОРИЧЕСКАЯ СПРАВКАСлучайные последовательности широко используются в самых раз­личных областях. Исторически их применение было связано с развитиемтеории игр и использованием методов Монте-Карло для численного реше­ния математических задач.До середины XX в. случайные последовательности имитировались припомощи простейших случайных экспериментов: бросания монеты или иг­ральной кости, извлечения шаров из урны, раскладывания карт и т.д. В1927 г. английским ученым Леонардом Типпетом впервые были опубли­кованы таблицы [77], содержащие свыше 40 000 случайных цифр, «произ­вольно извлеченных из отчетов о переписи населения».Позже были разработаны механические генераторы случайных чисел.Первая такая машина была использована в 1939 г.

Кендаллом и Бабингтон-Смитом для построения таблицы [41], содержащей 100 000 случайныхчисел.Компьютер Ferranti Mark I, запущенный в 1951 г., обладал встроен­ным резисторным генератором шума, с которого при помощи специальнойпрограммы 20 случайных бит подавались на сумматор (этот метод былпредложен Аланом Тьюрингом). В 1955 г. RAND Corporation опубликова­ла таблицы [61], в которых содержался миллион случайных чисел, полу­ченных на специально сконструированной ЭВМ с физическим генераторомслучайных чисел.К концу XX в. спрос на генераторы случайных последовательностей сзаданными вероятностными распределениями, а также на сами случайные-10последовательности настолько возрос, что за рубежом стали появляться на­учно-производственные фирмы, занимающиеся производством и продажейбольших массивов случайных чисел.