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

Содержание

Введение……………………………………………………….…4

		Глава 1. Теоретические сведения…………………………….…5

	1.1 Клеточный автомат………...……………………….…5

	1.2 Генераторы ПСП…………….………………………...5

Глава 2. Построение ГСП на основе клеточного автомата…....8

	2.1 Периодичность клеточного автомата..……………….8

	2.2 Постановка задачи…………………………………….8

	2.3 Структура ГПСП……………………………………....8

	2.3 Локальная функция связи…………………………….9

2.5 Применение ЛФС……………………………………..11

2.6 Инициализация………………………………………..11

2.7 Общая схема работы………………………………….12

Глава 3. Тестирование ГПСП………..…………………………14

	3.1 Обзор тестов………………………...………………...14

	3.2 Подбор тестов………………………………………...14

Глава 4. Программный продукт………………………………..18

	4.1 Реализация…………………………………………....18

Глава 5. Тестирование ГПСП…………………………………..21

	5.1 Результаты тестирования ГПСП…………………….21

	5.2 Тестирование конфигураций ГПСП………………...22

Заключение……………………………………………………...25

Список используемых источников…………………………….26

	









































Введение

Клеточные автоматы широко используются в различных областях науки и техники - от моделирования физических процессов, до криптографии. Клеточные автоматы приобрели особую популярность  в математике, физике, теоретической биологии и микромеханике, за счет того, что многие сложные явления, такие как самовоспроизведение, рост и развитие, морфогенез, турбулентные процессы, которые трудно моделировать с помощью дифференциальных уравнений, удается описать с помощью клеточных автоматов. В компьютерных науках клеточные автоматы могут применяться для реализации системы распознавания образов, сжатия данных, построения шифров и генерации псевдослучайных последовательностей. В свою очередь, псевдослучайные последовательности используются для генерации гаммирующих последовательностей, хэширования информации, построения самосинхронизирующихся поточных шифров, формирования ключевой информации и внесения неопределенности в работу  средств защиты.

Данная работа посвящена разработке модели и программного продукта для генерации псевдослучайных последовательностей на основе клеточного автомата. 















Теоретические сведения

1.1 Клеточный автомат 

Клеточным автоматом (КлА) называется модель с дискретным временем, состоящая из множества ячеек памяти, упорядоченных в периодическую n-мерную решетку [2]. Заполнения ячеек являются элементами некоторого конечного множества. Для каждой ячейки выбирается ее окрестность, которая используется для определения заполнения ячейки на следующем такте работы по некоторому заранее заданному правилу. Для классических клеточных автоматов выполняются два свойства: однородности и локальности. Однородность означает, что значение каждой ячейки на следующем такте работы зависит только от текущих состояний клеток, входящих в окрестность данной и правила переходов для всех клеток одинаковы. Кроме того, для решения проблемы краевых клеток противоположные края решетки отождествляются, то есть двумерная решетка закручивается в тор. В соответствии со свойством локальности в окрестность каждой ячейки входят только ячейки, удаленные от нее на расстояние не более заданного. В качестве правила, определяющего новые заполнения ячеек на следующем такте работы, используется булева функция, аргументами которой являются заполнения ячеек, входящих в окрестность данной. Такая функция называется локальной функцией связи (ЛФС). 

1.2 Генераторы ПСП

Генератором псевдослучайной последовательности называют алгоритм, который на основе входных данных, порождает последовательность чисел независимых друг от друга, подчиняющихся заданному распределению. Чаще всего, в качестве такого распределения служит равномерное распределение.

Функционирование генератора псевдослучайной последовательности можно разделить на два этапа:

1. Инициализация генератора

2. Выработка случайной последовательности

Первая фаза функционирования генератора выполняется лишь однажды – перед началом генерации. Вторая фаза выполняется до тех пор, пока не будет получена последовательность нужной длины. 

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

Источники настоящих случайных чисел найти крайне трудно. Физические шумы, такие, как детекторы событий ионизирующей радиации, дробовой шум в резисторе или космическое излучение, могут быть такими источниками. Однако применяются такие устройства в приложениях сетевой безопасности редко. Сложности также вызывают грубые атаки на подобные устройства.

Криптографические приложения используют для генерации случайных чисел особенные алгоритмы. Эти алгоритмы заранее определены и, следовательно, генерируют последовательность чисел, которая теоретически не может быть статистически случайной. В то же время, если выбрать хороший алгоритм, полученная численная последовательность — псевдослучайных чисел — будет проходить большинство тестов на случайность. Одной из характеристик такой последовательности является период повторения, который должен быть больше рабочего интервала, из которого берутся числа.











































Построение ГПСП на основе клеточного автомата



2.1 Периодичность клеточного автомата

Клеточные автоматы можно рассматривать как автономные конечные автоматы. Как и любой автономный конечный автомат, КлА обладают конечным периодом последовательности внутренних состояний, то есть заполнений ячеек решетки. В силу нелинейности локальной функции связи оценить период клеточного автомата не представляется возможным.

2.2 Постановка задачи

Главной задачей, решаемой в рамках данной работы, является создание ГПСП на основе КлА. Для решения данной задачи требуется разработать модель КлА, а также программный продукт, реализующий КлА, функционирующий на основе предложенной модели. Также, программный продукт должен содержать необходимые для проверки ГПСП тесты, на основе которых возможно будет сделать вывод о свойствах генерируемой последовательности.

2.3 Структура ГПСП 

В основе ГПСП будем использовать двумерные булевы клеточные автоматы с прямоугольными ячейками. В таких автоматах значения ячеек содержат значения двоичного множества {0, 1}. Окрестностью ячейки будут являться все ячейки смежные с данной. 

Структура ГПСП представляет из себя два независимых клеточных автомата. Размер решеток обоих клеточных автоматов составляет 47 х 13 ячеек. Выбор простых чисел в качестве размерности КлА позволяет избегать возникновения пространственных периодов [3]. 

В качестве выхода КлА используется подполе размерностью 32 х 8, т.е. ячейки с координатами {0, 0}, {0, 1}, .. {0, 7}, {1, 0}, .. {31, 7} (см. рис. 2.1). Такая конфигурация выходной последовательности автомата позволяет за один такт работы получить 256 значений. Использование в качестве выходных значений лишь часть решетки ячеек, позволяет затруднить восстановление внутреннего состояния генератора по известной выходной последовательности. 





Рис. 2.1. Выход КлА

Выход генератора формируется посредством суммирования по модулю 2 выходных последовательностей обоих генераторов, что позволяет существенно увеличить период итоговой последовательности.

2.4 Локальная функция связи

Для каждого клеточного автомата используется своя локальная функция связи, которая формируется с помощью регистра сдвига с линейной обратной связью (РСЛОС). Для РСЛОС максимальный период достигается при использовании примитивного многочлена в качестве характеристического многочлена и равняется 2L- 1, где L - длина РСЛОС [4]. Для наших целей будем использовать РСЛОС длиной 63 и характеристическими многочленами f(x) = x63 + x62 + 1, f(x) = x63 + x + 1, для первой и второй локальной функции связи соответственно. Для формирования локальной функции связи необходимо сгенерировать 8 бит при помощи РСЛОС и составить локальную функцию связи на основе полученной последовательности. 

Сопоставим каждому сгенерированному биту ячейку клеточного автомата, лежащую в окрестности ячейки с координатами {i, j}. Таким образом, первому биту будет соответствовать ячейка с координатами {i - 1, j - 1}, второму – {i -1, j}, третьему – {i - 1, j + 1}, четвертому – {i, j - 1}, последнему – {i + 1, j + 1}. Получаем локальную функцию связи, определяемую как сложение по модулю 2 ячеек автомата, которым соответствует значение 1 выходной последовательности РСЛОС (см. рис. 2.2). РСЛОС, используемый для этих целей, будем называть регистром локальных функций.



Рис. 2.2. Построение ЛФС



2.5 Применение ЛФС

За один такт работы решетка клеточного автомата может быть перестроена несколько раз с использованием различных локальных функций связи. Для этих целей будем использовать два независимых РСЛОС длиной 12 и характеристическими многочленами f(x) = x12 + x6 + x4 + 1, f(x) = x12 + x11 + x7 + 1 для первого и второго КлА соответственно. Таким образом, на каждом такте работы автомата, РСЛОС будет генерировать 2 бита, на основе которых определяется количество пересчетов решетки автомата. Для значения 00 - необходимо сгенерировать ЛФС и пересчитать значения для ячеек автомата лишь однажды, для значения 01 - необходимо сгенерировать две ЛФС и выполнить два пересчета значений ячеек (для каждой из сгенерированных ЛФС) и т.д. РСЛОС, выполняющий данные действия, будем называть регистром циклов.

Такая конфигурация позволяет увеличить общее количество ЛФС путем композиции переменного числа ЛФС полученных от регистра локальных функций.

2.6 Инициализация

Начальное заполнение РСЛОС определяется случайно и неодинаково для каждого из регистров, т.е. регистры сходного назначения для разных автоматов не должны совпадать.

Заполнение КлА тоже выполняется случайным образом, но ограничено следующими правилами: 

1) запрещено заполнение всех ячеек одинаковыми значениями;

2) количество нулевых ячеек должно стремиться к количеству ячеек со значением 1;

2.7 Общая схема работы

Представить схему работы генератора можно в виде следующего алгоритма:

1.заполнение КлА случайными значениями

2.если КлА заполнен одинаковыми значениями вернуться на шаг 1

3.если доля ячеек одного типа превышает 60% вернуться на шаг 1

4.инициализация РСЛОС

5.если РСЛОС сходного назначения совпадают для разных автоматов вернуться на шаг 4

6.i := 0

7.сгенерировать 2 бита с помощью регистра циклов 

8.n := значение, полученное на шаге 7

9.сгенерировать 8 бит с помощью регистра локальных функций

10.сформировать локальные функции связи

11.рассчитать новые значения ячеек

12.если i >= n, перейти к шагу 15

13.i++

14.перейти к шагу 9

15.извлечь выходные последовательности автоматов

16.сложить по модулю 2 полученные последовательности

17.если достигнута заданная длина выходной последовательности, перейти к шагу 19, иначе перейти к шагу 6

19.конец













































3.	Тестирование ГПСП	

3.1 Обзор тестов 

Под тестированием псевдослучайной последовательности понимается совокупность действий, направленных на определение меры близости псевдослучайной последовательности к истинно случайной. В качестве такой меры могут выступать: большой период, наличие равномерного распределения, равная частота появления одинаковых подстрок и т.д.

Тесты для оценки ПСП делятся на две категории: графические и оценочные. В графических тестах статистические свойства последовательностей отображаются в виде графических зависимостей, по виду которых делается вывод о свойствах исследуемой последовательности. Недостаток этой группы тестов заключается в том, что интерпретацией тестов занимается человек, что может привести к неоднозначности выводов, полученных на основе результатов тестирования. В оценочных тестах статические свойства последовательностей определяются числовыми характеристиками. На основе оценочных критериев делаются заключения о степени близости свойств анализируемой и истинно случайной последовательностей. В отличии от графических тестов, данный вид тестов выдает численную характеристику последовательности, что позволяет однозначно сказать пройден тест или нет [1].

3.2 Подбор тестов

В качестве графических тестов будем использовать тест "Проверка серий". Проверка серий позволяет оценить равномерность распределения символов в исследуемой последовательности на основе анализа частоты появления нулей и единиц, и серий, состоящих из k бит. Данный тест подсчитывает сколько раз встречаются нули, единицы, серии-двойки (всевозможный набор значений из двух бит), серии-тройки и т.д. в битовом представлении исследуемой последовательности. На основе полученных результатов строится график. У последовательности, чьи статические свойства близки к свойствам истинно случайной последовательности разница между числом появлений нулей и единиц, между появлением серий пар, серий строек каждого вида должны стремиться к нулю. 

Для оценочного тестирования воспользуемся тестами Д. Кнута и тестами NIST. Проверка несцепленных серий - тест, автором которого является Д. Кнут, исследующий последовательность на случайность, анализируя длины несцепленных серий различной длины. В двоичной последовательности длины n подсчитывается число появлений всевозможных непересекающихся серий длиной m и вычисляется статистика. Полученный результат анализируется при помощи критерия Хи-квадрат с числом степеней свободы 2m - 1. 

Набор статистических тестов NIST разработан американским Национальным институтом стандартов и технологий и предназначен для оценки статистических свойств двоичных последовательностей. Поскольку набор рассчитан на применение в области криптографии, в нем предъявляются наиболее жесткие требования. Этим объясняется то, что большинство используемых в данной работе тестов является тестами NIST. Статистический тест формулируется для проверки определенной нулевой гипотезы H0 о том, что проверяемая последовательность является случайной. С этой нулевой гипотезой связана альтернативная гипотеза H? о том, что последовательность неслучайна. Для каждого применяемого теста получают заключение о принятии или отклонении нулевой гипотезы, основываясь на сформированной исследуемым генератором последовательности.

Рассмотрим тесты NIST: частотный тест в подпоследовательностях, тест блоков в подпоследовательностях и монобитный тест. Частотный тест в подпоследовательностях проверяет равномерность появления 0 и 1 в подпоследовательностях. Двоичная последовательность длины n разбивается на N непересекающихся M-битных подпоследовательностей, где N - целая часть отношения n и M. Определяется доля нулей и единиц в каждой подпоследовательности, высчитывается статистика и значение P-value. Для того чтобы тест считать пройденным значение P-value должно быть больше 0.01. 

Тест блоков в подпоследовательностях исследует равномерность распределения 0 и 1 в исследуемой последовательности на основе анализа количества появления блоков в подпоследовательностях. Двоичная последовательность длины n разбивается на N непересекающихся M-битных подпоследовательностей, где N - целая часть отношения n и M. Число появлений подпоследовательностей с максимальной длиной блока распределяется по категориям в зависимости от длины блока. Вычисляется статистика и значение P-value. Тест считается пройденным, если значение P-value больше 0.01.

Объектом исследования монобитного теста является соотношение количества единиц и нулей в исследуемой подпоследовательности. Для случайной подпоследовательности ожидается, что число единиц и нулей будет приблизительно одинаковым. В двоичной последовательности длины n  вычисляем разницу между числом появления нулей и единиц. Вычисляем статистику и значение P-value, если значение P-value больше 0.01 – тест пройден.











































4.	Программный продукт

4.1 Реализация

Для реализации программного продукта был использован язык программирования C# и технология WindowsForms. В качестве среды разработки выбрана VisualStudio.

Основная цель продукта – генерация ПСП на основе клеточного автомата, функционирующего по схеме приведенной в главе 2. 

Интерфейс программного продукта состоит из окна с двумя вкладками:

генератор

тесты

Вкладка «Генератор» (см. рис. 4.1) предназначена для генерации псевдослучайной последовательности  на основе разработанной модели ГПСП. Для того чтобы сгенерировать ПСП, необходимо указать размеры решеток для клеточных автоматов, длину выходной последовательности и разрядность выходной последовательности. Просмотреть сгенерированную последовательность можно в одноименном текстбоксе. При установке параметра «Вывод в файл», сгенерированная ПСП будет сохранена в файл Random_Sequence_date, где date – дата и время на начало генерации ПСП.



Рис. 4.1. Окно генерации ПСП

Вкладка «Тесты» (см. рис. 4.2) служит для анализа статистических свойств построенного генератора. На данной вкладке реализованы все тесты, описанные в главе 3. Окно разбито на 2 рабочие области: графические и оценочные тесты. Построение графических тестов происходит в MS Excel и интерпретация результатов возлагается на пользователя, в отличии от оценочных тестов. Для того чтобы приступить к тестированию ПСП, необходимо указать длину выходной последовательности генератора и количество исследуемых последовательностей. Для некоторых тестов необходимо задать входные значения: тест “Проверка несцепленных серий” требует указания длины серий, для частотного теста в подпоследовательностях требуется ввести длину подпоследовательности. После выполнения тестов, выводится средний результат для каждого из тестов, а также количество последовательностей, успешно пройденных тест, и количество последовательностей, для которых результаты теста оказались неудовлетворительными.



Рис. 4.2. Окно тестирования ГПСП



















5.	Тестирование ГПСП

5.1 Результаты тестирования ГПСП

Тестирование генератора производилось на ста различных последовательностях длиной 750000 бит. Результаты оценочного тестирования приведены в таблице 1.

Таблица 1. Результаты оценочного тестирования



В тесте на проверку несцепленных серий, 95 из 100 последовательностей прошли тест при среднем значении Хи-квадрат равном 7,456 для 7 степеней свободы. Частотный тест в подпоследовательностях показал стопроцентный результат. При длине подпоследовательностей 8000 бит среднее значение P-value равняется 0,529, что больше 0,01, следовательно, данный тест может считаться пройденным. Тест блоков в подпоследовательностях также дал стопроцентный результат: все 100 исследуемых последовательностей прошли тест. Средний результат P-value 0,428, таким образом, тест считается успешно пройденным. В монобитном тесте 99% тестов завершились успешно. При этом, средний показатель P-value составил 0,485.

Графический тест проверки серий (см. рис. 4.3) демонстрирует, что разница между появлением нулей и единиц, серий пар и серий-троект, является незначительной для тестируемой выборки, следовательно, считаем данный тест выполненным.



Рис. 4.3. Результат теста “Проверка серий”



5.1 Тестирование конфигураций ГПСП

Протестируем различные конфигурации генератора для оценки влияния модели генератора на статистические свойства генерируемой последовательности и скорость генерирования последовательности. 

Дадим определения различным конфигурациям генератора. Полной конфигурацией генератора назовем генератор, функционирующий в полном соответствии с моделью, предложенной в главе 2. Конфигурацией генератора без регистров цикла будем называть полный генератор, не использующий регистры цикла, т.е. генератор, пересчитывающий значения ячеек автомата один раз за такт работы. Конфигурацией с одним автоматом назовем полную конфигурацию генератора, использующую только один КлА, т.е. выходная последовательность снимается с единственного КлА без сложений по модулю два с чем-либо. Рассмотрим заключительную конфигурацию генератора – минимальную. Минимальная конфигурация является объединением конфигурации без регистра циклов и конфигурации с одним автоматом, т.е. минимальная конфигурация представляет из себя генератор, в котором отсутствуют регистры циклов и используется только один КлА.

Проведем тестирование указанных конфигураций с помощью программного продукта, разработанного в главе 4 на наборе тестов, рассмотренных в главе 3. Результаты тестирования представлены в таблице 2.

Таблица 2. Результаты тестирования конфигураций генератора



Было проведено по три тестовые сессии для каждой из ста тестируемой последовательности. Каждая последовательность состояла из 750000 бит. Исходя из данных, приведенных в таблице 2, можно проследить зависимость конфигурации автомата от количества выполненных тестов. При минимальной конфигурации генератора процент выполненных тестов составляет 88%, при полной – 98,25%. Наибольший прирост процента выполненных тестов дает добавление второго КлА в генератор, это можно проследить, рассчитав разницу процента выполненных тестов между минимальной конфигурацией и конфигурацией без регистра циклов – 7,25%. Добавление в модель регистра циклов дает немного меньший прирост – приблизительно 2,8%. Так же, можно наблюдать обратную тенденцию – с усложнением (добавлением новых элементов) модели генератора, растет время, затраченное на генерацию выходной последовательности. Так для минимальной конфигурации генератора это время составляет 0,473с, в свою очередь, для полной конфигурации это число уже равняется 2,388с.





























Заключение

В рамках данной работы была разработана модель ГПСП на основе КлА, а также программный продукт, реализующий, разработанную модель ГПСП и набор тестов для анализа статистических свойств генератора. По результатам тестирования, был сделан вывод о близости генерируемой последовательности и истинно-случайной последовательностей.

	

































Список используемых источников

1.   Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. – М.: КУДИЦ-ОБРАЗ, 2003. – 240 с. – (СКБ – Специалисту по компьютерной безопасности)

2.    М. Шредер. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001, 528 с.

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

4. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты  на языке Си. М.: Изд-во "Триумф", 2002. 816.









4.......................