Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 18
Текст из файла (страница 18)
раздел 2.1.4) позволяют гарантировать,что период последовательности' внутренних состояний автомата будет неменьше величины TR. Поскольку каждый член выходной последовательности генератора формируется из значений большей части ячеек клеточногоавтомата, можно утверждать, что период выходной последовательноститакже ограничен снизу значением TR.Двоичные регистры сдвига с линейными обратными были рассмотрены в разделе 1.2.6.2. Регистр сдвига характеризуется длиной L и структурой обратных связей, т.е.
ячейками, с которых осуществляется съем.Мы используем РСЛОС длины 63 с характеристическим многочленомf(x) — х63-\-х-\-1. Выбор многочлена обусловлен простотой и эффективно--118стью программной реализации регистра, поскольку съем осуществляетсявсего с двух ячеек (старшей и младшей). Т. к. многочлен f(x) — примитивный над полем F2 (см. табл. 1 на стр. 43), регистр является М-генератором иобеспечивает период выходной последовательности TR = 2 6 3 —1 ~ 9,2-1018,достаточный для большинства практических применений.
Тем не менее,при необходимости получения большего гарантированного периода генератора псевдослучайных последовательностей длина регистра может бытьувеличена.Таким образом, период Т выходной последовательности базового генератора ограничен снизу величиной периода выходной последовательностирегистра сдвига R и сверху — мощностью множества внутренних состоянийгенератора, равной 2 3 7 п • 2 6 3 = 2 4 7 0 ^ 3,0 • 1 0 ш :9,2-1018^Г^З,0-10141.3.2.2.Б А З О В Ы Й Г Е Н Е Р А Т О Р НА ОСНОВЕ Н Е О Д Н О Р О Д Н Ы Х К Л Е Т О Ч Н Ы ХАВТОМАТОВВ базовом генераторе на основе неоднородных клеточных автоматов используется неоднородный булев клеточный автомат размера 257 сокрестностью мощности 4.
Для формирования членов выходной последовательности генератора используются значения всех ячеек, кроме одной.Выбор параметров генератора на основе неоднородных клеточных автоматов обусловлен теми же соображениями, что и в случае классическихклеточных автоматов, и поэтому описывается в краткой форме.3.2.2.1.ОБОСНОВАНИЕ ВЫБОРА ОКРЕСТНОСТИКак было отмечено ранее, мощность окрестности ячейки, т.е. числоаргументов локальной функции связи, в значительной степени определяет эффективность аппаратной реализации клеточного автомата.
В разделе 2.2.3 было показано, что неоднородные клеточные автоматы по сравнению с классическими обладают лучшими характеристиками лавинногоэффекта при равномощных окрестностях.Это позволяет понизить мощность окрестности без существенногоухудшения характеристик. Кроме того, поскольку в неоднородных кле--119точных автоматах ячейки не упорядочиваются в некоторую регулярнуюструктуру (решетку), окрестность может выбираться произвольным образом без учета геометрической интерпретации.Основываясь на изложенных соображениях, мы используем окрестность Ч?4 мощности 4. Элементы окрестности для каждой ячейки неоднородного клеточного автомата являются фиксированными (т.
е. не изменяются в процессе работы), но выбираются случайным образом.Применимость полученного клеточного автомата для использованияв составе генератора псевдослучайных последовательностей определяетсяэкспериментально при проведении исследований статистических свойстввыходной последовательности.3.2.2.2. О Б О С Н О В А Н И Е В Ы Б О Р А Р А З М Е Р А К Л Е Т О Ч Н О Г О АВТОМАТАИ СПОСОБА Ф О Р М И Р О В А Н И Я В Ы Х О Д Н О Й П О С Л Е Д О В А Т Е Л Ь Н О СТИИспользуемый размер неоднородного клеточного автомата—257 ячеек — обеспечивает мощность множества внутренних состояний (и, соответственно, максимально возможный период последовательности внутреннихсостояний), равную 2 2 5 7 « 2,3 • 10 77 .Каждый член выходной последовательности генератора формируетсяиз значений 256 ячеек клеточного автомата с индексами от 0 до 255 (см.рис.
3.4):« t = [m0,t, miit,...m255,i]GZ562 >где mXf, — значение ячейки клеточного автомата с индексом х в моментвремени t, что обеспечивает, как и в случае классических клеточных автоматов, формирование 256 бит выхода за один такт работы генератора.При таком выборе размеров неоднородного клеточного автомата и способа формирования выходной последовательности генератора он не уступает по быстродействию классическому аналогу, но при этом обладает более эффективной реализацией за счет меньшего количества ячеек памяти.Тем не менее, в случае неоднородных клеточных автоматов значения всехячеек клеточного автомата может быть легко восстановлено по выходнойпоследовательности, что является нежелательным в криптографических-120-mч255 256777257Рис.
3.4. Формирование выходнойпоследовательностинеоднородногоклеточного автомата (штриховкой обозначено множество ячеек,с которых осуществляется съем значений)приложениях.3.2.2.3. О Б О С Н О В А Н И Е В Ы Б О Р А Л О К А Л Ь Н О Й ФУНКЦИИ С В Я З ИВ соответствии с доводами, изложенными в разделе 2.2.2, в качествелокальной функции связи неоднородного клеточного автомата мы используем равновесную булеву функцию, вектор значений которой был полученпри помощи генератора псевдослучайных последовательностей. Применимость конкретной функции определяется эмпирическим путем при тестировании статистических свойств выходной последовательности генератора.3.2.2.4. О Б О С Н О В А Н И Е В Ы Б О Р А П А Р А М Е Т Р О В Р С Л О С и П Е Р И О Д А ВЫХОДНОЙ П О С Л Е Д О В А Т Е Л Ь Н О С Т ИКак и в случае базового генератора на основе классических клеточных автоматов (см.
раздел 3.2.1.4), мы используем РСЛОС длины 63 спримитивным характеристическим многочленом/(ж) = х63 + х + 1. Выходрегистра сдвига прибавляется по модулю 2 к ячейке клеточного автоматас индексом 256 (см. рис. 3.5).01у, 'УУУ// /.т./у/•••255 256'//'У/ ' / / / / /У/.//©РСЛОСРис. 3.5. Сложение выхода РСЛОС со значением ячейки клеточного автомата-121Период выходной последовательности генератора при этом ограниченнеравенством9,2-1018<TsC2,l-1096,что, на наш взгляд, удовлетворяет современным требованиям к генераторам псевдослучайных последовательностей (в противном случае длинарегистра может быть увеличена).3.2.3.
П А Р А М Е Т Р Ы И Н А Ч А Л Ь Н Ы Е З Н А Ч Е Н И Я Г Е Н Е Р А Т О Р АВ генераторе выделяются постоянные параметры, определяющие егосвойства, и начальные значения, от которых зависит конкретная выходнаяпоследовательность.К постоянным параметрам базового генератора относятся (для справки в скобках указаны используемые значения):1) параметры клеточного автомата С:- множество О.
значений ячеек (Г2 = Z2);- количество ячеек (двумерная решетка 37 х 11 ячеек для классических клеточных автоматов и набор из 257 ячеек для неоднородныхклеточных автоматов);- окрестность ячеек (Ч^ — квазиполная окрестность радиуса 1 —для классических клеточных автоматов и Ч^ — случайно выбираемая для каждой ячейки окрестность мощности 4 — для неоднородных клеточных автоматов);- локальная функция связи / (нелинейная равновесная выбираемаяслучайным образом);2) параметры регистра сдвига с линейными обратными связями R:- длина регистра (63 ячейки);- характеристический многочлен f(x),определяющий структуру63обратных связей (f(x) = ж + х + 1).Начальное состояние генератора определяется значениями ячеек регистра сдвига R — двоичным набором гад = [тщ 0 , тщ 0 , .
. . , тщ2 0 ] . В качестве гщ ' может использоваться любой набор, кроме нулевого (т. е. средиэлементов 7тгг-0 , 0 ^ г < 63, должен быть хотя бы один ненулевой).Заполнение ячеек клеточного автомата С в начальный момент време--122ни в зависимости от применения может являться как параметром (например, в генераторах, используемых для моделирования), так и определяющим начальное состояние значением (в качестве долговременного ключав криптографических приложениях). В силу свойств клеточных автоматов это заполнение не должно быть целиком нулевым или единичным, атакже, в случае классических клеточных автоматов, не должно обладатьпространственными периодами.
Кроме того, желательно, чтобы число единичных и нулевых значений было приблизительно одинаковым. Предпочтительным способом получения такого начального заполнения ячеек нанаш взгляд является использование случайных равномерно распределенных двоичных последовательностей.Мы будем рассматривать начальное заполнение ячеек клеточного автомата как постоянный параметр.3.2.4. А Л Г О Р И Т М Р А Б О Т ЫАлгоритм работы генератора включает в себя три фазы:1) фазу инициализации, на которой устанавливаются начальные значения;2) фазу холостого хода, в течение которой осуществляется функционирование генератора, но выходная последовательность игнорируется;исходя из длины регистра сдвига и характеристик лавинного эффектапродолжительность этой фазы выбрана равной 100 тактам, что позволяет выходным значениям регистра распространиться по клеточномуавтомату;3) фазу генерации, обеспечивающую непосредственно выработку псевдослучайной выходной последовательности.Алгоритм работы базового генератора можно описать следующим образом:1) инициализация:1.1) присвоить счетчику тактов значение t = 0;1.2) занести начальные значения в регистр сдвига с линейными обратными связями R;1.3) перейти к шагу 2.1 (фазе холостого хода);-1232) холостой ход:2.1) вычислить новые значения ячеек клеточного автомата С;2.2) прибавить выходное значение регистра сдвига R к значению соответствующей ячейки клеточного автомата;2.3) вычислить новое состояние регистра сдвига R]2.4) увеличить счетчик тактов t на единицу;2.5) если t = 100, перейти к шагу 3.1 (фазе генерации); иначе перейтик шагу 2.1;3) генерация:3.1) вычислить новые значения ячеек клеточного автомата С;3.2) прибавить выходное значение регистра сдвига R к значению соответствующей ячейки клеточного автомата;3.3) вычислить новое состояние регистра сдвига R;3.4) сформировать член cxt+i выходной последовательности генератора из значений ячеек клеточного автомата С;3.5) увеличить счетчик тактов t на единицу;3.6) если получена выходная последовательность достаточной длины,работа генератора завершена; иначе перейти к шагу 3.1;3.2.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
