Model of complication function for generator of pseudorandom sequences over the field GF(2).pdf Рассмотрим преобразование f (X) : GF(2)n ^ GF(2)n, (1) где n чётное; GF(2)n - множество n-мерных двоичных векторов. Пусть отображение (1) является биекцией и вектор X формируется некоторым генератором псевдослучайных последовательностей со свойствами случайной равновероятной последовательности. Преобразование (1) рассматривается как функция усложнения. Предлагается модель функции усложнения, обладающая алгоритмическими возможностями изменения структуры ПСП и увеличения ансамбля формируемых ПСП. Рассмотрим линейное преобразование вектора X в виде Zl = Аг ■ X, (2) где Aj - двоичная невырожденная матрица размера n и равенство понимается по модулю 2. Число линейных невырожденных преобразований, выполняемых по формуле (2), при n = 2 равно 6. Учтём, что отображению (1) при n = 2 соответствует максимальное число различных биекций равное 24 [1]. Разобьём вектор X = x1x2 ... xn на непересекающиеся пары переменных (x2i-1, x2i), i = 1,..., n/2. Введём в рассмотрение транспонированный кортеж вида (3) (91,92,... ,qm)T, где m = n/2; q, - некоторое линейное биективное преобразование над вектором (x2i-1 , x2i) в вектор (z2i-1,z2i), i = 1,...,n/2. Пусть в (3) m =24 и число различных элементов q, равно максимальному числу биекций от двух двоичных переменных, т.е. 24. Определение всех элементов множества G = (q, : i = 1,..., 24} для системы (3) рассматривается как задача построения требуемой функции усложнения. Обозначим A = (A, : i = 1,... , 24} некоторое множество невырожденных матриц Aj размера 3, позволяющих выполнить по формуле (2) 24 различных биекции. Введём векторы (x2i-1,x2i, 1) и (z2i-1,z2i, 1) как расширения соответственно векторов (x2i-1,x2i) и (z2i-1,z2i), i = 1,..., 24. Теорема 1. В системе (3) линейное биективное преобразование q, E G над вектором (x2i-1,x2i) представимо однозначно соответствующей невырожденной матрицей Aj E A, осуществляющей преобразование вектора (x2i-1,x2i, 1) в вектор (z2i-1,z2i, 1), i = 1,..., 24. Доказательство теоремы основано на результатах работы [2], показывающих возможность сведения аффинного преобразования к линейному. Следствие 1. При n = 48 для отображения (1) существует 24! биективных преобразований вектора X в вектор Zl вида (3). Для случая n = 48 на модели (3) при фиксированной М-последовательности на входе путём перестановки элементов q, можно получить ансамбль V периодических последовательностей векторов Zl мощности Q1 = 24!. Множество матриц A можно разбить на три подмножества M1, M2, M3 с мощностями |M 1| = 10, |M2| = 8, |M3| = 6; M1 = (E}U(Ai : O(Ai) = 2}; M2 = (A, : O(Ai) = = 3}; M2 = (A, : O(A,) = 4}, где E - единичная матрица; O(Aj) -порядок матрицы A, в группе GL(3). Возможность сочетания в функции усложнения (3) невырожденных матриц A, из множеств M1, M2, M3 позволяет менять строение выходной последовательности: создавать разнообразный порядок следования векторов Zl, отличающийся от порядка следования входных векторов X; при этом последовательности векторов Zl из ансамбля V сохраняют величину периода и статистические свойства входной М-последова-тельности. В частном случае на основе определённых матриц A, E A можно получить тождественное преобразование вектора X. На входе системы (3) можно использовать М-последовательности из ансамбля мощности Q2 = (^(248 - 1))/48, где ^ - функция Эйлера, при этом для n = 48 выполняется Q1 > Q2. Тогда на выходе системы (3) можно формировать ансамбль последовательностей векторов Zl мощности Q1 • Q2.

Скачать электронную версию публикации