Автоматная модель представления нелинейных псевдослучайных последовательностей с функцией выхода на основе системы инъективных преобразований

Захаров Вячеслав Михайлович доктор технических наук профессор, кафедра Компьютерных систем, Казанский Национальный Исследовательский Технический Университет им. А. Н. Туполева – КАИ 420111, Россия, Татарстан область, г. Казань, ул. К.маркса, 10 Zakharov Vyacheslav Mikhailovich Doctor of Technical Science professor of the Department of Computer Systems at Kazan National Research Technical University named after A.N. Tupolev 420111, Russia, Tatarstan, Kazan, Karl Marx' str., 10 gilvv@mail.ru Песошин Валерий Андреевич доктор технических наук профессор, кафедра Компьютерных систем, Казанский Национальный Исследовательский Технический Университет им. А. Н. Туполева – КАИ 420111, Россия, республика Татарстан, г. Казань, ул. К.маркса, 10 Pesoshin Valerii Andreevich Doctor of Technical Science professor of the Department of Computer Systems at Kazan National Research Technical University named after A.N. Tupolev 420111, Russia, Tatarstan, Kazan, Karl Marx' str., 10 pesoshin-kai@mail.ru Шалагин Сергей Викторович доктор технических наук профессор, кафедра Компьютерных систем, Казанский Национальный Исследовательский Технический Университет им. А. Н. Туполева – КАИ 420111, Россия, республика Татарстан, г. Казань, ул. К.маркса, 10 Shalagin Sergei Viktorovich Doctor of Technical Science professor of the Department of Computer Systems at Kazan National Research Technical University named after A.N. Tupolev 420111, Russia, Tatarstan, Kazan', Karl Marx' str., 10 sshalagin@mail.ru

Эминов Булат Фаридович кандидат физико-математических наук доцент, кафедра Компьютерных систем, Казанский Национальный Исследовательский Технический Университет им. А. Н. Туполева – КАИ 420111, Россия, республика Татарстан, г. Казань, ул. К.маркса, 10 Eminov Bulat Faridovich PhD in Physics and Mathematics associate professor of the Department of Computer Systems at Kazan National Research Technical University named after A.N. Tupolev 420111, Russia, Republic of Tatarstan, Kazan', Karl Marx' str., 10 bulfami@mail.ru

Введение

Тема развития, совершенствования моделей и алгоритмов построения генераторов псевдослучайных последовательностей (ПСП) с характеристиками, близкими к случайным последовательностям, постоянно отражается в публикациях. Примерами подобных работ, опубликованных в последние годы, являются [1–18]. Одной из активно исследуемых задач в этом направлении является задача ^[19,20] усложнения аналитического строения псевдослучайных последовательностей, применяемых для различных приложений (помехозащищенность широкополосных сигналов, защита информации и др.). Распространенный подход усложнения строения формируемой ПСП заключается в применении к элементам заданной исходной ПСП дополнительного преобразования в виде некоторой нелинейной внешней логики (нелинейной функции усложнения (НФУ)) ^{[6, 19-24]}.В данном подходе выбором исходнойПСП обеспечивается требуемый максимальный период формируемой псевдослучайной последовательности, а необходимое ее качество определяется моделью НФУ.

Важной задачей в отмеченном подходе является построение математических моделей нелинейной функции усложнения, однозначно выполняющей преобразование исходной ПСП и формирующей выходные нелинейные последовательности, обладающие на заданном максимальном периоде статистическими свойствами, приближающимися к свойствам случайной равновероятной последовательности. Этой задаче посвящена, в частности, работа ^[24], где представлена модель генератора ПСП с нелинейной функцией усложнения, реализующей усложнение ПСП из класса М-последовательностей ^[7] путем перестановки ее элементов. Перестановка в ^[24] реализуется на основе модулярной операции возведения в степень по модулю простого числа Ферма. Данная НФУ позволяет менять строение ПСП параметрически - путем замены в модулярной операции значений первообразных корней ^[25]. Однако период получаемых нелинейных ПСП на модели ^[24] ограничен величиной модуля, определяемого простым числом Ферма.

Целью работы является определение и алгоритмическое построение математической модели представления нелинейных ПСП на основе модулярной операции возведения в степень по модулю, принадлежащему к множеству простых чисел Ферма, позволяющей получать нелинейные ПСП с заданными перио­дами L = 2ⁿ−1 и L = 2ⁿ , где n > 1.

1.Постановка задачи

Рассмотрим генератор ПСП в виде конечного автономного автомата с функцией выхода:

(S, Y, , , s_⁰), (1)

где S - конечноемножество состояний; Y - конечное множество выходных букв; : S → S - функция переходов; : S → Y - функция выхода; s₀ – начальное состояние. Пусть |S| = |Y|, состояния автомата (1) являются двоичными векторами , выходные буквы являются двоичными векторами . Функция переходов автомата выполняет преобразование вектора Х в вектор Х и реализуется как генератор последовательности де-Брейна с периодом 2ⁿ на основе РС с нелинейной функцией обратной связи, определяемой полиномом вида ^[20]:

, (2)

где F(x) примитивный полином степени n над полем GF(2) = {0, 1}. Полином F(x) задает функцию обратной связи РС, генерирующего M-последовательность с периодом 2ⁿ−1. Функция выхода рассматривается как функция усложнения, выполняющая однозначное отображение

Z = (X): G(2)ⁿ → G(2)ⁿ, (3)

где G(2)n – множество n-мерных двоичных векторов, |G(2)ⁿ| = 2ⁿ.

Введем следующее нелинейное преобразование - алгоритм возведения в степень по модулю простого числа ^[25]:

, (4)

где p - простое число, j - целое число, Q_h - заданный первообразный корень (примитивный элемент) по модулю p, h = 1, 2, …, (p−1) (число первообразных корней при заданном модуле p равно значению функции Эйлера (p−1)) ^[25], Q_h принимает значения из интервала 1 < Q_h < p−1.

Отметим следующие свойства алгоритма (4), вытекающие из свойств первообразных корней по модулю p ^[25]. Обозначим их символами С1, С2, С3. Введем множества М₁ = {1, 2, …, p−1}, М₂ = {0,1, 2, …, p−1}.

Свойство С1 ^[25]. Пусть в алгоритме (4) переменная jпринимает значения из множества М₁ = {1, 2, …, p−1}. Тогда алгоритм (4) выполняет инъективное отображение F1: М₁ → М₁ и последовательность значений у_j, получаемая по алгоритму (4), имеет период p−1. Отображение F₁ есть перестановка, заданная на М₁.

Свойство С2 ^[25]. Пусть в алгоритме (4) переменная j принимает значения из множества М₂ ={0,1, 2, …, p-1}. Тогда алгоритм (4) выполняет однозначное отображение, сюръекцию F₂: М₂→М₁. В (4) значениям j = 0 и j = p−1 сопоставляется значение у_j = 1.

Свойство С3 ^[25]. Пусть в алгоритме (4) переменная jпринимает значения из множества М₁. Тогда алгоритм (4) при j = (p−1)/2 и заданном Q_h, 1 < Q_h < p –1, выполняет соответствие вида j→(влечет) у_j = р − 1, т.е.

(5)

Решаемой задачей является построение для автоматной модели (1) нелинейной функции выхода, реализующей инъективное отображение (3), где n – четное, n > 1, на основе алгоритма (4).

2. Анализ задачи, подход к решению

Из свойств С1-С3 следует:

1) для реализации в модели (1) инъективного отображения (3) алгоритмом (4) необходимым условием является выполнение соотношения p > 2^_n, n > 1;

2) чем больше величина ∆= p − 2ⁿ, тем больше отличается по составу и величине элементов множество Y от S при реализации функции выхода .

Введем в рассмотрение следующее множество простых чисел p, при которых величина ∆ имеет минимальное значение, равное ∆ =1: множество М_F={р₁, р₂, р₃, р₄} простых чисел Ферма (чисел вида р = 2^m + 1, где m=2, 4, 8, 16, р₁=2²+1=5, р₂=2⁴+1=17, р₃=2⁸+1=257, р₄=2¹⁶+1=65537).

Введем множество М₃ = {0, 1, 2, …, 2^m−1}, |М₃|=2^m, m=2, 4, 8, 16.

Рассмотрим решение задачи реализации инъективного отображения вида F3: М₃→М₃ на основе алгоритма (4).

Отметим следующее свойство алгоритма (4).

Утверждение 1. Пусть в алгоритме (4) выполняются следующие условия: модуль рМ_F, 1 < Q_h < p–1, переменная j принимает значения из множества М3, величина 2^m = p−1, m = 2, 4, 8, 16. Тогда алгоритм (4) выполняет инъективное отображение вида

F₂: М₃ → М₄ = {1, 2, …, 2^m-1, 2^m},

где представлено соответствие

. (6)

Справедливость утверждения 1 следует из свойств С1, С2, C3.

Отметим: операцию возведения в степень по модулю рМ_F по выражению (4) можно реализовать путем применения вычислительного алгоритма, представленного в виде ^[26].

Пример 1. Реализация в соответствии с ^[26] операции возведения в степень по модулю. Пусть m=4, р₂=17, Q₁=3.

1) Зададим двоичное текущее значение j. Пусть j =(х₀ х₁ х₂ х₃)₂=1011.

2) Заполним следующую таблицу

где б₀=Q₁=3 - заданный примитивный элемент по модулю р=17,

, l = 0, 1, 2, 3.

3) Результат y_j = б₃ (двоичный четырехразрядный код) считывается из последней ячейки второй строки. Для j =1011 получим yj= б₃=0111.

Обозначим символом Ам алгоритм, являющийся следующей модификацией алгоритма (4): алгоритм Ам отличается от алгоритма (4) только тем, что при рМ_F, j = 2^m/2 и 1 < Q_h < p−1 выполняет вместо соответствия (6) соответствие вида

. (7)

Следствие 1 (из утверждения 1). Пусть j в (4) принимает значения из множества М3, модуль рМ_F, 2^m = p−1, m = 2, 4, 8, 16 и 1 < Q_h < p–1. Тогда алгоритм Ам выполняет инъективное отображение F₃: М₃ → М₃.

Отображение F₃ есть перестановка, заданная на М₃.

Из следствия 1 вытекает следующее:

1) применение в автоматной модели (1) алгоритма Ам для реализации функции выхода позволяет выполнять инъективное отображение (3), где n = m = 2, 4, 8, 16;

2) получаемая нелинейная ПСП на выходе НФУ имеет абсолютно максимальный период L = 2ⁿ, где n = m = 2, 4, 8, 16 и по своей структуре является перестановкой элементов (векторов Х) последовательности де-Брейна, формируемой по соотношению (2).

Замечание 1. Число H(p_a), , первообразных корней помодулю рМ_F , определяемое функцией Эйлера, равно:

- для р₁ = 5: H(p₁)=(5-1)=2;

- для р₂ = 17: H(p₂)=(17-1)=8;

- для р₃ = 257: H(p₃)=(257-1)=128;

- для р₄ = 65537: H(p₄)=(65537-1)=32768. (8)

Применение в алгоритме Ам при фиксированном модуле рМ_F различных примитивных элементов Q_h позволяет параметрически, меняя Q_h в Ам (для каждого периода используется новый элемент Q_h), менять структуру ПСП на выходе алгоритма Ам и получать ансамбль формируемых ПСП, определяемый величиной H(p_a), , представленной в (8).

Отметим: величина периода получаемых ПСП на выходе автоматной модели (1) при реализации НФУ в виде алгоритма Ам, где n = m = 2, 4, 8, 16, ограничена величиной модуля рМ_F.

В разделе 3 предлагается представление модели НФУ в виде системы алгоритмов Ам, реализующей инъективное отображение (3), где n - четное, n > 1.

3. Модель функции усложнения

Примем n ≥ m. Выполним разбиение n-мерного двоичного вектора Х, n≡0(modm),m = 2, 4, 8, 16, на k блоков - m−разрядных двоичных векторов Х_i, , k = n/m. Подобное разбиение проведем и для вектора Z = (Zi), . При данном разбиении двоичные вектора Х_i и Z_i , , принимают значения из множества М₃ = {0,1,2, …, 2^m -1}, m = 2, 4, 8, 16.

Введем в рассмотрение кортеж вида

(β₁, β₂, …, β_k) (9)

где β_i, - однозначное преобразование (инъекция), выполняемое алгоритмом Ам при m = 2, 4, 8, 16 двоичных значений вектора Х_i, , по модулю рМ_F при заданном Q_h , 1 < Q_h< p–1, в двоичные значения вектора Z_i. Примем n=k·m ≥ H(p_a)·m, , m = 2, 4, 8, 16 (данные условия определяют возможность кратного применения в (9) элемента β_i , ).

Покажем, что нелинейная функция усложнения в модели (1), представляемая как система (9), при отмеченных ограничениях выполняет инъективное отображение (3).

Утверждение 2 (основное). Если в модели (1) нелинейная функция усложнения определена как система (9), то нелинейная функция усложнения выполняет в (1) инъективное отображение (3).

Справедливость утверждения 2 следует из свойств образов и прообразов для инъективного отображения ^{[27, с. 17]}.

Систему преобразований (9) будем рассматривать как модель функции усложнения для реализации инъективного отображения (3) в автомате (1).

4. О величине ансамбля формируемых последовательностей

Применение в преобразованиях β_i , , системы (9) при фиксированном модуле рМ_F различных примитивных элементов Q_h позволяет параметрически (меняя Q_h) менять структуру ПСП на выходе НФУ.

Условия, принятые для системы (9): n=k·m ≥ H(p_a)·m, , m = 2, 4, 8, 16 и утверждение 2 определяют разнообразие модификаций реализации системы (9) и получение на основе (1) различных по размеру ансамблей нелинейных ПСП.

Рассмотрим два случая получения ансамблей нелинейных ПСП, определяемые следующими ограничениями, которые накладываются на систему (9).

Примем, что в системе (9) ограничение имеет вид

n =k·m= H(p_a)·m, m = 2, 4, 8, 16, . (10)

Следствие 2 (из утверждения 2). Пусть в системе (9) при ограничении (10) в преобразованиях β_i, , применяются различные элементы Q_h, 1 < Q_h< p–1, в соответствии с фиксированным модулем рМ_F. Тогда для реализации в модели (1) отображения (3) при фиксированном модуле рМ_F существует H(p_a)!, , различных систем вида (9).

Следствие 2 обосновывает возможность при выполнении ограничения вида (10) в системе (9) получить на выходе автомата (1), при фиксированной функции переходов вида (2), с примитивным полиномом степени n = H(p_a)·m, ансамбль V_h = H(p_a)! нелинейных псевдослучайных последовательностей с заданным периодом L = 2ⁿ, где n = H(p_a)·m, .

Пример 2. Пусть для модели (1) в системе (9) с ограничением (10), в элементах β_i применяется модуль р₃ = 257, m = 8, k = H(p_a) = 128 и в (2) применяется примитивный полином степени n = H(p_a)·m = 1024. Тогда период ПСП на выходе автомата (1) равен L = 21024 и ансамбль V_h = 128!

Нижнюю оценку величины V_h = H(p_a)! при m = 16 и n=m·32768 определим (в соответствии с формулой Стирлинга ^[28]) значением

V_h = О(232768). (11)

Примем, что в системе (9) ограничение имеет вид

n=k·m > H(p_a)·m, , m = 2, 4, 8, 16. (12)

Для данного случая в качестве иллюстрации простейшего схемного представления НФУ в модели (1), определяемого применением наименьшего модуля р₁ = 5 в элементе β_i , рассмотрим следующую последовательностную реализацию системы (9) с ограничением (12).

Пусть в (1) задан период L=2n последовательности де-Брейна, например, n = 128, m = 2, модуль р₁ = 5 и заданы элементы Q₁ = 2 и Q₂ = 3, вектор Х разбит на k = n/m двухразрядных блоков (Х_i, ). Преобразование вектора Х_i в вектор Z_i элементом β_i , , назовем раундом. Пусть система (9) содержит только один элемент β, где модуль р₁ = 5. Преобразование вектора Х размера 128 бит в вектор Z размера 128 бит проведем этим элементом β за k=128/2 раундов. В раундах, на периоде 2ⁿ, преобразование в элементе β выполняется с чередованием элементов Q₁, Q₂ (хранимыми в отдельной памяти). Пусть динамическое чередование элементов Q₁, Q₂ в каждом раунде производится в соответствии с некоторой дополнительной двоичной ПСП (элементу 0 сопоставляется Q₁, элементу 1 сопоставляется Q₂) генерируемой дополнительным генератором с периодом L₁=k=64, определяемым числом раундов. В частности, таким генератором может быть генератор де-Брейна , подобный рассмотренному выше, с периодом L₁ =64. В этом случае число возможных, дополнительных ПСП равно 2^k = 2⁶⁴, что позволяет получить на выходе НФУ при модуле р₁ = 5 ансамбль нелинейных ПСП, имеющих период L = 2ⁿ, n=k·m, размером V₁=2^k = .

В подобной последовательностной реализации схемы НФУ с увеличением модуля рМ_F размер ансамбля формируемых последовательностей можно увеличить. С этой целью преобразование β в раундах по модулю рМ_F выполняется динамическим чередованием элементов Q_h из множества первообразных корней мощности H_a = H(p_a), . Чередование в раунде выполняется в соответствии с некоторой дополнительной H_a-значной ПСП, генерируемой дополнительным генератором ПСП с периодом L = k_i =n/m_i ,m_i=4, 8, 16, где k_i > H_i, i=a = 2, 3, 4. Используемые в раунде элементы Q_h хранятся в отдельной памяти емкостью H_i , i= 2, 3, 4 , m_i-разрядных ячеек.

Рассмотренная схема реализации НФУ позволяет получить следующие размеры ансамблей , i = 2, 3, 4, формируемых нелинейных последовательностей периода L = 2ⁿ.

При m = 4, H₂ = 8, k₂ = n/4, = 8^n/4 = 2^3n/4 ,

при m = 8, H₃ = 128, k₃ = n/8, = 128^n/8=2^7n/8,

при m = 16, H₄ = 32768, k₄ = n/16, = 32768^n/16=2^15n/16. (13)

5. Автоматная модель формирования

нелинейных ПСП с периодом 2n-1

Рассмотрим следующий частный случай автоматной модели (1), позволяющий получать нелинейные ПСП с периодом 2ⁿ−1.

Пусть функция : S → S переходов определяемого автомата реализуется регистром сдвига с характеристическим примитивным полиномом F(x) степени n. Состояния автомата являются двоичными векторами , выходные буквы являются двоичными векторами . Полином F(x) задает функцию линейной обратной связи РС, генерирующего М-последовательность с периодом 2ⁿ-1. В М-последовательности отсутствует состояние (вектор Х) из n нулей, которое обозначим как вектор Х₀. Функция выхода рассматривается как функция усложнения, выполняющая инъективное отображение

: S → Y, |S|=|Y| =2ⁿ−1. (14)

Данную модификацию конечно-автоматной модели (1) обозначим символом КА_Y.

Рассмотрим задачу построения для автомата КA_Y математической модели нелинейной функции выхода, реализующей инъективное отображение вида (14) на основе алгоритма (4) и позволяющей получить выходную нелинейную ПСП с заданным перио­дом L=2ⁿ−1, где n ≡ 0(mod m),m = 2, 4, 8, 16, n > m.

Представление модели требуемой нелинейной функции усложнения для автомата КA_Y определим на основе системы преобразований (9) при ограничениях (10) и (12).

Примем: в системе (9) ограничение имеет вид (10); преобразование β_i, , в (9) выполняется алгоритмом Ам , где двоичные вектора Х_i и Z_i принимают значения из множества М₃ ={0,1,2, …, 2^m−1}.

Возможность реализации НФУ в модели КА_Y на основе системы (9) при ограничении (10) обосновывает

Следствие 3 (из утверждения 2). Если нелинейная функция усложнения определена как система (9) с ограничением (10), то НФУ в модели КА_Y выполняет инъективное отображение (14), и где S не равно Y.

Примем: в системе (9) ограничение имеет вид (12).

Возможность реализации НФУ в модели КА_Y на основе системы (9) при ограничении (12) обосновывает

Следствие 4 (из утверждения 2). Если нелинейная функция усложнения определена как система (9) с ограничением (12), то НФУ в модели КА_Y выполняет инъективное отображение (14), и где S не равно Y.

Замечание 2.При реализации в КАY системой (9) отображения при ограничениях (10) и (12) получаемое множество Y отличается от множества S двумя n-разрядными векторами: Y включает нулевой вектор Z – вектор Z₀, все n разрядов которого содержат значение 0 и не содержит вектор Z=(Z_i), где у m-разрядного вектора Z_i, , m=2, 4, 8, 16, младший разряд содержит значение 1.

Вектор Z₀ включен в Y в силу следствия 1. Вектор Z=(Z_i), , не содержится в Y вследствие того, что множество S не содержит вектор Х₀, которому алгоритм Ам ставит в соответствие данный вектор Z = (Z_i).

ПСП, получаемую на выходе автомата КА_Y, будем рассматривать как квазиподобную М-последовательности по статистическим (частотным) свойствам на периоде 2ⁿ−1.

Пример 3.Преобразование М-последовательности системой (9) вида (β₁, β₂).

Пусть n = 4, р = 5, m = 2, k = 2 система (9) представлена парой преобразований (β₁, β₂), где β₁ выполняется с Q₁=3 и β₂ выполняется с Q₂ = 2 и функция переходов автомата КА_Y формирует последовательность векторов Х, принимающих следующие 15 различных четырехразрядных двоичных значений в соответствии с М-последовательностью, построенной на РС с s₀ = 1000, по примитивному полиному f(x)=x⁴+x+1: (1000, 0100, 0010, 1001, 1100, 0110, 1011, 0101, 1010, 1101, 1110, 1111, 0111, 0011, 0001). Тогда на выходе НФУ, представленной парой преобразований (β₁, β₂), будет получена следующая последовательность четырехразрядных двоичных векторов Z с периодом L=15: (0001, 1101, 0100, 0010, 1001, 1100, 0011, 1110, 0000, 1010, 1000, 1011, 1111, 0111, 0110). В данной последовательности имеется вектор 0000 и отсутствует вектор 0101, что соответствует замечанию 2.

Отметим: размеры ансамблей, получаемые на модели КА_Y определяются соотношениями (11) и (13).

Заключение

1. Представленная автоматная модель формирования нелинейных псевдослучайных последовательностей с заданными периодами L = 2ⁿ и L = 2ⁿ−1, где n>1, n ≡ 0 mod m, m=2,4,8,16, отличается видом модели функции выхода, задаваемой системой, реализующей k = n/m нелинейных операций возведения в степень по модулю, принадлежащему к множеству простых чисел Ферма и выполняющей инъективное преобразование.

2. Определены и аналитически обоснованы алгоритмические возможности автоматной модели (утверждения 1 и 2, следствия 1 и 2), определяющие вид аналитического усложнения ПСП на периоде L = 2ⁿ: функция выхода автомата выполняет на основе нелинейных модулярных операций псевдослучайную перестановку элементов (векторов Х) последовательности де-Брейна.

3. Определены и аналитически обоснованы алгоритмические свойства автоматной модели (следствие 3, следствие 4), определяющие аналитическое усложнение ПСП на периоде L = 2ⁿ−1: функция выхода автомата порождает на основе нелинейных модулярных операций нелинейную ПСП, квазиподобную М-последовательности по статистическим (частотным) свойствам на периоде 2ⁿ−1.

4. В автоматной модели достигается дополнительное изменение структуры выходных ПСП путем псевдослучайной перестановки в модулярных операциях значений первообразных корней.

5. Нижняя оценка размера ансамбля V_h = H(p_a)! при m = 16 и n=m·32768 определяется значением V_h =О(2³²⁷⁶⁸).