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

< tn случайные величины a t l , . . . , atn независимы в совокупности;2) для любого номера i G N случайная величина at имеет равномерноераспределение вероятностей:Pr[at = и] = —,UEOL.Такие последовательности могут быть получены в следующей схемеиспытаний. Допустим, что имеется N шаров, различающихся только сво­им цветом. Сопоставим каждому шару уникальный номер от 1 до iV ипоместим их в непрозрачную урну. Для формирования членов случайной-20-последовательности будем повторять следующую последовательность ша­гов:1) перемешаем шары в урне и вытянем наугад один шар;2) сопоставим событию «из урны вытянут шар номер г» элемент сиг Е О.и примем его в качестве очередного члена последовательности щ;3) вернем шар в урну.Очевидно, что испытания (вытягивания шаров из урны) являютсянезависимыми.

Кроме того, введенные таким образом события являютсяпопарно несовместными и имеют одинаковую вероятность Pr[at = и] — ^ ,ш £ О. Таким образом, полученная последовательность dt —ai,a2,...удовлетворяет фундаментальным требованиям и является равномерно рас­пределенной на дискретном множестве О случайной последовательностью.В дальнейшем мы будем рассматривать в основном числовые случай­ные последовательности над множеством Q.

— ZJV = { 0 , 1 , . . . , N — 1}. Дляэтого достаточно сопоставить каждому элементу и;* Е П. число (г—1) Е Ъ^.Исходя из фундаментальных требований, можно доказать ряд другихсвойств числовых равномерно распределенных случайных последователь­ностей [12]:1) математическое ожидание E[a t ] и дисперсия D[o^] имеют следующиезначения:„г,N-1E N = -y~,_г.D[at] = -N2-l1 Г;2) для любого числа п £ N и любой фиксированной последовательно­сти индексов 1 ^ t\ < ... < tn n-мерное дискретное распределениевероятностей случайных элементов а^,...,Pr[a t l =ai,...,octn=ап] = — ,atn — равномерное на Щ^\а ь .

. . , ап £ ZN;3) (воспроизводимость при прореживании) для любой фиксированнойпоследовательности индексов 1 ^ t\ < Ь2 < ...последовательностьР = atl, cxt2, • •., получаемая в результате «прореживания» а, также яв­ляется равномерно распределенной случайной последовательностью;4) (воспроизводимость при суммировании) если Р = /?!,/% > ••• — произ­вольная независимая от а последовательность (случайная или неслу--21чайная), то последовательность у = {at + А}, получаемая почленнымсуммированием последовательностей а и /3, также является равномер­но распределенной случайной последовательностью;5) (непредсказуемость) для произвольного числа п £ N количество ин­формации по Шеннону [72], содержащееся в п-членной последователь­ности /3 = а.\,..., ап о значении элемента ап+\ последовательности а,равно нулю:1[<хп+иР] = H [ a n + i ] - H[a n + i|/3] = О,т. е.

прогнозирование (предсказание) ап+\ по ос\,..., ап невозможно;6) если U С Z^r — некоторая произвольная фиксированная область кмерного векторного пространства над ZJV, мощность которой (т.е.количество элементов) равна и, то при п —>• со имеет место схо­димость частоты попадания случайных векторов vi,...,vn,Vi =в{Щг-1)к+1, • • • ot(i-i)k+k), эту область:lim S k ^ M _ »п->ооjvигде (Tu(vi) — индикаторная функция:(l,<ги(?г) = <(О,Vi€U,$U.Vi1.1.2. ПОДХОДЫ К ПОЛУЧЕНИЮ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ СЛУ­ЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙДля выработки случайных последовательностей на практике исполь­зуются генераторы случайных последовательностей — методы или устрой­ства, позволяющие по запросу получить реализацию равномерно распре­деленной случайной последовательности a = a i , .

. . , a n длины п 6 N.Элементы а\,... ,ап этой последовательности также часто называют слу­чайными числами. Существует два основных типа генераторов случайныхпоследовательностей:- физические;-22-- детерминированные.Физический генератор — это специальное устройство, выходной сиг­нал которого определяется некоторым случайным физическим явлением,поэтому такой генератор также называется генератором истинно случай­ных последовательностей. Недостатками физических генераторов случай­ных последовательностей являются невозможность повторного получениянекоторой реализации случайной последовательности в силу недетермини­рованности генератора и высокая зависимость генератора от различныхфизических процессов (помех, смещений рабочего режима).Детерминированный генератор — это программа или устройство, реа­лизующее преобразование небольшого количества входных данных в вы­ходную последовательность произвольной длины.

Члены выходной после­довательности детерминированного генератора по своей природе не явля­ются случайными, в связи с чем такую последовательность принято на­зывать псевдослучайной, а сам генератор — генератором псевдослучайныхпоследовательностей.В дальнейшем будут рассматриваться только детерминированные ге­нераторы псевдослучайных последовательностей.1.2.ГЕНЕРАТОРЫПСЕВДОСЛУЧАЙНЫХПОСЛЕДОВАТЕЛЬ­НОСТЕЙ1.2.1. Ф О Р М А Л Ь Н О Е О П Р Е Д Е Л Е Н И Е Г Е Н Е Р А Т О Р А П С Е В Д О С Л У Ч А Й Н Ы ХПОСЛЕДОВАТЕЛЬНОСТЕЙГенераторомпсевдослучайныхпоследовательностей(генераторомПСП) в общем случае называется отображениед: S -> п°°конечного множества начальных состояний S в множество бесконечныхпоследовательностей с элементами из О..Генераторы псевдослучайных последовательностей удобно рассматри­вать с точки зрения теории конечных автоматов в качестве автономныхконечных автоматов с выходом [43].

При таком подходе генератор описы--23-вается пятеркой-4g(5,s 0 ,/,O,p),где:- S — конечное множество внутренних состояний;- SQ — начальное состояние автомата, определяемое вектором инициали­зации;- / : S —> S — функция переходов, определяющая состояние автомата,на следующем такте работы в зависимости от его текущего состояния;- О — выходной алфавит автомата;- д : S —>• D. — функция выходов, формирующая очередной член выход­ной последовательности на основании текущего состояния.Функционирование генератора псевдослучайных последовательностейвключает в себя две фазы:1) инициализацию генератора;2) выработку (генерацию) псевдослучайной последовательности.Первая фаза выполняется только один раз — перед непосредственным:использованием генератора.

Вторая фаза выполняется циклически до т е хпор, пока не будет получено необходимое количество членов вырабатывае­мой генератором последовательности.Таким образом, функционирование генератора псевдослучайных по­следовательностей в автоматной модели может быть описано следующим:алгоритмом:1) инициализация:1.1) присвоить счетчику тактов t значение 0;1.2) перевести автомат в начальное состояние SQ\2) генерация:2.1) перевести автомат в состояние st+i, определяемое функцией пе­реходов /: st+i <- f(st);2.2) сформировать очередной член выходной последовательности оспри помощи функции выходов д: at+i <— g(st+i);2.3) увеличить значение счетчика тактов: t «— t + 1;2.4) если получено достаточное количество символов выходной после­довательности, то работа генератора завершена; иначе перейти к-24-шагу 2.1.Из того, что генератор псевдослучайных последовательностей являет­ся автономным конечным автоматом, с необходимостью следуют основныенедостатки детерминированных генераторов:1) последовательности s = {st} внутренних состояний генератора и а ={at}выходных символов являются периодическими, т.

е. существуюттакие числа Т0 G N U {0} и Т 6 N, что при любом t > Т 0 выполняетсясоотношенияSt = St+T,Cit =&t+T,где To — предпериод, a T — период генератора;2) символы выходной последовательности а не являются независимы­ми, и следовательно, существует такое число п G N, что количествоинформации по Шеннону [72], содержащееся в последовательности/3 = a?i,..., ап о значении элемента an+i, не равно нулю:l[an+lJ]= H[a n + i] - Щап+1\Р] ф 0,т.

е. возможно предсказание значения символа ап+\ по a i , . . . , ап.Таким образом, очевидно, что выходная последовательность детерми­нированного генератора не является случайной в смысле раздела 1.1.1. Темне менее, для использования псевдослучайных последовательностей доста­точно, чтобы они были на практике неотличимы от истинно случайныхпоследовательностей:1) период Т должен существенно превосходить требуемое на практикечисло членов выходной последовательности а\2) статистические различия между характеристиками псевдослучайнойи истинно случайной последовательности не должны обнаруживатьсяпри помощи известных статистических тестов;3) для генераторов ПСП криптографического качества не должно бытьизвестно эффективных алгоритмов, позволяющих предсказывать про­извольный символ щ выходной последовательности по известным еечленам atl,...,Oitn Для любых разумных значений п Е N.Вместе с тем генераторы псевдослучайных последовательностей обла--25дают и неоспоримыми достоинствами, среди которых:1) возможность получения последовательности произвольной длины, непревосходящей величины периода;2) возможность воспроизводства построенной ранее последовательности(при известном значении вектора инициализации);3) меньшая подверженность сбоям по сравнению с физическими генера­торами;4) более низкая стоимость по сравнению с физическими генераторами.1.2.2.

К Л А С С И Ф И К А Ц И Я Г Е Н Е Р А Т О Р О В П С Е В Д О С Л У Ч А Й Н Ы Х ПОСЛЕ­ДОВАТЕЛЬНОСТЕЙКлассификация генераторов существенно зависит от целей исследова­ния. Так, например, генераторы можно разделять:- по структуре —на простые (элементарные) генераторы, использующиеединственную псевдослучайную последовательность для построениявыхода, и составные (комбинированные) генераторы, использующиедля этой цели две или более «элементарные» псевдослучайные после­довательности;- по свойствам используемого для формирования выходной последова­тельности преобразования — на линейные и нелинейные;- по множеству внутренних состояний — на генераторы, осуществляю­щие преобразования в кольце Z ^ , произвольном конечном поле ¥q,двоичном полеЕг, некотором линейном пространстве L(F 9 ) над полемF g и т. д.Мы будем, основываясь на [12], пользоваться классификацией гене­раторов по типу используемого преобразования и способу его реализации.В соответствии с выбранным признаком мы выделяем следующие классыпростых генераторов псевдослучайных последовательностей:1) линейные конгруэнтные генераторы;2) нелинейные конгруэнтные генераторы;3) генераторы Фибоначчи;4) генераторы на основе регистров сдвига;5) генераторы на основе клеточных автоматов.-26Следует отметить, что такое деление на классы является весьма услов­ным.