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

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

Текст из файла (страница 3)

Практические результаты включают в себя:- разработку эталонной программной реализации предложенных гене­раторов с использованием объектно-ориентированного подхода на язы­ке высокого уровня С # ;•,- разработку аппаратной реализации предложенных генераторов наязыке VHDL, обеспечивающей выработку псевдослучайной последо­вательности со скоростью 23,8 Гбит/с на тактовой частоте 100 МГц ипревосходящей современные аналоги как по быстродействию, так и поэффективности;- разработку программного комплекса автоматизации процесса иссле­дования статистических свойств выходных псевдослучайных последо­вательностей генераторов на основе клеточных автоматов.Теоретическая и практическая значимость.

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

Внедрение предложенных генераторов в при­кладные системы позволит увеличить их быстродействие, а также повы­сить эффективность за счет хороших статистических свойств и контроли­руемого периода вырабатываемых псевдослучайных последовательностей.Публикация и апробация результатов. Результаты исследований опуб­ликованы в тринадцати научных работах, из них шесть — в ведущих рецен­зируемых научных журналах и изданиях, рекомендованных ВАК Минобрнауки РФ. Все публикации без соавторов.Основные результаты исследований докладывались и обсуждались на9-ой (2007 г.) и 12-ой (2010 г.) ежегодных международных конференцияхРусКрипто (г.

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

Н. Э. Баумана и кафедры «Комплексная защита инфор­мации» Омского государственного технического университета, а также ис­пользованы в научно-производственной деятельности ЗАО «Научно-произ­водственное предприятие «Безопасные информационные технологии».-16ПОСТАНОВКА ЗАДАЧИСлучайной равномерно распределенной двоичной последовательно­стью называется бесконечная двоичная последовательность а\, о^,. •., удо­влетворяющая следующим свойствам:1) для любого натурального числа п G N и произвольных значений ин­дексов 1 ^ i\ < г2 < ... < гп случайные величины а:^, ctij 2 ,..., а г „независимы в совокупности;2) для любого натурального числа г Е N случайная величина аг име­ет равномерное на множестве {0; 1} распределение вероятностей, т.е.Рфг= 0] = Рт{а{ = 1] = 1/2.Генераторомпсевдослучайныхдвоичныхпоследовательностей(ГПСП) формально назовем детерминированное отображение0 : S-)> {0; 1}°°множества S начальных состояний генератора на множество бесконечныхдвоичных последовательностей, также называемых выходными псевдослу­чайными двоичными последовательностями (ПСП).В диссертационной работе ставится задача разработать и реализовать(в т.

ч. на аппаратном уровне) алгоритмы, реализующие отображение Q иотвечающие следующим требованиям:1) выходные ПСП должны обладать большим периодом, превосходящимтребуемое на практике значение;2) выходные ПСП должны быть статистически неотличимы от случай­ных равномерно распределенных двоичных последовательностей, чтодолжно подтверждаться успешным прохождением наборов специали­зированных статистических тестов.При этом:1) алгоритмы должны быть основаны на использовании клеточных ав­томатов;2) реализация алгоритмов на параллельных вычислительных устрой­ствах (например, аппаратная) должна обладать высоким быстродей­ствием, превосходящем известные аналоги.-17СТРУКТУРА ДИССЕРТАЦИИДиссертационная работа состоит из введения, пяти глав, заключения,списка литературы и шести приложений.Первая глава посвящена обзору основных существующих алгоритмовгенерации псевдослучайных последовательностей с равномерным распре­делением и анализу их достоинств и недостатков.

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

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

Выбор параметров клеточных автоматов осу­ществляется на основании результатов, полученных во второй главе.В четвертой главе проводится экспериментальное исследование ста­тистических свойств выходных последовательностей разработанных гене--18раторов при помощи специализированного набора статистических тестовНационального института стандартов и технологии США. По результатамтестов выбираются конкретные параметры клеточных автоматов, исполь­зуемых в структуре генераторов, а также делается заключение о возмож­ности применения разработанных алгоритмов.Пятая глава посвящена построению высокоскоростной аппаратной ре­ализации разработанных алгоритмов. В частности, описывается структу­ра такой реализации и приводятся ее характеристики для двух комбини­рованных генераторов, выходные последовательности которых обладаютнаилучшими статистическими свойствами.

Также в этой главе проводитсясравнение разработанной аппаратной реализации с современными анало­гами и делается вывод о существенном превосходстве предложенных гене­раторов на основе клеточных автоматов.В приложениях приводятся дополнительные сведения, включение ко­торых в основной текст диссертации автор счел нецелесообразным.-19-ГЛАВА 1О Б З О Р МЕТОДОВ ГЕНЕРАЦИИПСЕВДОСЛУЧАЙНЫХ1.1.ПОСЛЕДОВАТЕЛЬНОСТЕЙОБЩИЕ СВЕДЕНИЯ1.1.1.С Л У Ч А Й Н Ы Е П О С Л Е Д О В А Т Е Л Ь Н О С Т И И ИХ СВОЙСТВАПрежде всего отметим, что проблема генерации случайной последова­тельности с произвольным вероятностным законом распределения сводит­ся с помощью известных методов обратной функции, исключения и ком­позиции (см., например, [5,13]) к генерации т.н.

базовой случайной по­следовательности — равномерно распределенной на дискретном множествеО — {tu\,uj2,. • • ,w/v}, |£2| = N, случайной бесконечной последовательно­сти вида а = ai,a2,...,где оц Е О.. Такая последовательность должнаудовлетворять следующим двум фундаментальным требованиям:1) для любого числа п Е N и произвольных значений индексов 1 ^ t\ <...

Характеристики

Список файлов диссертации