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

Диссертация на соискание ученой степени кандидата технических наук. Москва, МГТУ им. Баумана, 2011 — 224 стр. Специальность: 05.13.17 —Теоретические основы информатики Научный руководитель: к.ф-м.н. А. Е. Жуков Цель работы: разработка новых генераторов псевдослучайных равномерно распределенных двоичных последовательностей, отвечающих следующим требованиям:
- выходные последовательности генераторов на длине периода должны быть статистически неотличимы от случайных равномерно распределенных двоичных последовательностей, что должно подтверждаться успешным прохождением соответствующих специализированных тестов;
- период выходных последовательностей генераторов должен превосходить требуемые на практике значения;
- быстродействие и эффективность реализации генераторов на параллельных вычислительных устройствах, таких как ПЛИС, должны быть не ниже, чем у известных аналогов. Научная новизна:
- исследовано влияние веса локальной функции связи на распределение значений ячеек памяти клеточных автоматов; сформулирован, доказан и подтвержден экспериментально критерий сохранения равномерности распределения;
- впервые сформулировано понятие лавинного эффекта для клеточных автоматов; получено теоретическое описание характеристик оптимального лавинного эффекта и эмпирические зависимости характеристик лавинного эффекта от выбора окрестностей ячеек; показано, что клеточные автоматы обладают свойством размножения изменений;
- впервые введено и исследовано понятие пространственного периода в классических клеточных автоматах; сформулировано и доказано необходимое условие существования пространственного периода; показано, что нетривиальный пространственный период существенно снижает верхнюю границу периода последовательности внутренних состояний;
- разработаны новые методы генерации псевдослучайных последовательностей; на основании свойств клеточных автоматов осуществлен синтез структуры генератора и обоснован выбор его параметров; эмпирически подтверждено соответствие статистических свойств выходных последовательностей современным требованиям. Практическая ценность: Теоретическая значимость исследований заключается в разработке новых методов генерации псевдослучайных последовательностей и получении новых результатов в области теории клеточных автоматов.
Практическая ценность исследований обусловлена превосходством разработанных генераторов над существующими аналогами как по быстродействию, так и по эффективности реализации. Содержание: Введение
Краткая историческая справка
Общая характеристика работы
Постановка задачи
Структура диссертации
1. Обзор методов генерации псевдослучайных последовательностей
1.1. Общие сведения
1.2. Генераторы псевдослучайных последовательностей
1.3. Методы улучшения свойств генераторов псевдослучайных
чисел
1.4. О криптографически качественных генераторах псевдослучайных
последовательностей
1.5. Выводы
2. Исследование свойств клеточных автоматов
2.1. Классические клеточные автоматы
2.2. Неоднородные клеточные автоматы
2.3. Выводы
3. Разработка генераторов псевдослучайных последовательностей
3.1. О параметрах клеточных автоматов и эффективности их реализации ПО
3.2. Базовые генераторы
3.3. Комбинированные генераторы
3.4. Выводы
4. Исследование статистических свойств выходных последовательностей
генераторов
4.1. Общие сведения
4.2. Набор статистических тестов NIST
4.3. Методика проведения и результаты статистического тестирования
4.4. Выводы
5. Высокоскоростная аппаратная реализация разработанных
генераторов
5.1. Общие сведения
5.2. Описание реализации
5.3. Характеристики прототипов аппаратной реализации
5.4. Сравнение быстродействия и эффективности разработанной аппаратной реализации и существующих аналогов
5.5. Выводы
Выводы и заключение
Литература