Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 24
Текст из файла (страница 24)
Тем не. менее, оно может быть увеличено до33,4 Гбит/с для. генераторов на основе классических клеточных автоматов и. до 35;5 Рбит/с для генераторов: на основе неоднородных клеточныхавтоматов г за счет увеличения тактовой; частоты без изменения самой реализации.5.4.СРАВНЕНИЕБЫСТРОДЕЙСТВИЯ^ И Э Ф Ф Е К Т И В Н О С Т ИР А З Р А Б О Т А Н Н О Й АППАРАТНОЙ Р Е А Л И З А Ц И И И СУЩЕС Т В У Ю Щ И Х АНАЛОГОВ Г..•",'.•В табл.
10 представлено сравнение быстродействия^ аппаратной реализациифазработанных алгоритмов- генерации; псевдослучайных последовательностей (TD12 и ND32) и алгоритмов, представленных на европейскийконкурс eSTREAM, направленный на поиск новых перспективных поточных шифров. Выбор для сравнения алгоритмов поточного шифрованияобусловлен.тем,.что К; ним как к генераторам псевдослучайных последовательностей предъявляются высокие требования как по быстродействию,так и по статистическим качествам; выходных последовательностей. Крометого, поскольку конкурс eSTREAM проводился в 2005-2008 гг., сравнениеосуществляется с реализациями, соответствующими современному уровню технического развития: В качестве эталонного-алгоритма.в сравнениивыступает AES (Advanced, Encryption Standard) — стандарт шифрования, •принятый в США.
Данные о быстродействии реализаций алгоритмов получены из [33].Сравнение проводилось по двум показателям: абсолютному быстродействию, отражающему скорость выработки выходной последовательно--157-Таблица 10.Сравнение быстродействия аппаратных реализаций разработанныхгенераторов и некоторых существующих аналоговГенераторМакс, тактоваяАбсолютноеПриведенноечастота,быстродействие, быстродействиМГцМбит/сМбит/сAES (OFB)AchterbahnGrainMICKEYMOSQUITOSFINKS+TriviumVESTZK-Crypt1822503003082651673122862035284664475287739124218 5684 2576 0572901861492932797445 95114882 983TD12ND321401493418036 3772441424414сти на максимальной тактовой частоте, и приведенному быстродействию,показывающему скорость выработки выходной последовательности на частоте 100 МГц.Из таблицы хорошо видно, что реализации разработанных алгоритмовTD12 и ND32 значительно превосходят аналоги.
Так, например, реализация алгоритма ND32 по показателю абсолютного быстродействия превосходит наиболее быстрый из представленных на конкурс eSTREAM алгоритмTrivium в 1,96 раз, а по показателю приведенного быстродействия — в 4,10раз.Помимо быстродействия важную роль играет эффективность аппаратной реализации, которая выражается в быстродействии на единицу аппаратных ресурсов (для FPGA корпорации Altera такой единицей являетсялогический элемент —LE).
Сравнение эффективности аппаратной реализации представлено в табл. 11. Данные о производительности и эффективности аппаратных реализаций алгоритмов AES, Grain, MICKEY и Triviumполучены из работы [71].-158Таблица 11.Сравнение эффективности аппаратных реализаций разработанныхгенераторов и некоторых существующих аналогов^Генераторт-,„АппаратныеБыстродействие,ресурсы,м 6 и т / с~ , ,Эффективность,м б и т / ( с . Ь Е )AESGrainMICKEYTrivium6113 44022016 3205 0535085377000,126,770,4123,31TD12ND323418036 3772189210841,5633,55Как видно из таблицы, наибольшую эффективность, значительно превосходящую аналоги, имеет реализация алгоритма ND32. Также необходимо отметить, что реализация алгоритма TD12 обладает средней эффективностью.5.5.
ВыводыОдним из наиболее перспективных подходов к построению аппаратных реализаций сложных цифровых систем является использование микросхем программируемой логики и, в частности, FPGA. В данной главебыла представлена структура аппаратной реализации разработанных ранее комбинированных генераторов псевдослучайных последовательностейна FPGA.Для генераторов TD12 на основе классических клеточных автоматови ND32 на основе неоднородных клеточных автоматов были построеныпрототипы аппаратной реализации на микросхеме FPGA Altera Cyclone II(EP2C35F672C6) и проведено их сравнение с современными аппаратнымиреализациями поточных шифров (как генераторов псевдослучайных последовательностей, к которым предъявляются наиболее строгие требованиякак по быстродействию, так и по статистическим свойствам выходных последовательностей). Сравнение показало, что оба прототипа существенно(в несколько раз) превосходят аналоги по скорости выработки выходной-159последовательности; кроме того, реализация генератора TD12 не ус*=м=\У*-*a ND32 значительно превосходит аналоги по эффективности, в ы р а ^ з Е ^ ^в быстродействии на единицу аппаратных ресурсов (рис.
5.3).11>160-Быстродействие•10340! Ш а максимальной тактовой частотеIs На тактовой частоте 100 МГц3418036 37730I18 56820106 0574 2570^?шGrainTriviumVESTZK-CryptтККлАшНКлАЭффективность4033,55353023,31252015106,77Ш501,560,41T//SSSJ/\MickeyGrainTriviumККлАНКлА5.3. Сравнение разработанного прототипа и генераторов, представленных на конкурс eSTREAM (ККлА и НКлА — генераторы наоснове классических и неоднородных клеточных автоматов соответственно)-161-ВЫВОДЫ И ЗАКЛЮЧЕНИЕДиссертационная работа была посвящена разработке новых методовгенерации псевдослучайных равномерно распределенных двоичных последовательностей, основанных на использовании клеточных автоматов.
К основным достоинствам разработанных методов относятся контролируемыйпериод и хорошие статистические свойства псевдослучайных последовательностей, эффективность и высокое быстродействие аппаратной реализации генераторов.В процессе диссертационных исследований были получены следующиерезультаты:1) сформулированы требования, предъявляемые к генераторам псевдослучайных последовательностей;2) проведен аналитический обзор наиболее распространенных генераторов псевдослучайных последовательностей, выявлены их основные достоинства и недостатки; рассмотрены методы улучшения статистических свойств выходных последовательностей; составлена классификация методов генерации псевдослучайных последовательностей;3) исследовано влияние веса локальной функции связи на распределениезначений ячеек памяти клеточных автоматов; сформулирован, доказан и подтвержден эмпирически критерий сохранения равномерностираспределения;4) впервые сформулировано понятие лавинного эффекта в клеточных автоматах, введены его числовые характеристики; получено теоретическое описание характеристик оптимального лавинного эффекта и эмпирические зависимости характеристик лавинного эффекта от выбора окрестностей ячеек; показано, что клеточные автоматы обладают-162свойством размножения изменений;5) впервые введено и исследовано понятие пространственного периода вклассических клеточных автоматах; сформулировано и доказано необходимое условие существования пространственного периода; показано,что нетривиальный пространственный период существенно снижаетверхнюю границу периода последовательности внутренних состояний;6) разработаны новые методы генерации, псевдослучайных последовательностей; осуществлен синтез структуры генератора и обоснован выбор его параметров при использовании как классических, так и неоднородных клеточных автоматов; указан способ обеспечения заданногопериода выходной последовательности;7) исследованы статистические свойства выходных последовательностейразработанных генераторов; определены конкретные локальные функции связи и окрестности ячеек клеточных автоматов, обеспечивающие хорошие статистические свойства выходных последовательностей;подтверждено соответствие статистических свойств современным требованиям; разработан программный комплекс автоматизации процессастатистического тестирования;8) разработана эталонная программная реализация предложенных генераторов на> языке высокого уровня С # ;9) разработана и изготовлена в виде устройства на ПЛИС высокоскоростная аппаратная реализация предложенных генераторов, превосходящая аналоги как по быстродействию, так и по эффективности.Теоретическая значимость исследований заключается в разработке новых методов генерации псевдослучайных последовательностей и полученииновых результатов в области теории клеточных автоматов.
Практическаяценность обусловлена превосходством разработанных генераторов над существующими аналогами как по быстродействию, так и по эффективностиреализации.Внедрение разработанных генераторов целесообразно осуществлять ворганизациях, широко применяющих имитационное моделирование и методы Монте-Карло, таких как ВЦ РАН и НИВЦ МГУ.Перспективным направлением дальнейших исследований является-163оценка возможности и эффективности реализации предложенных генераторов псевдослучайных последовательностей на основе клеточных автоматах на широко распространенных вычислительных устройствах с параллельной архитектурой, таких как графические процессоры (GPU).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
