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

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

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

Генератор ГеффеДлинырегистровLi, L2 и Lz выбираютсячто обеспечивает максимальный период выходнойLTmax =Lвзамнопростыми,последовательностиL(2 i-l)(2 *-l)(2 *-l).Несмотря на то, что использование перемешивающей функции длякомбинирования выходов регистров позволило существенно увеличить пе­риод и улучшить статистические свойства вырабатываемой последователь­ности, генератор оказался подвержен корреляционной атаке [2]. Как видноиз табл. 2, значение функции F(x, у, z) совпадает со значениями аргумен­тов х и у в 75% случаев.

Таким образом, генератор Геффе является непри­годным для использования в криптографии.Таблица 2.Значения функции усложнения F(x, у, z) генератора ГеффеZ000001010F000XУ0111001010110111Совпадение 6/8 = 0,75Совпадение 6/8 = 0,75Совпадение 4/8 = 0,501Следует отметить, что корреляционным атакам подвержены и многиедругие комбинированные генераторы псевдослучайных последовательно­стей [2].-591.3.3.

П Р О Р Е Ж И В А Н И Е П О С Л Е Д О В А Т Е Л Ь Н О С Т Е ЙЕще одним методом улучшения статистических свойств псевдослу­чайных последовательностей является их прореживание. Пусть а=—ai, «2j • • • псевдослучайная последовательность, полученная при помощинекоторого генератора, и t\, £2, • • • G N (1 ^ t\ < £2 < ...) — не зависящая ота последовательность индексов.

Тогда последовательность/3 = atl,at2,...,-получаемая из а путем ее «прореживания», является равномерно распре­деленной, если исходная последовательность также являлась равномернораспределенной (см. раздел 1.1.1). При этом прореживание позволяет улуч­шить статистические свойства псевдослучайной последовательности и сде­лать ее менее предсказуемой за счет «разрушения» корреляций между раз­личными членами.К недостаткам метода прореживания можно отнести снижение быст­родействия генератора (за счет «отбрасывания» некоторых выходных зна­чений), а также неравномерность скорости выработки псевдослучайной по­следовательности.Примером практической реализации метода прореживания являетсясхема, предложенная Ниффелером в 1975 г. [65] и основанная на использо­вании РСЛОС с управляемым сдвигом.1.3.3.1. СХЕМА Н И Ф Ф Е Л Е Р АГенератор, построенный по схеме Ниффелера, включает в себя (см.рис.

1.8):- два регистра сдвига с линейными обратными связями R\ и R.2, одиниз которых вырабатывает исходную псевдослучайную последователь­ность, а второй — последовательность, определяющую индексы проре­живания, над полями ¥qi и ¥q2 соответственно;- функцию /, реализующую отображение / : ¥qi —> N.Начальное состояние генератора определяется начальными заполне­ниями регистров Ri и it^.

Выход xt первого регистра преобразуется припомощи функции f{xt)и подается на вход тактирования второго регистра,определяя величину его сдвига, а выход второго регистра используется дляформирования членов выходной последовательности а = {cxt}.-60-РСЛОСЯхX,fЛ**)•'VTifi ГТГЛГ1 JX2пrK^JlW^a,Р и с . 1.8. Генератор НиффелераТаким образом, на каждом такте работы генератора выполняются сле­дующие шаги:1) регистр Ri сдвигается на одну позицию и формируется его выходноезначение Xt G F 9 l ;2) вычисляется значение функции f(xt)3) регистр i?2 сдвигается на f(xt)6 N;позиций и формируется его выходноезначение at G F g 2 , являющееся очередным членом выходной последо­вательности а генератора.Анализ свойств генератора, предложенного Ниффелером, был прове­ден Смитсом в работе [74].

Исследования показали, что при выполненииряда условий обеспечивается высокая линейная сложность выходной по­следовательности и ее хорошие статистические свойства.Развитие идей Ниффелера и более глубокий анализ различных вари­антов комбинации регистров сдвига с линейными обратными связями припостроении генераторов псевдослучайных последовательностей был про­веден Голлманом и Чэмберсом; результаты .исследований опубликованыв [27-29] и др.1.3.3.2. С Ж И М А Ю Щ И Й Г Е Н Е Р А Т О РНа методе прореживания также основан сжимающий генератор [73],предложенный в 1993 г. Генератор состоит из двух двоичных регистровсдвига с линейными обратными связями R\ и i? 2 , первый из которых яв­ляется управляющим, а второй вырабатывает псевдослучайную последо­вательность.Алгоритм работы сжимающего генератора основан на повторении сле­дующих шагов на каждой итерации:1) осуществляется сдвиг регистров R\ и R2 на одну позицию;-612) если на выходе Ri сформировалось значение 1, то на выход генератораподается выходное значение R2\3) если на выходе R\ сформировалось значение 0, то на выход генераторане подается ничего (т.

е. очередной член к выходной последовательно­сти генератора на текущем шаге не добавляется).Если регистры R\ и R2 имеют длины L\ и L2 соответственно и явля­ются М-генераторами, то верны следующие утверждения:- период выходной последовательности сжимающего генератора состав­ляет Т = (2L2 —1)2£'1~1, если длины регистров L\ и L2 взаимнопросты;- линейная сложность С(а) выходной последовательности генератораограничена неравенствомL2 • 2 L l ~ 2 < Ца)^L2-2L^\Основным недостатком сжимающего генератора является непостоян­ство скорости выработки псевдослучайной последовательности.1.4. О КРИПТОГРАФИЧЕСКИ КАЧЕСТВЕННЫХ ГЕНЕРАТО­РАХ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙВ криптографии генераторы псевдослучайных последовательностейиспользуются, прежде всего, в качестве генераторов гаммы в схемах по­точного шифрования информации.

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

Так, например, алгоритм Trivium [67] использует несколько реги­стров сдвига с нелинейными обратными связями, выход которых склады­вается при помощи операции «исключающее или», а алгоритм Grain [35] —комбинацию регистров сдвига с линейными и нелинейными обратными свя­зями.-62Кроме того существуют генераторы, не подходящие под приведеннуювыше классификацию: в алгоритме RC4 [14], например, используются пе­рестановки элементов 256-байтового массива памяти.Наконец, в качестве криптографически качественного генераторапсевдослучайныхпоследовательностеймогут использоваться блочныешифры в режиме гаммирования [3,64].Общим недостатком большинства криптографически качественных ге­нераторов псевдослучайных последовательностей является их недостаточ­ное для использования в современных информационных системах быстро­действие, что связано с повышенными требованиями к таким генераторами необходимостью использования дополнительных преобразований для вы­работки выходной последовательности.1.5.

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

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

С другой стороны, повышениебыстродействия за счет использования более простых конструкций приво­дит к снижению качества выходной последовательности.Требования к современным генераторам псевдослучайных последова­тельностей неуклонно возрастают по мере развития возможностей вычис­лительной техники, и существующие генераторы уже не полностью им со--63ответствуют (в первую очередь это касается быстродействия). Учитываяуровень и темпы развития информационных технологий, в настоящее вре­мя существует потребность в разработке новых методов генерации псевдо­случайных последовательностей, обеспечивающих одновременно высокоебыстродействие и хорошие статистические свойства, а для криптографи­ческих приложений — также удовлетворяющих требованию непредсказуе­мости.Таблица 3.Основные достоинства и недостатки различных генераторов псевдослучайных последовательностей№МетодДостоинстваНедостаткиКонгруэнтные методы1Линейный конгруэнтный методПростота реализации, высокоеЗначительные статистическиебыстродействиеотклонения, линейность,предсказуемость2Метод «середины квадрата» (вНизкие требования кМалый период, склонность кнастоящее время невычислительным ресурсам«зацикливанию» генератораВысокое быстродействие,Сводится кхорошие статистическиемультипликативномусвойстваконгруэнтному генератору,применяется)3Метод умножения с переносомотклонения в распределениистарших битов4Квадратичный конгруэнтныйХорошие статистическиеметодсвойства, непредсказуемость,может использоваться вкриптографииНизкое быстродействиеТаблица 3 — продолжение№5МетодДостоинстваИнверсивный (обратный)Хорошие статистическиеконгруэнтный методсвойстваНедостаткиНизкое быстродействиеГенераторы Фибоначчи67Классический генераторПлохие статистическиеФибоначчи (в настоящее времясвойства, линейностьне применяется)преобразованияАддитивный генераторВысокое быстродействие,Фибоначчиумеренно хорошиеЛинейность преобразованияСЛстатистические свойства8Мультипликативный генераторВысокое быстродействие,Фибоначчиумеренно хорошиестатистические свойства9Генератор Фибоначчи соперацией «исключающее или»Высокое быстродействие05Линейность преобразования,эквивалентность выходнойпоследовательностисовокупности независимыхбитовых последовательностейТаблица 3 — продолжение№МетодДостоинстваНедостаткиГенераторы на основе регистров сдвига10 Регистры сдвига с линейнымиобратными связямиВысокое быстродействие,Предсказуемость, линейностьравномерность распределенияпреобразованиявыходной последовательности,эффективность аппаратнойреализации11 Обобщенные регистры сдвигаВысокое быстродействиеЛинейность преобразования,эквивалентность выходнойпоследовательностисовокупности независимыхбитовых последовательностей12 Обобщенные регистры сдвига сВысокое быстродействиекриптографиизакручиванием13 Регистры сдвига с нелинейными Непредсказуемость,обратными связямиНе могут применяться вНедостаточная изученность,потенциально высокая линейная проблематичность обеспечениясложность (определяетсяхороших статистическихфункцией обратной связи)свойств0502Таблица 3 — окончание№МетодДостоинстваНедостаткиГенераторы на основе клеточных автоматов14 Генераторы на основеХорошие статистическиеНедостаточная изученность,одномерных клеточныхсвойства, непредсказуемость,неэффективность программнойавтоматовнелинейность преобразования,реализациивысокая эффективностьаппаратной реализации-68-ГЛАВА 2ИССЛЕДОВАНИЕ СВОЙСТВ К Л Е Т О Ч Н Ы ХАВТОМАТОВ2.1.КЛАССИЧЕСКИЕ КЛЕТОЧНЫЕ АВТОМАТЫ2.1.1.

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

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