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

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

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

Д О С Т О И Н С Т В А И Н Е Д О С Т А Т К И Б А З О В Ы Х Г Е Н Е Р А Т О Р О ВБазовые генераторы псевдослучайных последовательностей обладаюткак достоинствами, так и недостатками. К достоинствам относятся- высокое быстродействие за счет выработки 256 бит выхода на каждомтакте работы генератора;- контролируемый период выходной последовательности, определяемыйдлиной регистра сдвига;- эффективность аппаратной реализации за счет использования клеточ­ных автоматов, в которых вычисление значений всех ячеек может осу­ществляться параллельно.К основным же недостаткам такого типа генераторов можно отнести:- недостаточно хорошие статистические свойства (как будет показано вдальнейшем, базовые генераторы не проходят набор статистическихтестов NIST);-124- возможность частичного восстановления внутреннего состояния гене­ратора и предсказания членов выходной последовательности по из­вестной ее части, поскольку значения ячеек клеточного автомата ис­пользуются в качестве выхода генератора без какой-либо обработки.Для устранения указанных недостатков мы предлагаем использоватькомбинированные генераторы псевдослучайных последовательностей, ко­торые будут рассмотрены далее.3.3.КОМБИНИРОВАННЫЕ ГЕНЕРАТОРЫКомбинированный генератор псевдослучайных последовательностейпостроен на основе двух базовых генераторов и включает в себя (см.рис.

3.6):- два двоичных клеточных автомата С\ и Сг;- регистр сдвига с линейными обратными связями R длины 63.Клеточный автомат CiРСЛОСЯаО)PtКлеточный автомат С?7t—»-«;(2)Р и с . 3.6. Общая структура комбинированного генератора псевдослучай­ных последовательностей на основе клеточных автоматовВ качестве автоматов С\ и С*2 могут использоваться как классические,так и неоднородные клеточные автоматы.

Выбор параметров клеточныхавтоматов аналогичен описанному в разделе 3.2. При этом в автоматах С\и Сг должны выбираться независимо друг от друга локальные функциисвязи и, в случае неоднородных клеточных автоматов, окрестности ячеек.Отметим, что базовый генератор может быть получен из комбинированного-125«отключением» одного из клеточных автоматов, при котором этот автоматформирует на выходе нулевую последовательность (для этого достаточ­но выбрать в качестве локальной функции связи автомата тождественныйноль).Регистр сдвига является общим для обоих клеточных автоматов.

Чле­ны выходной последовательности J3 регистра прибавляются по модулю 2к значению одной из ячеек клеточного автомата, как это было описано вразделах 3.2.1.4 (для классических автоматов) и 3.2.2.4 (для неоднородныхавтоматов).Члены выходных последовательностей cS^ и д№ клеточных автома­тов С\ и Сг формируются из значений подмножества всех ячеек так же,как и в базовых генераторах (см. разделы 3.2.1.4 и 3.2.2.4).Для формирования выхода комбинированного генератора использует­ся метод сложения последовательностей при помощи логической операции«исключающее или»:Выходные последовательности клеточных автоматов рассматриваются как256-разрядные двоичные векторы, и сложение осуществляется покомпо­нентно; члены выходной последовательности генератора 7 в таком случаетакже являются 256-разрядными двоичными векторами, т.е. комбиниро­ванный генератор вырабатывает 256 бит выхода за один такт работы.Поскольку последовательности oS1' и 6tS2' являются независимыми, ихсложение при помощи бинарной операции «исключающее или» позволяетулучшить свойства выходной последовательности-у (см.

раздел 1.3.2.1).Функция д(х, у) — х ®у является одной из двух нетривиальных кор­реляционно-иммунных булевых функций 1-го порядка от двух переменных(другой функцией является ее инверсия) [8]. Это означает, что количествоинформации по Шеннону, содержащееся в значении функции о значениилюбого из ее аргументов, равно нулю:1[х,д(х,у)] = 1[у,д(х,у)] = 0.-126Таким образом, сложение последовательностей а^1' и aS2' также позволяетсущественно затруднить как восстановление внутреннего состояния генера­тора (т. е. значений ячеек памяти клеточного автомата и регистра сдвига)по выходной последовательности, так и предсказание членов -у последова­тельности по известной ее части.

Отметим, что нетривиальных корреля­ционно-иммунных булевых функций 2-го порядка от двух переменных несуществует.3.3.1. П А Р А М Е Т Р Ы И Н А Ч А Л Ь Н Ы Е З Н А Ч Е Н И Я Г Е Н Е Р А Т О Р АКак и в базовом генераторе, мы различаем фиксированные парамет­ры, определяющие свойства генератора, и переменные начальные значения,определяющие начальное состояние генератора и задающие конкретнуювыходную последовательность.К параметрам комбинированного генератора относятся:*1) параметры клеточных автоматов С\ и Сч'- множество О значений ячеек (О — Z2);- количество ячеек (37 х 11 ячеек, упорядоченных в двумерную ре­шетку, для классических клеточных автоматов и набор из 257 яче­ек — для неоднородных);- окрестность ячеек (Ч^ — квазиполная окрестность радиуса 1 —для классических клеточных автоматов и W^ — выбираемая слу­чайным образом для каждой ячейки каждого клеточного автома­та окрестность мощности 4 —для неоднородных);- локальная функция связи / (нелинейная равновесная выбираемаяслучайно и независимо для каждого клеточного автомата);2) параметры регистра сдвига с линейными обратными связями:- длина регистра (63 ячейки);- характеристический многочлен f(x)63(f{x) — х+ х 4-1).Начальное состояние определяется значениями ячеек РСЛОС R, т.

е.63-разрядным набором, все элементы которого не должны одновременнопринимать нулевое значение.Заполнения ячеек клеточных автоматов С\ и С? мы рассматриваем вкачестве параметров генератора. Тем не менее, в некоторых приложениях-127(например, в криптографии) они могут рассматриваться в качестве значе­ний, определяющих начальное состояние. При выборе начального заполне­ния следует учитывать, что оно не должно быть целиком единичным илинулевым (более того, желательно, чтобы количество нулевых и единичныхзначений было приблизительно одинаковым), а также, в случае класси­ческих клеточных автоматов, избегать пространственной периодичности.Указанным требованиям отвечают начальные заполнения, выбранные слу­чайным образом (например, сформированные из некоторой случайной дво­ичной последовательности).3.3.2.ДЕТАЛИЗИРОВАННАЯ СТРУКТУРА И АЛГОРИТМ РАБОТЫСтруктура комбинированных генераторов с учетом особенностей ре­ализации на основе классических и неоднородных клеточных автоматовсхематично представлена на рис.

3.7.Алгоритм работы комбинированного генератора в целом аналогичентаковому для базового генератора. Он включает в себя фазы инициализа­ции (установки начальных значений), холостого хода (функционированиягенератора без выработки выходной последовательности) и генерации вы­ходной последовательности и может быть представлен следующим обра­зом:1) инициализация:1.1) присвоить счетчику тактов значение t = 0;1.2) занести начальные значения в регистр сдвига с линейными об­ратными связями R;1.3) перейти к шагу 2.1 (фазе холостого хода);2) холостой ход:2.1) вычислить новые значения ячеек клеточных автоматов С\ и Сч\2.2) прибавить выходное значение регистра сдвига R к значению со­ответствующих ячеек клеточных автоматов С\ и С2;2.3) вычислить новое состояние регистра сдвига R;2.4) увеличить счетчик тактов t на единицу;2.5) если t — 100, перейти к шагу 3.1 (фазе генерации); иначе перейтик шагу 2.1;128-Жa(i)«7t(2)w/w/x/.A777'i/л_22.У////, 4 ^777®РСЛОСЯ©fit(a)(6)Рис.

3.7. Детализированнаяструктуракомбинированногогенераторапсевдослучайных последовательностей на основе клеточных ав­томатов: (а) - классических, (б)неоднородных-1293) генерация:3.1) вычислить новые значения ячеек клеточных автоматов С\ и Ci\3.2) прибавить выходное значение регистра сдвига R к значению со­ответствующих ячеек клеточных автоматов С\ и Сг;3.3) вычислить новое состояние регистра сдвига Л;3.4) сформировать члены а^ + 1 и а^ + 1 выходных последовательностейклеточных автоматов С\ и Сг соответственно из значений под­множеств их ячеек;3.5) вычислить член выходной последовательности генератора"7 f+1 =3.6) увеличить счетчик тактов t на единицу;3.7) если получена выходная последовательность достаточной длины,работа генератора завершена; иначе перейти к шагу 3.1;3.3.3.

Д О С Т О И Н С Т В А И Н Е Д О С Т А Т К И .Комбинированные генераторы обладают лучшими свойствами по срав­нению с их базовыми аналогами. К достоинствам комбинированных гене­раторов относятся:- высокое быстродействие (выработка 256 бит выходной последователь­ности за один такт работы) и эффективность аппаратной реализации;- контролируемый период, зависящий от выбранной длины регистрасдвига с линейными обратными связями;- хорошие статистические свойства выходной последовательности (приопределенных вариантах выбора локальной функции связи и, в случаенеоднородных клеточных автоматов, окрестностей ячеек);- непредсказуемость выходной последовательности и сложность восста­новления внутреннего состояния генератора.Основным недостатком комбинированных генераторов являются вдвоебольшие требования к ресурсам при аппаратной реализации и вдвое мень­шее быстродействие при программной (по сравнению с базовыми генера­торами) за счет необходимости вычисления значений двух клеточных ав­томатов.-130-3.4.

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

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