СПОСОБ ТРАНСЛЯЦИОННОГО УСЛОЖНЕНИЯ НЕЛИНЕЙНЫХ РЕКУРРЕНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В ВИДЕ КОДОВ КВАДРАТИЧНЫХ ВЫЧЕТОВ, СУЩЕСТВУЮЩИХ В ПРОСТЫХ ПОЛЯХ ГАЛУА GF(p), И УСТРОЙСТВО ДЛЯ ЕГО РЕАЛИЗАЦИИ
METHOD OF TRANSMISSION COMPLICATION OF NON-LINEAR RECURRENT SEQUENCES IN THE FORM OF CODES OF QUADRATIC RESIDUES EXISTING IN SIMPLE GALOIS FIELDS GF(P) AND DEVICE FOR ITS IMPLEMENTATION

1. Область применения, к которой относится изобретение
Изобретение относится к способам и устройствам обеспечения безопасности широкополосной радиосвязи, где для расширения спектра сигнала используются нелинейные псевдослучайные последовательности (ПСП), а также к вычислительной технике, использующейся в системах связи со сложными сигналами (шумоподобными сигналами - ШПС).
В широкополосных системах связи помехозащищенность и имитостойкость сигналов достигается, во-первых, расширением их спектра путем манипуляции информативных параметров несущего колебания по закону псевдослучайных последовательностей (ПСП), а во-вторых, использованием таких ПСП, которые обеспечивают высокую требуемую структурную скрытность сигналов. Структурная скрытность характеризуется способностью противостоять мерам радиотехнической разведки, направленным на раскрытие структуры (вида) сигнала, и для ее увеличения необходимо иметь по возможности большой ансамбль используемых сигналов и достаточно часто изменять форму сигнала (Г.И. Тузов и др. // Помехозащищенность радиосистем со сложными сигналами - М.: Радио и связь, 1985. - 264 с.). При этом в интересах обеспечения заданной помехоустойчивости необходимо достижение хороших корреляционных свойств ПСП.
В работах (Сныткин И.И. Теория и практическое применение сложных сигналов с нелинейной структурой. Монография МО СССР, Часть 1-4, - 1989-1990.) показывается, что большой класс оптимальных дискретных сигналов - нелинейные рекуррентные последовательности (НЛРП) - основу которых составляют коды квадратичных вычетов (ККВ), характеристические коды, коды Холла, Якобы, обладают рядом существенных преимуществ по отношению к линейным рекуррентным последовательностям (ЛРП) в области обеспечения помехозащищенности и имитостойкости сигналов. Однако выявленные особенности в правилах построения (генерирования) НЛРП указывают на возможность раскрытия их структуры по аналогии с алгоритмом Берлекэмпа-Месси раскрытия структуры ЛРП. Поэтому разработка эффективных способов генерирования таких НЛРП, которые бы обеспечивали высокую требуемую структурную скрытность ШПС, является важным направлением развития теории сигналов и практики их применения, особенно в специальных системах связи.
2. Уровень техники
Одним из путей повышения указанных параметров является усложнение внутренней структуры ПСП.
Известен способ усложнения ЛРП на основе использования генераторов Макларена-Марсальи (Алферов А.П. и др. // Основы криптографии. Учебное пособие, 2/е изд., испр и доп. - М.: Гелиос АРВ, 2002, с. 279-283.)
В самом общем виде принцип работы таких генераторов можно сформулировать следующим образом. Пусть имеются три ЛРП и массив памяти. Элементы первой ЛРП записываются в память по адресам, которые определяются элементами второй ЛРП. Элементы выходной последовательности получаются при считывании значений, хранящихся в массиве памяти, в соответствии с элементами третьей ЛРП. Частным примером такого генератора является случай, когда процессами записи и считывания управляет одна и та же ЛРП.
0
1
i
L-1
i
i
n
n
n
Однако данный способ (прототип) не применим для усложнения НЛРП, существующих в простых полях Галуа GF(p), ввиду того, что формирование НЛРП в общем случае связано с вычислением двузначного характера ψ(⋅) соответствующего элемента поля GF(q)={a,a,…,a,…,a}, где q - порядок поля (для GF(p)⇒q=p, a GF(p)⇒q=p), a - элементы поля (для GF(p) - числа от «0» до «р-1», для GF(p) - числа от «0» до «р-1» и полиномы f(x) степени не больше n), т.е. элементы μ есть:
n
*
*
n
где  (для GF(p) приведение осуществляется по mod(p), а для GF(p) приведение осуществляется по двойному модулю modd(f(x),p), где f(x) - первообразный неприводимый полином для GF(p)); θ - первообразный элемент поля.
1
2
i
L
i
i
То есть НЛРП обладают двузначным характером отображения, например, μ={μ,μ,…,μ,…,μ}, где: μ={1;-1} или μ={1;0}, и не могут определять адреса в массиве памяти для записи или считывания элементов последовательности.
Сходными признаками известного способа (прототипа) усложнения ЛРП на основе использования генераторов Макларена-Марсальи с заявляемым способом трансляционного усложнения НЛРП в виде ККВ, существующих в простых полях Галуа GF(p), являются следующие:
i
V
j
B
формирование двух псевдослучайных последовательностей V={μ:i=1,…,L} и B=(b:j=1,…,L};
k
B
i
V
k
j
B
инициализация массива памяти R={r:k=1,…,L} путем заполнения элементами последовательности V={μ:i=1,…,L} ячеек памяти r, номера k которых определяются элементами последовательности В={b:j=1,…,L};
i
W
i
V
k
B
формирование выходной последовательности W={w:i=1,…,L} путем выборки элементов последовательности V={μ:i=1,…,L} из массива памяти R={r:k=1,…,L}.
0
1
i
L-1
1
q-1
Техническая реализация указанных сходных признаков при осуществлении заявляемого способа трансляционного усложнения НЛРП в виде ККВ, существующих в простых полях Галуа GF(p), требует возможности, во-первых, формирования элементов ККВ V={μ,μ,…,μ,…,μ}, длительности L=p, р - простое число, и во-вторых, формирования элементов мультипликативной группы B={b,…,b} поля GF(q).
n
Решение задачи формирования последовательности элементов мультипликативных групп как простых GF(p), так и расширенных GF(p) полей Галуа было осуществлено в рамках ряда устройств (А.С. №849895 (СССР). Устройство для формирования элементов мультипликативных групп полей Галуа // Сныткин И.И., Долгов В.И., Горбенко И.Д.; А.С. №1236497 (СССР). Устройство для формирования элементов мультипликативных групп полей Галуа // Сныткин И.И., Петренко В.И. - опубл. в Б.И. 1986, №21; А.С. №1334982 (СССР). Устройство для формирования элементов мультипликативных групп полей Галуа // Сныткин И.И., Горбенко И.Д., Ткач А.А.; Устройство для формирования элементов мультипликативных групп полей Галуа GF(p) // Патент RU 2007032 С1, опубл. 30.01.1994, Бюл. №28).
Методы и средства генерирования НЛРП, базирующиеся на использовании правил их построения, достаточно сложные и ориентированы на использование микропроцессорной техники. В работе (Сныткин И.И., Спирин А.В., Сныткин Т.И. Теоретическая концепция генерирования нелинейных рекуррентных последовательностей на основе использования регистров сдвига. - Международный научно-технический журнал «Нелинейный мир», №8, т. 11, 2013. - с. 531-539.) показывается, что регистр сдвига, снабженный некоторой «внутренней и внешней» логикой, может использоваться для генерирования любых ПСП с наперед заданными свойствами. Поэтому целесообразным путем технической реализации устройства для трансляционного усложнения НЛРП является использование средств формирования НЛРП на основе использования регистра сдвига.
Известны устройства формирования НЛРП фиксированных длительностей L на основе использования регистра сдвига (Устройство формирования словарей нелинейных рекуррентных последовательностей // Авторское свидетельство СССР №2024053, опубл. 30.11.1994. Бюл. №22; Устройство формирования кодовых словарей нелинейных рекуррентных последовательностей // Патент RU 2439657 С2, опубл. 10.01.2012. Бюл. №1).
Устройство для формирования имитостойких нелинейных рекуррентных последовательностей (Патент RU 2574805 С1, опубл. 10.02.2016. Бюл. №4) обеспечивает формирование различных словарей ККВ и их программную смену в процессе работы длительностью L=13. Возможность применения словарей НЛРП данной длительности, построенных на основе автоморфных, неинверсно-изоморфных и изоморфных преобразований исходной НЛРП с использованием программных принципов смены словарей НЛРП, обеспечивает высокую скрытность формируемых на их основе ШПС, что позволяет считать данное устройство близким аналогом (прототипом) к заявляемому устройству. Однако данное устройство не позволяет решать задачу трансляционного усложнения НЛРП в виде ККВ, существующих в простых полях Галуа GF(p).
Сходными признаками данного устройства (прототипа) с заявляемым устройством являются:
устройство содержит: блок формирования циклической последовательности символов (БФЦПС), состоящий из сумматора по модулю два, регистра сдвига, дешифратора и элемента задержки; блока внешней логики (БВЛ), включающего три элемента И и один элемент ИЛИ; блока управления (БУ), содержащего два регистра хранения, два счетчика, ключ и элемент ИЛИ, с соответствующими функциональными связями.
3. Раскрытие изобретения
В (Каневский З.М., Литвиненко В.П. Теория скрытности. - Воронеж: Воронежский государственный университет, 1991. - 144 с.) изложен метод определения структурной скрытности сигналов, в рамках которого оцениваются соответствующие временные и аппаратные затраты, необходимые для раскрытия структуры сигнала. При этом выделяют алгоритмическую и потенциальную структурные скрытности. Алгоритмическая структурная скрытность характеризуется средним числом двоичных измерений, необходимых для раскрытия структуры сигнала при заданном алгоритме. Потенциальная структурная скрытность определяется числом двоичных измерений, которые необходимо осуществить для раскрытия структуры сигнала.
c
Общее выражение для структурной скрытности (S) ШПС (Каневский З.М., Литвиненко В.П. Теория скрытности. - Воронеж: Воронежский государственный университет, 1991. - 144 с.):
сп
где V - арсенал сменных параметров ПСП, используемой для расширения спектра.
сп
j
a
из
При этом объем сменных параметров V ПСП фиксированной длительности L определяется количеством ее автоморфных V и изоморфных V преобразований в случае фиксированных изоморфизмов (Патент RU 2553057 С1. Устройство формирования систем двукратных производных нелинейных рекуррентных последовательностей // Сныткин И.И. и др., опубл. 10.06.2015, бюл. №16):
M
n
В случае, когда в качестве расширяющих спектр сигнала функций для создания ШПС используют М-последовательности (последовательности максимального периода), генерируемые посредством регистра сдвига с линейной обратной связью (РСЛОС), длительности L=2-1 (n=1,2,… - число ячеек РСЛОС и степень неприводимого первообразного полинома С(х), соответствующего вырабатывающему ее РСЛОС), число автоморфных преобразований М-последовательности фиксированной длительности  представляет собой число циклических сдвижек и равно длительности последовательности  Общее же число-арсенал сменных параметров М-последовательности фиксированной длительности  равен , где  - число изоморфных преобразований (невзаимных первообразных полиномов степени n), где ϕ(…) - функция Эйлера (Свердлик М.Б. Оптимальные дискретные сигналы. М.: изд-во «Советское радио», 1975, 200 с.).
Однако широко известно, что при помощи алгоритма Берлекэмпа-Месси можно полностью раскрыть структуру М-последовательности по определенному числу  точно известных последовательно расположенных ее элементов. Работа алгоритма Берлекэмпа-Месси основана на том положении, что n+1 последовательных состояний РСЛОС линейно зависимы, и если  символов М-последовательности заданы, то полином С(х), задающий обратные связи РСЛОС, однозначно определен. То есть элементы М-последовательностей линейно коррелируют друг с другом.
Данное обстоятельство существенным образом сокращает арсенал сменных параметров М-последовательности на величину числа .
n
Альтернативу М-последовательностям представляют существующие в простых GF(p) и расширенных GF(p) полях Галуа нелинейные рекуррентные последовательности (НЛРП), не генерируемые посредством РСЛОС. Алгоритм Берлекэмпа-Месси, предназначенный для работы с линейными логическими связями, неприменим при анализе НЛРП (Сныткин И.И., Спирин А.В., Сныткин Т.И. Теоретическая концепция генерирования нелинейных рекуррентных последовательностей на основе использования регистров сдвига. - Международный научно-технический журнал «Нелинейный мир», №8, т. 11, 2013. - с. 531-539).
n
Число автоморфных преобразований простых НЛРП  в виде кодов квадратичных вычетов (ККВ) или характеристических кодов (ХК), существующих в простых полях Галуа GF(p), представляет собой число циклических сдвижек простых НЛРП и равно , где простое число р>2. Общее же число-арсенал сменных параметров простых НЛРП фиксированной длительности  равен , где  - число изоморфных преобразований простых GF(p) и расширенных GF(p) полей Галуа.
j
Таким образом, для сравнимых по длительности L последовательностей :
i
i
Однако авторами был установлен ряд особенностей в правилах построения и формирования (генерирования) простых НЛРП в виде ККВ и выявлено, что элементы ККВ μ, номера i которых соответствуют простым числам (i∈P), коррелируют друг с другом на основе квадратичного закона взаимности (свойство квадратичной взаимности элементов ККВ L=23 проиллюстрировано на фигуре 1), а учитывая, что схема произведения квадратичных вычетов и невычетов аналогична схеме сложения для «четного и нечетного» (Хассе Г. Лекции по теории чисел. - М.: изд-во Наука, 1953. - 528 с.), то полностью восстановить структуру любого кода можно на основе указанных ее элементов μ (i∈Р) (свойство взаимной мультипликативности элементов ККВ L=23 проиллюстрировано на фигуре 2).
Данное обстоятельство указывает на то, что при разработке соответствующего алгоритма раскрытия структуры последовательностей существенным образом сократится арсенал сменных параметров НЛРП.
c
Следовательно, для повышения структурной скрытности (S) ШПС на базе НЛРП, существующих в простых полях Галуа GF(p), необходимо, во-первых, увеличивать арсенал сменных параметров  НЛРП фиксированных длительностей , а во-вторых, уменьшать степень корреляции элементов последовательностей.
Одним из способов решения указанных задач является предлагаемое трансляционное усложнение НЛРП.
Существенными отличительными признаками известного способа (прототипа) усложнения ЛРП на основе использования генераторов Макларена-Марсальи с заявляемым способом трансляционного усложнения нелинейных рекуррентных последовательностей в виде кодов квадратичных вычетов, существующих в простых полях Галуа GF(p), являются следующие:
1
р
1
НЛРП
формируется нелинейная рекуррентная последовательность в виде кода квадратичных вычетов V={μ,…,μ}, μ=1, существующих в простых полях Галуа GF(p), длительности 1=р, р - простое число, с учетом всевозможных автоморфных и изоморфных преобразований {V};
1
р
из набора всевозможных автоморфных и изоморфных преобразований {V} сформированного кода квадратичных вычетов определяется конкретная исходная для последующего усложнения последовательность V={μ,…,μ};
1
ϕ(q-1)
формируется массив F={f,…,f} первообразных элементов поля GF(q);
1
q-1
i
i-1
1
q-1
формируется мультипликативная группа B={b,…,b} простого поля Галуа GF(q), в соответствии с рекуррентным соотношением b=b⋅f(modq), b=f, b=1, f - первообразный элемент поля GF(q);
1
q-1
1
р
из набора всевозможных автоморфных преобразований {В} сформированной мультипликативной группы простого поля Галуа GF(q) определяется конкретная мультипликативная группа B={b,…,b}, которая будет использоваться для последующего усложнения последовательности V={μ,…,μ};
j
1
q-1
инициализируется массив памяти R, размером , путем трансляции с каждым шагом  (циклически) элемента ККВ μ в массив памяти R на позицию, равную значению j-го элемента мультипликативной группы В={b,…,b} поля GF(q);
HЛРП
j-1
k=1
на каком-либо шаге j=m⋅1+(q-1), m=1,2,… элемент μ кода квадратичных вычетов транслируется в первую ячейку памяти r, что свидетельствует о том, что все ячейки массива памяти R заполнены элементами кода квадратичных вычетов;
i
формируется (q-1) первых элементов трансляционной нелинейной рекуррентной последовательности W={W:i=1,…,q-1} путем выборки элементов кода квадратичных вычетов из массива памяти R: ;
1
q-1
k=1
после окончания выборки (q-1) первых элементов трансляционной нелинейной рекуррентной последовательности, элементы кода квадратичных вычетов продолжают транслироваться в массив памяти R на позиции, равные значениям элементов мультипликативной группы B={b,…,b} поля GF(q), пока заново ячейка памяти r не будет заполнена;
i
формируется (q-1) вторых элементов трансляционной нелинейной рекуррентной последовательности W={W:i=(q,…,h⋅(q-1)}, h=2 путем выборки элементов кода квадратичных вычетов из массива памяти R: ;
i
НЛРП
последние (q-1) элементов трансляционной нелинейной рекуррентной последовательности W={W:i=(р-1)⋅(q-1)+1,…,р⋅(q-1)} формируются, когда h становится равным h=1=р.
4. Краткое описание чертежей
На фигуре 1 изображено свойство квадратичной взаимности элементов ККВ L=23.
На фигуре 2 изображено свойство взаимной мультипликативности элементов ККВ L=23.
На фигуре 3 изображен алгоритм трансляционного усложнения нелинейных рекуррентных последовательностей в виде кодов квадратичных вычетов, существующих в простых полях Галуа GF(p).
На фигуре 4 изображены графики и статистические характеристики АКФ ТНЛРП и ККВ сравнимых длительностей L.
На фигуре 5 изображены графики ВКФ изоморфных ТНЛРП различных длительностей L.
На фигуре 6 изображена функциональная схема устройства для трансляционного усложнения НЛРП в виде ККВ, существующих в простых полях Галуа GF(p).
На фигуре 7 изображена функциональная схема формирователя элементов мультипликативной группы простого поля Галуа GF(q).
5. Осуществление изобретения
Заявляемый способ характеризуется в приведенном на рисунке 3 алгоритме следующей совокупностью последовательных действий (этапов):
Этап 1. Формирование НЛРП в виде ККВ, существующих в простых полях Галуа GF(p) (блоки 3-6 на рисунке 3).
Построение ККВ базируется на использовании двузначного характера мультипликативной группы простого поля GF(p), с длительностью L=p и правилом построения в терминах характеров (Свердлик М.Б. Оптимальные дискретные сигналы. М.: изд-во «Советское радио», 1975, 200 с.):
В (Сныткин И.И. Теория и практическое применение сложных сигналов с нелинейной структурой. Часть 4, - 1990. - 128 с.) разработан способ формирования ККВ, позволяющий избежать трудностей в вычислении характеров, индексов или символов Лежандра.
Сначала вычисляется значение θ минимального первообразного элемента поля GF(p) (блок 3 на рисунке 3).
В соответствии с рекуррентным соотношением:
1
р-1
формируется мультипликативная группа А={а,…,а} поля GF(p) (блок 4 на рисунке 3).
1
i
р
1
i
i
Формирование НЛРП квадратичных вычетов (V={μ,…,μ,…,μ}, μ=1) означает присвоение элементам μ (значение меандра ψ(1,-1) (или ψ(1,0)) на позиции i=a (блок 5 на рисунке 3).
Этап 1 завершается определением из набора всевозможных автоморфных и изоморфных преобразований {V} сформированного ККВ исходной для последующего усложнения последовательности (блок 6 на рисунке 3).
Этап 2. Формирование мультипликативной группы простого поля Галуа GF(q) (блоки 7-10 на рисунке 3).
1
ϕ(q-1)
1
q-1
1
q-1
Формируется массив F={f,…,f} первообразных элементов поля GF(q) (блок 7 на рисунке 3). Выбор конкретного значения f первообразного элемента поля GF(q) (блок 8 на рисунке 3) означает определение конкретной мультипликативной группы B={b,…,b} из набора всевозможных изоморфных преобразований {В}. По аналогии с соотношением (6) мультипликативная группа B={b,…,b} поля GF(q) (блок 9 на рисунке 3) формируется в соответствии с рекуррентным соотношением:
и определяется автоморфное преобразование мультипликативной группы из набора {В} (блок 10 на рисунке 3).
1
i
p
1
Этап 3. Трансляционное усложнение ККВ V={μ,…,μ,…,μ}, μ=1 (блоки 11-17 на рисунке 3).
j
1
q-1
1
q-1
i
Инициализируется массив памяти R, размером , путем трансляции с каждым шагом  (циклически) элемента ККВ μ в массив памяти R на позицию, равную значению j-го элемента мультипликативной группы B={b,…,b} поля GF(q) (блоки 12-16 на рисунке 3). Тем самым формируется массив R={r,…r} (q-1) первых (h=1) элементов трансляционной НЛРП W={W:i=1,…,q-1}.
i
i
Затем этап 3 повторяется заново (блоки 12-16 на рисунке 3), значение h увеличивается на единицу, формируется (q-1) следующих (h=2) элементов трансляционной НЛРП W={W:i=q,…,2⋅(q-1)}. Так происходит, пока h не станет равным р, и не будут сформированы последние (q-1) (h=p) элементов трансляционной НЛРП W={W:i=(р-1)⋅(q-1)+1,…,р⋅(q-1)}.
i
Введем определение для получившейся последовательности W={W:i=1,…,p⋅(q-1)}.
i
НЛРП
j
НЛРП
1
q-1
i
i-1
1
Определение. Трансляционной НЛРП вида W={W:i=1,…,L}, L=1⋅(p-1), называется такая последовательность, которая образуются путем трансляции элементов простой НЛРП вида V={V:j=1,…,1}, существующей в простом поле Галуа GF(p), на позиции, равные значениям элементов мультипликативной группы B={b,…,b} простого поля Галуа GF(q), построенной в соответствии с рекуррентным соотношением b≡b⋅f(modq), b=f, f - первообразный элемент поля GF(q).
Число автоморфных преобразований ТНЛРП  представляет собой число циклических сдвижек ТНЛРП и равно .
Число изоморфных преобразований ТНЛРП равно произведению:
где  - число изоморфизмов поля GF(q),  - число автоморфизмов поля GF(q).
Общее же число-арсенал сменных параметров ТНЛРП фиксированной длительности  равен:
Отсюда видно, что объем арсенала сменных параметров (при близких по значениям ), у ТНЛРП больше, чем у НЛРП, в  раз.
Кроме того, по аналогии с последовательностями, формируемыми генератором Макларена-Марсальи, элементы ТНЛРП почти не будут взаимозависимы друг от друга, даже если длительность L последовательности не существенна (Кнут Дональд Эрвин. Искусство программирования, Т. 2. Получисленные алгоритмы, 3-е изд.: Перевод с английского: Учебное пособие. - М.: Издательский дом «Вильямс», 2001. - 832 с.: ил. - Парал. тит. англ. ISBN 5-8459-0081-6 (рус.)).
Помимо структурных свойств к основным характеристикам ШПС относятся их корреляционные свойства (автокорреляционные функции (АКФ) и взаимокорреляционные функции (ВКФ), и их характеристики).
бmax
бmin
Ввиду того, что ШПС на базе ККВ обладают оптимальными по соответствующим критериям корреляционными свойствами (Свердлик М.Б. Оптимальные дискретные сигналы. М.: изд-во «Советское радио», 1975, 200 с.), на рисунке 5 для сравнения представлены графики АКФ и их статистические характеристики (U - значение максимального положительного бокового выброса (БВ), U - значение максимального (по модулю) отрицательного бокового выброса, М(Х) - математическое ожидание, d - среднеквадратическое отклонение, D - дисперсия бокового выброса) для некоторых сравнимых по длительности L ККВ и ТНЛРП.
На рисунке 6 в целях наглядности возможности применения ШПС на базе ТНЛРП представлены графики ВКФ для некоторых из синтезированных и исследованных систем ТНЛРП.
Целью, достигаемой устройством для трансляционного усложнения НЛРП является расширение функциональных возможностей устройства для формирования имитостойких НЛРП по выполнению функций трансляционного усложнения НЛРП, формирования различных кодовых словарей трансляционных НЛРП и их программной смены в процессе работы.
Цель достигается тем, что в устройство для формирования имитостойких НЛРП, содержащее: блок формирования циклической последовательности символов, включающий сумматор по модулю два, регистр сдвига, дешифратор и первый элемент задержки; блок внешней логики, включающий три элемента И и первый элемент ИЛИ; блок управления, включающий два регистра хранения, два счетчика, ключ и второй элемент ИЛИ, - причем вход кода начальной фазы блока управления соединен с информационными входами первого регистра хранения, соответствующие выходы которого соединены с информационными входами регистра сдвига, вход записи которого соединен с выходом сумматора по модулю два, первый вход которого соединен с выходом первого элемента задержки, вход которого соединен с выходом дешифратора, соответствующие информационные входы которого соединены с соответствующими информационными выходами регистра сдвига, третий информационный выход которого соединен со вторым входом сумматора по модулю два, третий вход которого соединен с четвертым информационным выходом регистра сдвига, третий выход и четвертый инверсный выход которого соединены со входами первого элемента И, выход которого соединен с первым входом первого элемента ИЛИ, второй вход которого соединен с выходом второго элемента И, входы которого соединены со вторым и третьим информационными выходами регистра сдвига, второй выход и четвертый инверсный выход которого соединены со входами третьего элемента И, выход которого соединен с третьем входом первого элемента ИЛИ, соответствующие информационные выходы регистра сдвига соединены с информационными входами первого регистра хранения, вход записи которого соединен со входом записи исходного состояния блока управления, входом записи второго регистра хранения, вторым входом ключа и выходом переполнения второго счетчика, управляющий вход которого соединен с управляющим входом регистра хранения и выходом второго элемента ИЛИ, первый вход которого соединен с управляющим и счетным входами первого счетчика, выход переполнения которого соединен со входом начала работы блока управления, вторым входом второго элемента ИЛИ, входами записи первого и второго регистров хранения, первым и третьим входами ключа, выход которого соединен со счетным входом второго счетчика, соответствующие информационные входы которого соединены с соответствующими информационными выходами второго регистра хранения, информационные входы которого соединены со входом записи кода шифра словаря блока управления, введены: блок трансляционного усложнения, включающий формирователь элементов мультипликативной группы поля, второй элемент задержки, блок памяти, третий элемент ИЛИ и третий счетчик, причем вход записи значения первообразного элемента поля блока трансляционного усложнения соединен с первой группой информационных входов формирователя элементов мультипликативной группы поля, выход блока памяти соединен с выходом последовательности элементов трансляционной нелинейной рекуррентной последовательности блока трансляционного усложнения, выход первого элемента ИЛИ соединен с первым информационным входом блока памяти, соответствующие информационные входы которого соединены с соответствующими информационными выходами формирователя элементов мультипликативной группы поля, первый выход которого соединен со входом второго элемента задержки, выход которого соединен с первым входом второго элемента ИЛИ, первым входом третьего элемента ИЛИ, входом формирования следующего элемента мультипликативной группы поля формирователя мультипликативной группы поля и входом записи блока памяти, вход считывания которого соединен о входом переполнения третьего счетчика, управляющий и счетный входы которого соединены с выходом третьего элемента ИЛИ, второй вход которого соединен со входом начала работы блока управления и управляющим входом формирователя элементов мультипликативной группы поля, вторая группа соответствующих информационных входов которого соединена с информационными входами третьего счетчика и входом записи значения простого числа.
Функциональная схема устройства для трансляционного усложнения НЛРП в виде ККВ, существующих в простых полях Галуа GF(p), представлена на рисунке 6.
Устройство содержит:
блок 1 формирования циклической последовательности символов (БФЦПС), состоящий из сумматора 2 по модулю два, регистра 5 сдвига, дешифратора 3 и элемента 4 задержки;
блок 6 внешней логики (БВЛ), включающий три элемента 7-9 И и один элемент 10 ИЛИ;
блок 11 управления (БУ), содержащий два регистра хранения 12 и 13, два счетчика 13 и 16, ключ 15 и элемент 17 ИЛИ;
блок 18 трансляционного усложнения (БТУ), содержащий формирователь 19 элементов мультипликативной группы поля GF(q) (ФЭМГП), элемент 20 задержки, блок 21 памяти, элемент 22 ИЛИ и счетчик 23, с соответствующими функциональными связями.
Устройство работает следующим образом.
Этап 1 формирования НЛРП в виде ККВ, существующих в простых полях Галуа GF(p) (блоки 3-6 на рисунке 3) и этап 2 формирования мультипликативной группы простого поля Галуа GF(q) (блоки 7-10 на рисунке 3) устройством выполняются параллельно. При этом с каждым тактом БУ 6 формирует один элемент последовательности и ФЭМГП 19 формирует один элемент мультипликативной группы поля GF(q).
1
q-1
ФЭМГП 19 предназначен для формирования мультипликативной группы B={b,…,b} поля GF(q) (блок 9 на рисунке 3) и может быть сконструирован в соответствии с функциональной схемой устройства для формирования элементов мультипликативных групп полей Галуа GF(p) (Патент RU 2007032 С1, опубл. 30.01.1994, Бюл. №28), представленной на рисунке 7.
Перед началом работы на вход 26 устройства поступает код исходной начальной фазы для состояния разрядов регистра 5, на вход 29 устройства поступает код первообразного элемента f поля GF(q), на вход 30 устройства поступает код простого числа q, являющегося характеристикой поля GF(q).
В первый тактовый момент с помощью синхроимпульса «Запись исходного состояния», подаваемого на вход 26 устройства и дальше на вход записи регистра 12, код исходной начальной фазы записывается в регистр 12. Во второй тактовый момент на вход 27 поступает импульс «Начало работы», который, пройдя на вход считывания регистра 12, обеспечивает списывание кода начальной фазы из регистра 12 в регистр 5, а пройдя через элемент ИЛИ 17 на вход записи регистра 5, обеспечивает запись кода начальной фазы в регистр 5. Одновременно код начальной исходной фазы появляется на выходах регистра 5.
1
Также импульс «Начало работы» проходит на вход запуска ФЭМГП 19, обеспечивает запись в него кода первообразного элемента f и кода простого числа q, и устройство формирует первый элемент мультипликативной группы поля GF(q) (b=f), код которого поступает на второй вход бока 21 памяти. По окончании формирования элемента мультипликативной группы поля GF(q) с выхода 1 ФЭМГП 19 формируется импульс, который, пройдя через элемент задержки 20, поступает на вход записи блока 21 памяти, а также через элемент ИЛИ 17, на вход регистра 5, обеспечивая последовательное изменение состояний разрядов регистра 5 в соответствии с функцией внутренней логики.
Время задержки элемента 20 задержки выбирается несколько больше формирования БВЛ 6 следующего элемента последовательности для исключения ложных срабатываний блока 21 памяти.
В последующие тактовые моменты, с третьего по пятнадцатый импульсы с выхода 1 ФЭМГП 19, поступающие на вход регистра 5 через элемент ИЛИ 17, обеспечивают последовательное изменение состояний разрядов регистра 5 в соответствии с функцией внутренней логики так, что, начиная с шестнадцатого такта, состояния разрядов регистра 5 повторяются. Таким образом, с периодом L=13 обеспечивается повторение состояний разрядов регистра.
Формирование при этом циклической последовательности символов кода длительностью L=13 обеспечивается с помощью элементов 7-10 БВЛ 6.
Таким образом, поступающие на вход 1 блока 21 памяти элементы циклической последовательности символов записываются по адресам, соответствующим элементам мультипликативной группы поля GF(q).
Импульсы с выхода 1 ФЭМГП 19 через элемент ИЛИ 22 поступают также на счетный вход счетчика 23, коэффициент пересчета которого прежде устанавливается кодом числа q-1. После окончания записи в блок 21 памяти q-1 символов последовательности, счетчик переполняется и формирует на своем выходе импульс, который поступает на вход считывания блока 21 памяти. На выходе 24 устройства формируется q-1 первых элементов ТНЛРП.
Определение из набора всевозможных автоморфных и изоморфных преобразований {V} сформированного ККВ исходной для последующего усложнения последовательности (блок 6 на рисунке 3) предусмотрено в БУ 11 за счет режимов формирования определенного типа словаря НЛРП и формирования различных словарей НЛРП.
Для НЛРП с L=13 имеются два инверсных изоморфизма, остальные (12) - автоморфные преобразования, которые представляют собой циклические сдвижки каждого неинверсного изоморфизма. В нашем случае инверсным изоморфизмом является НЛРП=(1011000011011), формирование которого обеспечивается устройством при начальной фазе регистра 5 «1011». Для формирования других (автоморфных) НЛРП достаточно обеспечить начало формирования НЛРП не с начальной фазы «1011», а с начальной фазы такой, которая соответствует какому-либо промежуточному состоянию разрядов регистра 5.
Характер словаря НЛРП, таким образом, зависит от того, какая начальная фаза устанавливается в регистре 5 после того, как были сформированы какие-то определенные (предыдущие) НЛРП. Порядок чередования (выбора) начальных фаз таким образом, определяет вид формируемого словаря НЛРП. Он может состоять только из одних постоянно формируемых НЛРП, только из двух постоянно формируемых НЛРП, только из трех НЛРП и т.д., и в конце концов из двенадцати НЛРП. В порядок чередования (выбора) начальных фаз таким образом закладываются свойства имитостойкости и скрытности. Оптимальными в этом смысле являются словари, построенные с помощью такого порядка чередования НЛРП, который носит псевдослучайный характер. Однако в любом конкретном случае, определяемом условиями функционирования, должна иметься возможность изменять этот порядок.
Эти возможности и реализованы в устройстве с помощью запоминания в регистре 12 промежуточного состояния регистра 5 в соответствии с кодом шифра словаря, подаваемого на вход кода шифра устройства. Так, например, в первый тактовый момент в регистр 14 заносится код цифры 7 (1110), что означает, что в регистре 12 после начала формирования первой НЛРП запомнено третье промежуточное состояние регистра 5 (в нашем случае это будет пятый тактовый момент). Счетчик 14, в который записан код цифры 7 (1110) в качестве его начального состояния, переполняется и выдает импульс переполнения через три тактовых импульса. Затем по окончании формирования первых НЛРП запомненное промежуточное состояние регистра 5 считывается из регистра 12 опять в регистр 5, но уже в качестве его начальной фазы. После этого начинается процесс формирования других НЛРП. Если к этому моменту не изменять код шифра словаря, то в последующем запоминается в регистре 12 каждое третье промежуточное состояние регистра 5 и затем считывается в регистр 5 в качестве его начальной фазы. Например, порядок чередования типа «каждая третья фаза» перебирает в конце концов (спустя одиннадцать циклов) всевозможные начальные фазы, такие как и любой другой порядок «каждая n-я фаза», где n=2,3,…,13, а порядок типа «каждая первая фаза» обеспечивает формирование словарей, состоящих только из одной определенной НЛРП. Таким образом, числом в законе «каждая n-я фаза» закладывается порядок чередования начальных фаз, т.е. чередования НЛРП в словаре, т.е., характер (тип) словаря НЛРП.
В режиме формирования различных словарей НЛРП в первый тактовый момент в регистр 14 записывается код шифра словаря в виде двоичного кода ключевой цифры (например «7» - «1110»), при этом ключ 15 закрывается. Во второй тактовый момент синхроимпульс «Начало работы» открывает ключ 15 и, проходя на второй вход регистра 14 и через элемент ИЛИ 17 на первый синхровход счетчика 16, обеспечивает считывание из регистра 14 в счетчик 16 код цифры 7 (1110). В третий тактовый момент вместе с началом формирования первых НЛРП тактовые импульсы с выхода ФЭМПГ 19 поступают в счетчик 13, а через открытый ключ 15 - на счетный вход счетчика 16 и через элемент ИЛИ 17 - на синхровход счетчика 16. Так как в счетчике 16 записано состояние «7» (1110), то спустя три такта на его выходе появляется импульс переполнения, который закрывает ключ 15, придя на первый вход регистра 14, обеспечивает запись в регистр 14 кода другой цифры, а придя на первый вход регистра 12, обеспечивает запись третьего промежуточного состояния регистра 5. Если код шифра (код цифры) не изменяется, то состояние регистра 14 не изменяется в этот тактовый момент. Спустя тринадцать тактовых импульсов с выхода ФЭМГП 19, на выходе счетчика 16 появляется импульс переполнения, который открывает ключ 15, придя на второй вход регистра 14, обеспечивает считывание кода цифры 7 в счетчике 16, а также, пройдя на второй вход регистра 12, обеспечивает считывание с него на входы регистра 5 кода запомненной начальной фазы. Таким образом, в пятнадцатый тактовый момент заканчивается формирование первых НЛРП, и устройство подготавливается для формирования последующих НЛРП из данного словаря определенных шифром-цифрой «7».
3
Начиная с шестнадцатого тактового момента, начинается формирование НЛРП, определяемых начальной фазой «1111», которая является промежуточным состоянием регистра 5 в пятый тактовый момент. Эти НЛРП имеют вид μ=(0111011000011) и тем самым представляют трехсимвольный сдвиг влево исходных НЛРП.
Таким образом, процесс формирования НЛРП продолжается по ранее описанному принципу так, что через каждые тринадцать тактов формируются новые НЛРП, сдвинутые от предыдущих на три символа влево.
1
q-1
Подача на вход 29 устройства определенного значения f первообразного элемента поля GF(q) (блок 8 на рисунке 3) означает определение конкретной мультипликативной группы В={b,…,b} из набора всевозможных изоморфных преобразований {В}.
Таким образом, работа устройства продолжается, и через каждые q-1 тактов на выходе 24 устройства формируется q-1 последующих элементов ТНЛРП.