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

На правах рукописи

Сухинин Борис Михайлович

Разработка и исследование высокоскоростных

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

05.13.17 —Теоретические основы информатики

1 О НОЯ 2011

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва - 2011

4859348

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Московский государственный технический университет имени Н.Э. Баумана» (МГТУ им. Н.Э. Баумана)

Научный руководитель: Официальные оппоненты:

Ведущая организация:

канд. физ.-мат. наук Жуков Алексей Евгеньевич

д-р физ.-мат. наук, проф. Грушо Александр Александрович

канд. техн. наук

Архангельская Анна Васильевна

Национальный исследовательский ядерный университет «МИФИ»

Защита диссертации состоится 8 декабря 2011 г. в 14 часов 30 минут на заседании диссертационного совета Д 212.141.10 при МГТУ им. Н.Э. Баумана по адресу: 105005, г. Москва, ул. 2-я Бауманская, д. 5, стр. 1.

Отзыв на автореферат, заверенный печатью организации, просим высылать по адресу: 105005, г. Москва, ул. 2-я Бауманская, д. 5, стр. 1, МГТУ им. Н. Э. Баумана, ученому секретарю совета Д 212.141.10.

С диссертацией можно ознакомиться в библиотеке МГТУ им. Н. Э. Баумана.

Автореферат разослан «—»-2011 г.

Ученый секретарь диссертационного совета,

канд. техн. наук, доцент —С. Р. Иванов

Общая характеристика работы

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

Актуальность проблемы. Актуальность обусловлена широким применением псевдослучайных последовательностей в имитационном моделировании, методах Монте-Карло, криптографии, программировании и иных областях. Свой вклад в исследование псевдослучайных последовательностей и их генераторов внесли такие известные ученые, как А. Н. Колмогоров, Р. фон Мизес, Дж. фон Нейман, Дж. Марсалья, Д. Кнут, П. Лекваер, С. Вольфрам и др. Вопросы генерации псевдослучайных последовательностей широко обсуждаются на отечественных и зарубежных научных конференциях, таких как 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 наименований.

Основные термины и определения

Пусть М = [mo, mi,... , mx-i] — множество двоичных ячеек памяти. Сопоставим каждой ячейке тх £ М ее окрестность — упорядоченный набор Wfax) = [mXl,mX2,..., mxJ, мощность которого не зависит от выбора ячейки тх, окрестностью Y также будем называть правило, по которому каждой ячейке тх сопоставляется набор Ш(тх). Обозначим через значение ячейки тх в момент времени t, а через W®(mx) — набор, составленный из значений ячеек, входящих в окрестность тх, в момент времени t.

Неоднородным клеточным автоматом (НКлА) размера X с окрестностью ¥ и локальной функцией связи (ЛФС) / будем называть автономный конечный автомат, состояние которого определяется совокупностью значений ячеек из множества М (|М| = X). Временная шкала такого автомата дискретна, а смена значений всех ячеек происходит синхронно при увеличении номера такта в соответствии с зависимостью mii+1' = / где / яв-

ляется булевой функцией от к переменных (к — мощность окрестности) и не зависит от выбора ячейки тх. 4

■■■

■■■

I I

__

m а:

— ш :

(а) (б) (в) (г)

Рис. 1. Типы окрестности двумерных классических клеточных автоматов: (а) и (б) — полная и неполная окрестности Мура, (в) и (г) — полная и неполная окрестности фон Неймана

Классические клеточные автоматы (ККлА) могут рассматриваться как частный случай неоднородных. В ККлА множество М упорядочено геометрически: ячейки располагаются в узлах п-мерной прямоугольной решетки размера Х\Х Х2Х.. .х Хп. Противоположные края решетки отождествляются, т. е. все действия над координатами выполняются по модулю соответствующего линейного размера решетки. Для обозначения ячейки с координатами (хг,х2,..., хп) далее используется запись тХиХ2,...)Хп.

Расстояние между ячейками те = тх х х и т:

■xltx2,...,xn и — ^ij.ij,...,®;;

ККлА равно наибольшей по абсолютному значению разности одноименных координат с учетом отождествления краев решетки: d(m,m*) = maxien {min (|Xi -хЦХ{- \x{ - ж||)}. Максимально возможное расстояние между ячейками классического клеточного автомата составляет dmax = rnaxm,m.6M {d(m,m*)} = maxi<is£ri {("(X, - l)/2]}.

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

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

Содержание работы

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

Глава 1. В первой главе приведено формальное понятие генератора псевдослучайных последовательностей и выполнен аналитический обзор су-

ККлА НКлА

Рис. 2. Эмпирическая зависимость вероятности Рг[т^ = 1] от номера такта í при равномерном начальном распределении значений ячеек для различных вариантов нормированного веса V) ЛФС

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

Глава 2. Во второй главе формализованы понятия НКлА и ККлА и исследован ряд свойств, имеющих важное значение при построении генераторов псевдослучайных последовательностей на основе клеточных автоматов: зависимость распределения значений ячеек от веса ЛФС, лавинный эффект и его характеристики, периодичность в клеточных автоматах.

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

В силу доказанного критерия при построении генераторов псевдослучайных равномерно распределенных последовательностей следует ограничиться применением клеточных автоматов с равновесными ЛФС.

Лавинный эффект. Лавинный эффект (ЛЭ) был введен X. Фейстелем для оценки свойств блочных шифров: «хорошим» считается такой ЛЭ, при котором малые изменения входных данных приводят к значительным изме-

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

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

При исследовании лавинного эффекта рассматривалась модель, состоящая из двух идентичных клеточных автоматов, различающихся только значением одной ячейки в начальный момент времени. С целью количественного описания ЛЭ в диссертации предложены две числовые характеристики: интегральная и пространственная.

Интегральная характеристика 77^) лавинного эффекта отражает временную зависимость отношения количества изменившихся ячеек к размеру клеточного автомата.

Теоретическими методами в работе получено выражение, описывающее интегральную характеристику г)ор1 (Ь) оптимального ЛЭ в классических клеточных автоматах, которое для частного случая двумерных ККлА с размером решетки X х У {X ^ У) и радиусом локальности г = 1 имеет вид

Для НКлА в диссертации доказано, что если каждая ячейка входит в окрестность ровно к других ячеек, где А; —мощность окрестности, то интегральная характеристика оптимального ЛЭ ограничена сверху соотношением

где X — размер клеточного автомата.

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

В диссертации получено выражение, описывающее пространственную характеристику оптимального ЛЭ, для двумерных клеточных автома-

тов с размером решетки X х У (X ^ У) и единичным радиусом локальности

(кш - 1)/{к - 1) < X, {кш-1)/(к-1)>Х,

имеющее вид

¿> \{Х-1)/2\.

М*) = {\(Х- 1)/2]

1

По результатам анализа эмпирических данных (рис. 3 и 4) сделан вывод о том, что клеточные автоматы обладают свойством размножения изменений, причем характеристики лавинного эффекта улучшаются с увеличением мощности окрестности, и для ККлА с окрестностями Мура практически совпадают с таковыми для оптимального ЛЭ. Кроме того, при фиксированной мощности окрестности лавинный эффект в НКлА выражен более ярко по сравнению с ККлА.

Периодичность. Период последовательности внутренних состояний произвольного клеточного автомата размера X ограничен сверху неравенством Т < Ттах = 2х, которое при X ^ 2 является строгим.

В классических клеточных автоматах возможно формирование пространственных периодов, характеризующихся выполнением равенства т[х= гп®+к1Ти х.+к.Т......Хп+кпТп для всех ячеек ККлА при любых целых кг (действия над координатами ячеек выполняются по модулю соответствующего линейного размера решетки). Т, — наименьшее целое число, при котором равенство верно — является величиной пространственного периода вдоль оси

Существование пространственного периода позволяет рассматривать вместо исходного ККлА с решеткой размера Х\Х Хч х ... х Хп клеточный автомат с решеткой размера х Т2 х ... х Тп и приводит к уменьшению максимально возможного периода последовательности внутренних состояний в 2Х1-Х2-ХП-ТГТ2-ТП ра3) что недопустимо при использовании клеточных автоматов в структуре генераторов псевдослучайных последовательностей.

В диссертации доказано, что необходимым условием существования пространственного периода является делимость линейных размеров решетки Х{ на соответствующие величины пространственных периодов Т{. Исходя из доказанного условия сделан вывод о том, что для исключения возникновения нетривиальных пространственных периодов в классических клеточных автоматах в качестве размеров решетки следует выбирать простые числа.

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

Генератор включает два клеточных автомата и С2 и регистр сдвига с линейными обратными связями Д (рис. 5). На каждом такте работы клеточные автоматы вырабатывают по 256 бит первичных псевдослучайных последовательностей. Выходная последовательность генератора формируется посредством поэлементного сложения по модулю 2 первичных последо-8

Интегральная — г

Пространственная —

оптимальный лавинный эффект-^-полная окрестность фон Неймана -а-полная окрестность Мура -»-неполная окрестность фон Неймана -«-неполная окрестность Мура

Рис. 3. Усредненные эмпирические характеристики ЛЭ в ККлА для различных вариантов выбора окрестности

-♦-мощность окрестности 6-^мощность окрестности 3 -о-мощность окрестности 5-^мощность окрестности 2 -»-мощность окрестности 4

Рис. 4. Усредненная эмпирическая интегральная характеристика ЛЭ в НКлА при различных вариантах мощности окрестности

Рис. 5. Структура генератора

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

В состав генератора на основе классических клеточных автоматов в качестве Сг и С2 входят двумерные ККлА размера 37 х 11 ячеек с неполной окрестностью Мура. Использование простых чисел в качестве размеров решетки исключает формирование пространственных периодов, а выбор окрестности обусловлен соответствующими ей хорошими характеристиками лавинного эффекта. Выход каждого клеточного автомата формируется из значений ячеек, лежащих на подрешетке размера 32 х 8.

При построении генератора на основе неоднородных клеточных автоматов их размер составляет 257 ячеек. Мощность окрестности равна 4, что позволяет достичь компромисса между характеристиками лавинного эффекта и эффективностью аппаратной реализации, а сама окрестность выбирается случайным образом для каждой ячейки. Выход автоматов формируется из значений ячеек с индексами от 0 до 255.

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

Регистр сдвига с линейными обратными связями Я используется для контроля периода выходной последовательности генератора. Выход регистра прибавляется по модулю 2 к значению одной из ячеек каждого клеточного автомата (для ККлА —с координатами (34,9), для НКлА —с индексом 256), не используемых напрямую при формировании первичных выходных последовательностей. Свойство размножения изменений в клеточных автоматах позволяет утверждать, что период выходной последовательности генератора будет не менее периода выходной последовательности регистра сдвига.

В диссертации использован регистр длины 63, для которого нижняя оценка периода выходной последовательности генератора составляет

Т > 256 • (263 — 1) и 2,36 • 1021. При необходимости обеспечения ббльшего периода длина регистра может быть увеличена.

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

Функционирование генератора включает три фазы:

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

2) фазу холостого хода, необходимую для распространения влияния выхода регистра сдвига на все ячейки клеточного автомата за счет лавинного эффекта;

3) фазу генерации, в процессе которой вырабатывается выходная последовательность.

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

В качестве инструмента исследования применялся общепризнанный в мировой практике набор статистических тестов Национального института стандартов и технологии США (NIST). В состав набора входят 15 разновидностей проверок, направленных на выявление статистических отклонений выходных последовательностей генераторов от случайных равномерно распределенных двоичных последовательностей.

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

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

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

Глава 5. В пятой главе описывается аппаратная реализация разработанных генераторов и проводится ее сравнение с современными аналогами.

Описание реализации. В качестве платформы для аппаратной реализации используется недорогая ПЛИС (FPGA) Altera Cyclone II. Выходная последовательность генератора по 256-разрядной шине подается напрямую

ПЛИС Altera Cyclone II (EP2C35F672C6) Генератор

Клеточный автомат 1 f р

Регистр сдвига

Клеточный автомат 2 (; Е>

256

Память на кристалле ПЛИС

UART

Выводы микросхемы Интерфейс RS-232

Рис. 6. Структурная схема аппаратной реализации

на выводы микросхемы, а также записывается во внутреннюю память ПЛИС для дальнейшего анализа (рис. 6).

Номинальная тактовая частота работы схемы составляет 100 МГц, причем статический анализ временных задержек показал, что она может быть увеличена до 140 МГц при построении генераторов на основе классических и до 149 МГц — на основе неоднородных клеточных автоматов без внесения каких-либо изменений в аппаратную реализацию.

Структура клеточных автоматов позволяет вычислять новые значения всех ячеек параллельно, что обеспечивает высокую эффективность аппаратной реализации генератора и формирование 256 бит выхода за один такт синхронизации схемы. Таким образом, скорость выработки псевдослучайной последовательности на номинальной тактовой частоте составляет 23,8 Гбит/с.

Разработка осуществлялась в САПР Altera Quartus II на языке описания цифровых устройств VHDL.

Сравнительные характеристики. Сравнение быстродействия и эффективности аппаратной реализации проводилось с генераторами, представленными на европейский конкурс eSTREAM.

В качестве показателя быстродействия использовалась скорость выработки выходной последовательности на максимальной тактовой частоте и на частоте 100 МГц. Нормирование по частоте обусловлено применением технологии специализированных микросхем ASIC для реализации генераторов, представленных на конкурс eSTREAM. Технология ASIC обеспечивает функционирование на более высокой по сравнению с FPGA тактовой частоте, однако требует существенно больших финансовых и технологических затрат. Как видно из графиков на рис. 7, по быстродействию разработанная аппаратная реализация превосходит лучший из аналогов — алгоритм Trivium — на максимальной тактовой частоте в два, на на частоте 100 МГц — в четыре раза.

!@На максимальной тактовой частоте 1Ща тактовой частоте 100 МГц

34180

36 377

18 568

4475

Grain

4257

6 057

1

Ш

Trivium VEST ZK-Crypt ККлА НКлА

Рис. 7. Сравнение быстродействия разработанной аппаратной реализации и генераторов, представленных на конкурс еБТПЕАМ

40

30

20

10

0,41

Mickey

23,31

15,77"

1,56

Ог£

Trivium

ККлА

33,55

НКлА

Рис. 8. Сравнение эффективности разработанной аппаратной реализации и генераторов, представленных на конкурс еБТКЕАМ

В качестве показателя эффективности было выбрано отношение скорость выработки выходной последовательности на максимальной тактовой частоте к количеству использованных аппаратных ресурсов (для ПЛИС Altera единицей ресурсов является логический элемент — LE). Сравнение показало (рис. 8), что наибольшей эффективностью, значительно превосходящей аналоги, обладает реализация генератора на основе неоднородных клеточных автоматов, что объясняется малой мощностью окрестности. Эффективность реализации генератора на основе классических клеточных автоматов является сравнительно невысокой, однако может быть существенно улучшена за счет использования старших семейств ПЛИС, таких как Altera Stratix, позволяющих реализовать булеву функцию от 8 переменных в пределах одного LE.

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

Основные результаты работы

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

2) Исследовано влияние веса локальной функции связи на распределение значений ячеек памяти клеточных автоматов; сформулирован, доказан и подтвержден эмпирически критерий сохранения равномерности распределения.

3) Впервые сформулировано понятие лавинного эффекта в клеточных автоматах; получено теоретическое описание характеристик оптимального лавинного эффекта и эмпирические зависимости характеристик лавинного эффекта от выбора окрестностей ячеек; показано, что клеточные автоматы обладают свойством размножения изменений.

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

5) Разработаны новые методы генерации псевдослучайных последовательностей; осуществлен синтез структуры генератора и обоснован выбор его параметров; указан способ обеспечения заданного периода выходной последовательности; разработана эталонная программная реализация генераторов на языке высокого уровня С#.

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

7) Разработана и изготовлена в виде устройства на ПЛИС высокоскоростная аппаратная реализация предложенных генераторов, превосходящая аналоги как по быстродействию, так и по эффективности.

Публикация результатов диссертации

1)Сухинин Б. М. Применение клеточных автоматов в криптографии // Интеллектуальные системы: Труды Восьмого международного симпозиума / Под ред. К. А. Пупкова. М., 2008. С. 509 - 512.

2) Сухинин Б. М. Применение классических и неоднородных клеточных автоматов при построении высокоскоростных генераторов псевдослучайных последовательностей // Проектирование и технология электронных средств. 2009. №3. С. 47-51.

3) Сухинин Б. М. О влиянии параметров локальной функции связи на распределение значений ячеек двоичных клеточных автоматов // Объединенный научный журнал. 2010. №8. С. 39 - 41.

4) Сухинин Б. М. О лавинном эффекте в клеточных автоматах // Объединенный научный журнал. 2010. №8. С. 41 - 46.

5) Сухинин Б.М. О новом классе генераторов псевдослучайных последовательностей на основе клеточных автоматов // Объединенный научный журнал. 2010. №8. С. 46 -49.

6)Сухинин Б.М. Практические аспекты оценки качества генераторов случайных последовательностей с равномерным распределением // Объединенный научный журнал. 2010. №8. С. 49 - 55.

7)Сухинин Б.М. Высокоскоростные генераторы псевдослучайных последовательностей на основе клеточных автоматов // Прикладная дискретная математика. 2010. №2. С. 34 - 41.

8)Сухинин Б.М. Высокоскоростные генераторы псевдослучайных последовательностей на основе клеточных автоматов // Прикладная дискретная математика. 2010. Приложение №3. С. 32 - 34.

9)Сухинин Б.М. Исследование характеристик лавинного эффекта в двоичных клеточных автоматах с равновесными функциями переходов // Наука и образование: электронное научно-техническое издание. 2010. №8. URL: http://technomag.edu.ru/doc/159565.html (дата обращения: 01.10.2010).

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

15

разование: электронное научно-техническое издание. 2010. №9. URL: http://technomag.edu.ru/doc/159714.html (дата обращения: 01.10.2010).

11)Сухинин Б. М. Генераторы псевдослучайных последовательностей на основе клеточных автоматов // Безопасные информационные технологии. Сборник тезисов докладов всероссийской научно-технической конференции (выпуск второй) / Под ред. В. А. Матвеева. М., 2011. С. 14 - 17.

12) Сухинин Б. М. О некоторых свойствах клеточных автоматов и их применении в структуре генераторов псевдослучайных последовательностей // Вестник МГТУ. Приборостроение. 2011. №2. С. 68 - 76.

13) Сухинин Б. М. Однородные двумерные булевы клеточные автоматы и их свойства применительно к генерации псевдослучайных последовательностей // Системы высокой доступности. 2011. Т. 7, №2. С. 39 - 41.

Подписано к печати 28.10.11. Заказ № 738 Объем 1,0 печ.л. Тираж 100 экз. Типография МГТУ им. Н.Э. Баумана 105005, Москва, 2-я Бауманская ул., д.5 (499) 263-62-01

Введение.

Краткая историческая справка.

Общая характеристика работы.

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

Структура диссертации.

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

1.1. Общие сведения.

1.1.1. Случайные последовательности и их свойства.

1.1.2. Подходы к получению равномерно распределенных случайных последовательностей.

1.2. Генераторы псевдослучайных последовательностей.

1.2.1. Формальное определение генератора псевдослучайных последовательностей

1.2.2. Классификация генераторов псевдослучайных последовательностей

1.2.3. Линейный конгруэнтный метод

1.2.4. Нелинейные конгруэнтные методы.

1.2.4.1. Метод «середины квадрата».

1.2.4.2. Метод умножения с переносом.

1.2.4.3. Квадратичный конгруэнтный метод.

1.2.4.4. Инверсивный (обратный) конгруэнтный метод.

1.2.5. Генераторы Фибоначчи.

-3Стр.

1.2.5.1. Классический генератор Фибоначчи.

1.2.5.2. Аддитивные генераторы Фибоначчи.

1.2.5.3. Мультипликативные генераторы Фибоначчи.

1.2.5.4. Генераторы Фибоначчи с операцией «исключающее или»

1.2.6. Генераторы на основе регистров сдвига.

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

1.2.6.2. Регистры сдвига с линейными обратными связями над полем

1.2.6.3. Обобщенные регистры сдвига.

1.2.6.4. Обобщенные регистры сдвига с закручиванием.

1.2.6.5. Вихрь Мерсенна.

1.2.6.6. Регистры сдвига с нелинейными обратными связями

1.2.7. Генераторы на основе клеточных автоматов.

1.2.7.1. Генераторы на основе одномерных клеточных автоматов

1.3. Методы улучшения свойств генераторов псевдослучайных чисел.

1.3.1. Применение фильтрующей функции.

1.3.1.1. Линейные регистры сдвига с фильтрующей функцией

1.3.2. Комбинация последовательностей.

1.3.2.1. Комбинация последовательностей при помощи бинарной операции.

1.3.2.2. Генератор Геффе.

1.3.3. Прореживание последовательностей.

1.3.3.1. Схема Ниффелера.

1.3.3.2. Сжимающий генератор.

1.4. О криптографически качественных генераторах псевдослучайных последовательностей

1.5. Выводы.

2. Исследование свойств клеточных автоматов.

2.1. Классические клеточные автоматы

2.1.1. Основные понятия и определения.

2.1.1.1. Одномерные булевы клеточные автоматы.

2.1.1.2. Двумерные булевы клеточные автоматы

2.1.2. Обзор имеющихся результатов для классических одномерных булевых клеточных автоматов

2.1.3. Локальная функция связи и равновероятность значений ячеек решетки.

2.1.4. Лавинный эффект.

2.1.4.1. Интегральная характеристика лавинного эффекта.

2.1.4.2. Пространственная характеристика лавинного эффекта

2.1.4.3. Зависимость характеристик лавинного эффекта от выбора окрестности.

2.1.5. Свойства периодичности

2.1.5.1. Временная периодичность клеточных автоматов.

2.1.5.2. Пространственная периодичность клеточных автоматов

2.1.5.3. Иные проявления периодичности.

2.2. Неоднородные клеточные автоматы.

2.2.1. Основные понятия и определения.

2.2.2. Локальная функция связи и равновероятность заполнения набора ячеек памяти.

2.2.3. Лавинный эффект.

2.2.3.1. Интегральная характеристика лавинного эффекта.

2.2.3.2. Зависимость характеристик лавинного эффекта от выбора окрестности.

2.2.4. Свойства периодичности

2.3. Выводы.

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

3.1. О параметрах клеточных автоматов и эффективности их реализации

3.2. Базовые генераторы.

3.2.1. Базовый генератор на основе классических клеточных автоматов

3.2.1.1. Обоснование выбора размерности решетки и типа окрестности

3.2.1.2. Обоснование выбор размера решетки и способа формирования выходной последовательности.

3.2.1.3. Обоснование выбора локальной функции связи

3.2.1.4. Обоснование выбора параметров PCJIOC и периода выходной последовательности

3.2.2. Базовый генератор на основе неоднородных клеточных автоматов

3.2.2.1. Обоснование выбора окрестности

3.2.2.2. Обоснование выбора размера клеточного автомата и способа формирования выходной последовательности

3.2.2.3. Обоснование выбора локальной функции связи

3.2.2.4. Обоснование выбора параметров PCJ10C и периода выходной последовательности.

3.2.3. Параметры и начальные значения генератора.

3.2.4. Алгоритм работы

3.2.5. Достоинства и недостатки базовых генераторов.

3.3. Комбинированные генераторы.

3.3.1. Параметры и начальные значения генератора.

3.3.2. Детализированная структура и алгоритм работы.

3.3.3. Достоинства и недостатки

3.4. Выводы.

4. Исследование статистических свойств выходных последовательностей генераторов.

4.1. Общие сведения.

4.1.1. Формальное описание процесса статистического тестирования

4.2. Набор статистических тестов NIST

4.2.1. Краткое описание статистических тестов.

4.2.2. Реализация набора статистических тестов NIST.

4.3. Методика проведения и результаты статистического тестирования

4.4. Выводы.

5. Высокоскоростная аппаратная реализация разработанных генераторов.

5.1. Общие сведения.

5.2. Описание реализации.

5.2.1. Блок Generator — реализация генератора.

5.3. Характеристики прототипов аппаратной реализации

5.4. Сравнение быстродействия и эффективности разработанной аппаратной реализации и существующих аналогов.

5.5. Выводы.

Краткая историческая справка

Случайные последовательности широко используются в самых различных областях. Исторически их применение было связано с развитием теории игр и использованием методов Монте-Карло для численного решения математических задач.

До середины XX в. случайные последовательности имитировались при помощи простейших случайных экспериментов: бросания монеты или игральной кости, извлечения шаров из Урны, раскладывания карт и т.д. В 1927 г. английским ученым Леонардом Типпетом впервые были опубликованы таблицы [77], содержащие свыше 40 ООО случайных цифр, «произвольно извлеченных из отчетов о переписи населения».

Позже были разработаны механические генераторы случайных чисел. Первая такая машина была использована в 1939 г. Кендаллом и Бабинг-тон-Смитом для построения таблицы [41], содержащей 100 000 случайных чисел.

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

К концу XX в. спрос на генераторы случайных последовательностей с заданными вероятностными распределениями, а также на сами случайные последовательности настолько возрос, что за рубежом стали появляться научно-производственные фирмы, занимающиеся производством и продажей больших массивов случайных чисел. Например, в мире с 1996 г. распространяется компакт-диск «The Marsaglia random number CDROM» [51], который содержит 4,8 млрд. «истинно случайных» бит, а в сети Интернет можно найти массивы случайных чисел, полученные в результате измерения атмосферных шумов (Random.Org, [70]) или регистрации радиоактивного распада (HotBits, [36]).

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

Поскольку любая программа описывает некоторый детерминированный алгоритм, получить истинно случайные числа с ее помощью невозможно. Джон фон Нейман по этому поводу отмечал, что «каждый, кто использует арифметические методы генерирования случайных чисел, без' условно, грешит» [79]. Последовательности, полученные при помощи подобных генераторов, не являются истинно случайными, однако обладают схожими (в идеальном случае — неотличимыми) свойствами, а потому носят название псевдослучайных.

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

Общая характеристика работы

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

Актуальность проблемы. Актуальность обусловлена широким применением псевдослучайных последовательностей в имитационном моделировании, методах Монте-Карло, криптографии, программировании и иных областях. Свой вклад в исследование псевдослучайных последовательностей и их генераторов внесли такие известные ученые, как А. Н. Колмогоров, Р. фон Мизес, Дж. фон Нейман, Дж. Марсалья, Д. Кнут, П. Лекваер, С. Вольфрам и др. Вопросы генерации псевдослучайных последовательностей широко обсуждаются на отечественных и зарубежных научных конференциях, таких как MCQMC, The Winter Simulation Conference, Crypto, EuroCrypt, FSE, CHES, Sibecrypt, РусКрипто и т.д.

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

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

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

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

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

- быстродействие и эффективность реализации генераторов на параллельных вычислительных устройствах, таких как ПЛИС, должны быть не ниже, чем у известных аналогов.

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

Для достижения поставленной цели были решены следующие задачи:

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

- исследованы свойства клеточных автоматов;

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

- экспериментально исследованы статистические свойства выходных последовательностей разработанных генераторов и подтверждено их соответствие предъявленным требованиям;

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

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

Методы исследований. Теоретические методы исследований включали применение теории конечных автоматов, теории графов, теории вероятности; эмпирические — проведение компьютерного моделирования и применение методов математической статистики для оценки свойств двоичных последовательностей. Для программной реализации был использован язык и платформа Microsoft .NET; разработка аппаратной реализации осуществлялась на языке описания цифровых схем VHDL, в качестве аппаратной^ платформы применялась ПЛИС Altera Cyclone II.

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

Научная новизна. Научная новизна работы заключается в следующем:

- исследовано влияние веса локальной функции связи на распределение значений ячеек памяти клеточных автоматов; сформулирован, доказан и подтвержден экспериментально критерий сохранения равномерности распределения;

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

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

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

Большинство теоретических результатов получено для общего случая п-мериых классических клеточных автоматов с произвольным радиусом локальности и неоднородных клеточных автоматов с произвольной мощностью окрестности; для важного класса двумерных булевых клеточных автоматов также получены частные результаты.

Практические результаты. Практические результаты включают в себя:

- разработку эталонной программной реализации предложенных генераторов с использованием объектно-ориентированного подхода на языке высокого уровня С#; • ,

- разработку аппаратной реализации предложенных генераторов на языке УНБЬ, обеспечивающей выработку псевдослучайной последовательности со скоростью 23,8 Гбит/с на тактовой частоте 100 МГц и превосходящей современные аналоги как по быстродействию, так и по эффективности;

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

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

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

Публикация и апробация результатов. Результаты исследований опубликованы в тринадцати научных работах, из них шесть — в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК Минобр-науки РФ. Все публикации без соавторов.

Основные результаты исследований докладывались и обсуждались на 9-ой (2007 г.) и 12-ой (2010 г.) ежегодных международных конференциях РусКрипто (г. Москва), научно-исследовательском семинаре «Защита информации: аспекты теории и вопросы практических приложений» МГТУ им. Н.Э. Баумана (г. Москва, 2010 г.), 9-ой сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография» (г. Тюмень, 2010 г.), всероссийской научно-технической конференции «Безопасные информационные технологии» (г. Москва, 2010 г.), научном семинаре кафедры Криптологии и дискретной математики НИЯУ «МИФИ» (г. Москва, 2011 г.).

Результаты исследований внедрены в учебный процесс кафедры «Информационная безопасность» Московского государственного технического университета им. Н. Э. Баумана и кафедры «Комплексная защита информации» Омского государственного технического университета, а также использованы в научно-производственной деятельности ЗАО «Научно-производственное предприятие «Безопасные информационные технологии».

ПОСТАНОВКА ЗАДАЧИ

Случайной равномерно распределенной двоичной последовательностью называется бесконечная двоичная последовательность ах, а^ ■ ■удовлетворяющая следующим свойствам:

1) для любого натурального числа п е N и произвольных значений индексов 1 ^ ¿1 < ¿2 < . < гп случайные величины ., а1п независимы в совокупности;

2) для любого натурального числа г Е N случайная величина аг имеет равномерное на множестве {0; 1} распределение вероятностей, т.е. Рг[а, = 0] = Рг[^ = 1] = 1/2.

Генератором псевдослучайных двоичных последовательностей (ГПСП) формально назовем детерминированное отображение д : {0;1}°° множества 5 начальных состояний генератора на множество бесконечных двоичных последовательностей, также называемых выходными псевдослучайными двоичными последовательностями (ПСП).

В диссертационной работе ставится задача разработать и реализовать (в т. ч. на аппаратном уровне) алгоритмы, реализующие отображение 0 и отвечающие следующим требованиям:

1) выходные ПСП должны обладать большим периодом, превосходящим требуемое на практике значение;

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

При этом:

1) алгоритмы должны быть основаны на использовании клеточных автоматов;

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

Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и шести приложений.

Выводы и заключение

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

В процессе диссертационных исследований были получены следующие результаты:

1) сформулированы требования, предъявляемые к генераторам псевдослучайных последовательностей;

2) проведен аналитический обзор наиболее распространенных генераторов псевдослучайных последовательностей, выявлены их основные достоинства и недостатки; рассмотрены методы улучшения статистических свойств выходных последовательностей; составлена классификация методов генерации псевдослучайных последовательностей;

3) исследовано влияние веса локальной функции связи на распределение значений ячеек памяти клеточных автоматов; сформулирован, доказан и подтвержден эмпирически критерий сохранения равномерности распределения;

4) впервые сформулировано понятие лавинного эффекта в клеточных автоматах, введены его числовые характеристики; получено теоретическое описание характеристик оптимального лавинного эффекта и эмпирические зависимости характеристик лавинного эффекта от выбора окрестностей ячеек; показано, что клеточные автоматы обладают свойством размножения изменений;

5) впервые введено и исследовано понятие пространственного периода в классических клеточных автоматах; сформулировано и доказано необходимое условие существования пространственного периода; показано, что нетривиальный пространственный период существенно снижает верхнюю границу периода последовательности внутренних состояний;

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

7) исследованы статистические свойства выходных последовательностей разработанных генераторов; определены конкретные локальные функции связи и окрестности ячеек клеточных автоматов, обеспечивающие хорошие статистические свойства выходных последовательностей; подтверждено соответствие статистических свойств современным требованиям; разработан программный комплекс автоматизации процесса статистического тестирования;

8) разработана эталонная программная реализация предложенных генераторов на> языке высокого уровня С#;

9) разработана и изготовлена в виде устройства на ПЛИС высокоскоростная аппаратная реализация предложенных генераторов, превосходящая аналоги как по быстродействию, так и по эффективности. Теоретическая значимость исследований заключается в разработке новых методов генерации псевдослучайных последовательностей и получении новых результатов в области теории клеточных автоматов. Практическая ценность обусловлена превосходством разработанных генераторов над существующими аналогами как по быстродействию, так и по эффективности реализации.

Внедрение разработанных генераторов целесообразно осуществлять в организациях, широко применяющих имитационное моделирование и методы Монте-Карло, таких как ВЦ РАН и НИВЦ МГУ.

Перспективным направлением дальнейших исследований является оценка возможности и эффективности реализации предложенных генераторов псевдослучайных последовательностей на основе клеточных автоматах на широко распространенных вычислительных устройствах с параллельной архитектурой, таких как графические процессоры (GPU). В случае положительного результата рассматриваемые генераторы могут быть использованы в большинстве бытовых вычислительных систем без применения дополнительного оборудования. Кроме того, представляется целесообразным рекомендовать проведение дополнительных исследований в области криптографических качеств предложенных генераторов в специализированных организациях, в частности в ИКСИ ФСБ РФ.

1. Берлекэмп Э. Алгебраическая теория кодирования: Пер. с англ. М.: Мир, 1972. 478 с.

2. Варфоломеев А. А., Жуков А. Е., Пудовкина М. А. Поточные криптосистемы. Основные свойства и методы анализа стойкости: Учеб. пособие. М.: ПАИМС, 2000. 272 с.

3. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования: Гос. стандарт. Введ. 01.07.1990. URL: http : //protect. gost. ru/document;. aspx?control=7&id=139177 (дата обращения: 01.03.2011).

4. Иванов M. А., Чугунков И. В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. М.: КУДИЦ-Образ, 2003. Кн. 2. 240 с.

5. Кельтон В., Лоу А. Имитационное моделирование. Классика Com.pu.ter Science: 3-е изд. СПб.: Питер, 2004. 848 с.

6. Кнут Д. Искусство программирования. Получисленные алгоритмь.1* 3-е изд.: Пер. с англ.: Учеб. пособие. М.: Издательский дом «Вильяме», 2001. 832 с.

7. Лидл Р., Нидеррайтер Г. Конечные поля: Пер. с англ. М.: Мир, Ю88. Т. 1. 430 с.

8. Сергиенко А. М. VHDL для проектирования вычислительных устройств. Киев: ЧП «Корнейчук» ООО «ТИД "ДС"», 2002. 208 с.

9. Теория и применение псевдослучайных сигналов / А. И. Алексеев и др. М.: Наука, 1969. 365 с.

10. Тоффоли Т., Марголус Н. Машины клеточных автоматов: Пер. с англ. М.: Мир, 1991. 280 с.

11. Харин Ю. С., Берник В. И., Матвеев Г. В. Математические основы криптологии: Учеб. пособие. Минск: БГУ, 1999. 319 с.

12. Харин Ю. С., Степанова М. Д. Практикум на ЭВМ по математической статистике. Минск: Университетское, 1987. 305 с.

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

14. Шнайер Б., Фергюсон Н. Практическая криптография: Пер. с англ. М.: Издательский дом «Вильяме», 2005. 424 с.

15. Blum L., Blum М., Shub М. A simple unpredictable pseudo-random number generator // SI AM Journal on Computing. 1986. Vol. 15. P. 364-383.

16. Brent R. On the periods of generalized Fibonacci recurrences // Mathematics of Computation. 1994. Vol. 63. P. 389-401.

17. Chou W. The period lengths of inversive congruential recursions // Acta Arithmetica. 1995. Vol. 73. P. 325-341.

18. Couture R., L'Ecuyer P. Distribution properties of multiply-with-carry random number generators // Mathematics of Computation. 1997. Vol. 66. P. 591-607.

19. Cyclone II Device Handbook / Altera corp. 2007. Vol. 1. 470 p. URL: http://www.altera.com/literature/hb/cyc2/cyc2cii5vl.pdf (дата обращения: 01.03.2011).

20. On the lattice structure of a nonlinear generator with modulus 2n / J. Eichenauer et al. // Journal of Computational and Applied Mathematics. 1990. Vol. 31. P. 81-85.

21. Eichenauer J., Lehn J. A non-linear congruential pseudo-random number generator // Statistical Papers. 1986. Vol. 27. P. 315-326.

22. Eichenauer J., Lehn J., Topuzoglu A. A nonlinear congruential pseudorandom number generator with power of two modulus // Mathematics of Computation. 1988. Vol. 51. P. 757-759.

23. Farmer D., Toffoli Т., Wolfram S. Preface to cellular automata // Cellular Automata: Proc. Interdisciplinary Workshop. Los Alamos, 1983. P. vii-xii.

24. Feistel H. Cryprography and computer privacy // Scientific American. 1973. Vol. 228. P. 15-23.

25. Gardner M. The fantastic combinations of John Conway's new solitaire game «Life» // Scientific American. 1970. Vol. 223. P. 120-123.

26. Gollmann D. Pseudo random properties of cascade connections of clock controlled shift registers // EUROCRYPT'84: Conf. proc. Paris, 1984. P. 93-98.

27. Gollmann D., Chambers W. Lock-in eifect in cascades of clock-controlled shift registers // EUROCRYPTJ88: Conf. proc. Davos, 1988. P. 341-432.

28. Gollmann D., Chambers W. A cryptoanalysis of Step^-cascades // EUROCRYPT'89: Conf. proc. Houthalen, 1989. P. 680-687.

29. Greenberger M. An a priori determination of serial correlation in computer generated random numbers // Mathematics of Computation. 1961. Vol. 15. P. 383-389.

30. Gustavson F. Analysis of the Berlekamp-Massey linear feedback shift-register synthesis algorithm // IBM Journal of Research and Development. 1976. Vol. 20. P. 204-212.

31. Hammer P. The mid-square method of generating digits // Monte Carlo Method: Symp. proc (Los Angeles, 1949). Washington, 1951. Vol. 12. P. 33.

32. Hechenleitner В. Defects in random number routines of well-known network simulators and appropriate improvements: Ph. D. dissertation. Salzburg: School of Scientific Computing of the University of Salzburg, 2004. 135 p.

33. Hell M., Johansson Т., Meier W. Grain —A stream cipher for constrained environments // The eSTREAM Project. 2005. 14 p. URL: http://www. ecrypt.eu.org/stream/p3ciphers/grain/Grainp3.pdf (дата обращения: 01.03.2011).

34. Hotbits: Genuine random numbers, generated by radioactive decay: web site. URL: http://www.fourmilab. ch/hotbits (дата обращения: 01.03.2011).

35. Hull Т.Е., Dobell A.R. Random number generators // SIAM Review. 1962. Vol. 4. P. 230-254.

36. IEEE Std 1076-2002. VHDL Language Reference Manual: IEEE Standard. 2002. URL: http://www.ece.gatech.edu/academic/ courses/spring2007/ece4170/Lectures/Standards/IEEE VHDLLangRefManual2002.pdf (дата обращения: 01.03.2011)

37. James F. A review of pseudorandom number generators // Computer

38. Physics Communications. 1990. Vol. 60. P. 329-344.

39. Kaminsky A. Cellular automata based stream ciphers: Lecture notes. Rochester: Rochester Institute of Technology, 2004. 15 p. URL: http: //www.cs.rit.edu/~ark/lectures/casc01/casc01.pdf(дата обращения: 01.03.2011).

40. Kendall M., Babington-Smith B. Tables of random sampling numbers: Reprint. London: Cambridge University Press, 1961. 60 p. (First published 1939).

41. Key E. An analysis of the structure and complexity of nonlinear binary sequence generators // IEEE Transactions on Information Theory. 1976. Vol. 22. P. 732-736.

42. L'Ecuyer P. Uniform random number generation // Annals of Operations Research. 1994. Vol. 53. P. 77-120.

43. L'Ecuyer P., Proulx R. About polynomial-time «unpredictable» generators // Winter Simulation Conference: Conf. proc. Washington, 1989. P. 467476.

44. Lehmer D. Mathematical methods in large-scale computing units //Large-Scale Digital Calculating Machinery: Symp. proc. Harvard, 1951. P. 141-146.

45. Lewis Т., Payne W. Generalized feedback shift register pseudorandom number algorithms // Journal of ACM. 1973. Vol. 21. P. 456-468.

46. Marsaglia G. Random numbers fall mainly in the planes // Proceedings of the National Academy of Sciences of USA. 1968. Vol. 61. P. 25-28.

47. Marsaglia G. The structure of linear congruential sequences // Applications of Number Theory to Numerical Analysis. Academic Press, 1972. P. 249285.

48. Marsaglia G. A current view of random number generators // Computing

49. Science and Statistics: Symp. proc. Atlanta, 1984. P. 3-10.

50. Marsaglia G. The mathematics of random number generators // Proceedings of Symposia on Applied Mathematics. 1992. Vol. 46. P. 73-89.

51. The Marsaglia random number CDROM including the DIEHARD battery of tests of randomness web site. / G. Marsaglia; Florida State University. [1995 ]. URL: http://stat.fsu.edu/pub/diehard (дата обращения: 01.03.2011).

52. Marsaglia G. Random number generators // Journal of Modern Applied Statistical Methods. 2003. Vol. 2. P. 2-13.

53. Massey J. Shift register synthesis and BCH decoding // IEEE Transactions on Information Theory. 1969. Vol. 15. P. 122-127.

54. Matsumoto M., Kurita Y. Twisted GFSR generators // ACM Transactions on Modeling and Computer Simulation. 1992. Vol. 2. P. 179-194.

55. Matsumoto M., Kurita Y. Twisted GFSR generators II // ACM Transactions on Modeling and Computer Simulation. 1994. Vol. 4. P. 254266.

56. Matsumoto M., Nishimura T. Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator // ACM Transactions on Modeling and Computer Simulation. 1998. Vol. 8. P. 3-30.

57. Maurer U. A universal statistical test for random bit generators // Journal of Cryptology. 1992. Vol. 5. P. 89-105.

58. Maximov A. Some Words on Cryptanalysis of Stream Ciphers: Ph. D. dissertation. Lund: Lund University, 2006. 256 p.

59. Menezes A., von Oorschot P., Vanstone S. Handbook of Applied Cryptography. Boca Raton: CRC Press, 1996. 816 p.

60. Mertens S., Bauke H. Entropy of pseudo random number generators // Physical Review E. 2004. Vol. 69. 4 p. (Art. 055702 preprint).

61. A Million Random Digits with 100,000 Normal Deviates / The RAND Corporation. New York: Free Press, 1955. 625 p.

62. Niederreiter H. The serial test for congruential pseudorandom numbers generated by inversions // Mathematics of Computation. 1989. Vol. 52. P. 135-144.

63. NIST SP 800-38A. Recommendation for block cipher modes of operation // NIST.gov-Computer Security Division. 2001. 66 p. URL: http: //csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf (дата обращения: 01.03.2011).

64. Nyffeler P. Binäre Automaten und ihre Linearen Rekursionen: Ph. D. dissertation. Bern: University of Bern, 1975. 113 s.

65. Packard N., Wolfram S. Two-dimensional cellular automata // Journal of Statistical Physics. 1985. Vol. 38. P. 901-946.

66. Preneel В., de Cannière С. Trivium specifications // The eS-TREAM Project. 2005. 7 p. URL: http://www.ecrypt.eu.org/stream/ p3ciphers/trivium/triviump3.pdf (дата обращения: 01.03.2011).

67. Publications by Stephen Wolfram // Stephen Wolfram: Official Website. URL: http://www.stephenwolfram.com/publications (дата обращения: 01.03.2011).

68. Random number generation // Wolfram Mathematica 8 Documentation. URL: http://reference.wolfram.com/mathematica/tutorial/ RandomNumberGeneration.html (дата обращения: 01.03.2011).

69. Random.org —True Random Number Service web site. URL: http:// www.random.org (дата обращения: 01.03.2011).

70. Rogawski M. Hardware evaluation of eSTREAM candidates: Grain, Lex, Mickeyl28, Salsa20 and Trivium // The eSTREAM Project. 2007. 10 p. URL: http: //www. ecrypt. eu. org/stream/papersdir/2007/025 . pdf (дата обращения: 01.03.2011).

71. Shannon С. A mathematical theory of communication // The Bell System Technical Journal. 1948. Vol. 27. P. 379-423, 623-656.

72. Coppersmith D., Krawczyk H., Mansour Y. The shrinking generator // Lecture Notes in Computer Science. 1993. Vol. 773. P. 22-39.

73. Smeets B. A note on sequences generated by clock controlled shift registers // EUROCRYPT'85: Conf. proc. Linz, 1985. P. 142-148.

74. Thomson W. A modified congruence method of generating pseudo-random numbers // Computer Journal. 1958. Vol. 1. P. 83-86.

75. Watson E. Primitive polynomials (mod 2) // Mathematics of Computation. 1962. Vol. 16. P. 368-369.

76. Wolfram S. Cellular automata // Los Alamos Science. 1983. Vol. 9. P. 2-21.

77. Wolfram S. Cryptography with cellular automata // Lecture Notes in Computer Science. 1986. Vol. 218. P. 429-432.

78. Wolfram S. Random sequence generation by cellular automata // Advances in Applied Mathematics. 1986. Vol. 7. P. 123-169.

79. Wolfram S. Cellular automation supercomputing // High-speed computing: scientific applications and algorithm design. Champaign: University of Illinois Press, 1988. P. 40-48.

80. Wolfram S. A New Kind of Science. Champaign: Wolfram Media, 2002. 1192 p.