Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей на основе клеточных автоматов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Сухинин, Борис Михайлович

• Сухинин, Борис Михайлович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Сухинин, Борис Михайлович

Введение.

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

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

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

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

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). В случае положительного результата рассматриваемые генераторы могут быть использованы в большинстве бытовых вычислительных систем без применения дополнительного оборудования. Кроме того, представляется целесообразным рекомендовать проведение дополнительных исследований в области криптографических качеств предложенных генераторов в специализированных организациях, в частности в ИКСИ ФСБ РФ.

Список литературы диссертационного исследования кандидат технических наук Сухинин, Борис Михайлович, 2011 год

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.