Построение и исследование алгебраических характеристик скрученных линейных рекуррентных последовательностей максимального периода над кольцами Галуа тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Зайцев, Сергей Николаевич

• Зайцев, Сергей Николаевич
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Зайцев, Сергей Николаевич

Оглавление

Введение

Глава 1. Методы построения скрученных рекуррент максимального периода над кольцами Галуа

§ 1.1 Постановка задачи и обзор предшествующих результатов

§ 1.3 Построение скрученных рекуррент максимального периода

методом определяющих многочленов

§ 1.4 Выводы по главе 1

Глава 2. Основные криптографические свойства скрученных

рекуррент максимального периода

§ 2.1 Основные понятия и свойства мультипликаторов скрученных

рекуррент максимального периода

§ 2.2 Связь поля мультипликаторов и линейной сложности скрученных рекуррент максимального периода

§ 2.3 Условия нелинеаризуемости и нередуцируемости

§ 2.4 Конструктивное построение нередуцируемых многочленов максимального периода

§ 2.5 Частотные и корреляционные свойства усложнений скрученных рекуррент максимального периода

§ 2.6 Выводы по главе 2

Глава 3. Восстановление скрученных рекуррент по старшей

разрядной последовательности

§ 3.1 Постановка задачи и обзор предшествующих результатов

§ 3.3 Восстановление скрученной рекурренты максимального периода над кольцом Галуа четной характеристики

§ 3.4 Восстановление скрученной рекурренты максимального периода по усложнению комбинации знаков старшего разряда

усложнению разрядов одного знака

§3.6 Матричный подход к восстановлению скрученных рекуррент

§ 3.7 Выводы по главе 3

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Построение и исследование алгебраических характеристик скрученных линейных рекуррентных последовательностей максимального периода над кольцами Галуа»

Введение

Поточные шифры играют важную роль в современной симметричной криптографии, особенно в случае применения высокоскоростного шифрования. В дополнение к высокой скорости поточные шифры не распространяют искажений, а также доказана их гарантированная стойкость при условии, что ключевая последовательность близка к случайной (К. Шеннон, [4]). При этом генерация действительно случайного ключевого потока (например посредством физических шумов) вызывает значительные трудности в организации обмена ключами, так как в этом случае их необходимо предварительно сгенерировать в большом объеме и физически доставить получателю.

Альтернативой такого подхода являются генераторы псевдослучайных последовательностей (ПСП), то есть последовательностей, генерируемых известным заранее определенным алгоритмом при подаче на вход некоторого ключа. Наиболее распространенным, легко реализуемым и в то же время надежным способом генерации таких последовательностей является построение одной или нескольких линейных рекуррент над кольцом Галуа (в частности над конечным полем или примарным кольцом вычетов) и в последующем их усложнении. Литературу, обосновывающую такой подход, трудно перечислить полностью. Здесь мы ограничимся указанием работ [7,11,12,14-17,19,21,22,24-26,35].

В связи со значительным расширением возможностей современных вычислительных устройств, а именно, с увеличением оперативной памяти, длины машинного слова и количества ядер процессоров, а также с улучшением технологий параллелизации, представляет интерес более эффективная реализация генератора ПСП, оперирующая векторами. В частности, реализация линейных рекуррент над кольцами Галуа большой мощности на современных процессорах будет гораздо эффективнее, если их элементы представлять в виде векторов над кольцом Галуа маленькой мощности, а умножение осуществлять матрично. Помимо матричной реализации умножения элементов

кольца Галуа существует еще табличная реализация и реализация с помощью преобразования Фурье. Но табличная реализация занимает много памяти, а преобразование Фурье не поддается распараллеливанию.

В таком контексте, очевидно, соответствующие матричные коэффициенты можно выбирать из всего множества матриц, а не только из тех, которые отвечают умножению на константу кольца Галуа. Произвол в выборе матриц естественным образом обобщает концепцию классических линейных рекуррент (скрученные линейные рекурренты). Таким образом можно заключить, что реализация скрученных линейных рекуррент не сложнее реализации классических линейных рекуррент.

Стоит заметить, что такие регистры сдвига будут вообще говоря нелинейными и для использования полученных последовательностей в качестве одного из узлов гаммообразующих устройств необходимо максимально полно изучить структуру и характеристики таких последовательностей, как то: период, линейная сложность, мультипликаторы, редуцированный период, частотные и корреляционные свойства, и т.д. Таким образом, необходимо развивать методы построения матричных регистров сдвига, обладающих гарантированными криптографическими свойствами, в частности, имеющих максимальный редуцированный период (нередуцируемые рекурренты).

Помимо исследования статистических и корреляционных свойств скрученных рекуррент для использования их в качестве ключевой информации необходимо дополнительное аналитическое обоснование сложности восстановления ключа. Поэтому на практике к рекуррентам применяется функция усложнения. При этом полученный генератор не должен иметь эквивалентных состояний (заполнений регистра). В работах [7,11,15-22,24] были получены результаты, подтверждающие хорошие статистические свойства и сложное аналитическое строение (большую линейную сложность) псевдослучайных последовательностей, полученных полиномиальным усложнением разрядов классических линейных рекуррент максимального периода над кольцами Галуа и, в частности, над примарными кольцами вычетов. Резуль-

таты по изучению рангов скрученных рекуррент максимального периода и их разрядных последовательностей опубликованы в [28,42,70]. В рамках данного диссертационного исследования в качестве кандидатов на функции усложнения рассматриваются полиномиальные функции от разрядов (в некотором разрядном множестве) матричных рекуррент.

Актуальность выбранной темы диссертации обусловлена необходимостью исследования криптографических характеристик псевдослучайных, в частности, рекуррентных последовательностей над кольцами Галуа и их усложнений; обоснования методов построения последовательностей большого периода с помощью нелинейных преобразований.

Степень научной разработанности проблемы. Изучением матричных регистров сдвига, имеющих максимально возможный период, а также восстановлением разрядноусложненных линейных рекуррент занимались такие ученые, как Нечаев В.И., Глухов М.М., Нечаев А.А., Кузьмин А.С., Куракин В.Л., Михалев А.В., Анашин В.С., Викторенков В.Е., Каморин В.В., Пронькин Д.А., Ларин М.Д., Маршалко Г.Б., Былков Д.Н., Цыпышев В.Н., H. Krawczyk, B. Preneel, B. Schneier, H. Niederreiter, B. Tsaban, U. Vishne, G. Zeng, W. Han, K. He, X. Liu, G. Tan, M. Zhang, M. Huang, Z. Dai, X. Zhu, W. Qi, T. Tian, J. Yang, J. Zhou, Shudhir R.G., Sartaj UL H., Kumari M., Ram S. (см. [7,11,30,31,33,34,36-45,50,51,54-56,59,61-64]).

Исследования скрученных рекуррент максимального периода проводились исключительно для случая, когда S — поле и в основном при R = GF(2). Основной целью исследований было построение скрученных МП-многочленов и изучение линейной сложности скрученных МП ЛРП. В работе [47] было найдено точное количество МП-многочленов над полем при заданных параметрах S, R,m, но доказательство соответствующей формулы имеет комбинаторный характер и не является конструктивным, т.е. не удается воспользоваться этим доказательством для построения классов скрученных МП ЛРП без перебора законов рекурсии и проверки отбраковывающих условий. Во всех, известных автору, работах построение скрученных МП-многочленов

имело переборный характер, за исключением одного небольшого конструктивно построенного в [45] класса (для R = GF(2)). Этот класс был независимо и одновременно построен автором в [70] совместно с Нечаевым А.А. и Гольтваницей М.А. (для произвольного R).

Что касается линейной сложности скрученных МП ЛРП, то в предшествующих работах было показано, что ее величина равна mk, для k £ 1 , n, где n = [S : R]. Гольтваницей М.А. было показано [70, Theorem 4], что k может принимать любое значение из 1,n (в зависимости от конкретной ре-курренты), и был предъявлен метод построения небольшого класса МП ЛРП, для которых k = n. Тем не менее, линейная сложность рекуррент из этого класса остается равной m при применении к каждому знаку одного и того же обратимого линейного преобразования. Краткий обзор предшествующих результатов приведен в § 1.1 данной работы.

Объектом исследования являются псевдослучайные последовательности, получаемые усложнением скрученных ЛРП над кольцами Галуа.

Предметом исследования являются криптографические свойства скрученных ЛРП над кольцами Галуа, а также их усложнений.

Целью диссертации является развитие методов описания алгебраических свойств скрученных ЛРП максимального периода (МП ЛРП), нахождение способов построения классов скрученных МП-многочленов, порождающих последовательности с гарантированными криптографическими свойствами, а также обоснование способов выбора параметров вышеописанного блока выработки гаммы (БВГ), при которых будет гарантировано отсутствие эквивалентных ключей.

Достижение поставленной цели потребовало решения следующих научных задач исследования.

1. В части развития методов описания свойств скрученных МП ЛРП

(а) Получения критерия свойства «быть скрученной МП ЛРП» через наложение ограничений на ее координатные последовательности.

(b) Сведение задачи описания отдельных свойств скрученных МП ЛРП к задаче описания свойств множеств их мультипликаторов.

(c) Сведение задачи построения множества МП ЛРП, к задаче построения его классов эквивалентности по отношению линейной эквива-летности.

(^ Описание свойств сечений скрученных МП ЛРП в терминах их матричного представления.

2. В части построения новых классов МП-многочленов.

(a) Построение классов скрученных МП-многочленов без применения переборных методов.

(b) Построение классов скрученных МП-многочленов, порождающих последовательности, гарантированно имеющие максимальную линейную сложность.

3. В части обоснования выбора параметров БВГ, гарантирующих отсутствие эквивалентных ключей.

(a) Обоснование способов выбора усложняющих преобразований в случае использования кольца Галуа нечетной характеристики.

(b) Обоснование способов выбора законов рекурсии в случае использования кольца Галуа четной характеристики и старшей разрядной функции в качестве функции усложнения.

Научная новизна. Для случая конечных полей в одной из предшествующих работ [47] было найдено точное количество МП-многочленов при заданных параметрах, но доказательство соответствующей формулы имеет комбинаторный характер и не является конструктивным, т.е. не удается воспользоваться этим доказательством для построения классов скрученных МП ЛРП без тотального перебора законов рекурсии и проверки каких-либо отбраковывающих условий. В первой главе диссертации работы представлены способы

построения новых классов МП-многочленов, исключающие переборные методы. В том числе впервые предъявляются способы построения классов МП-многочленов, генерирующих последовательности с максимальной линейной сложностью, неуменьшаемой действием какого-либо линейного преобразования.

Изучение свойств скрученных рекуррент и перенос известных результатов для классических линейных рекуррент на случай скрученных рекур-рент затрудняет в первую очередь некоммутативность кольца коэффициентов. Поэтому в главе 2 представленной работы производится развитие алгебраических методов исследования скрученных рекуррент, не использующих свойства коммутативности. В частности, в работе впервые описана структура множества мультипликаторов скрученной МП ЛРП. Показано, что это множество зависит от конкретной рекурренты, тогда как для классических МП ЛРП это множество определено однозначно. Обоснована максимальная линейная сложность для тех МП ЛРП, множество мультипликаторов которых минимально по мощности. Также в работе впервые обобщены некоторые оценки частот встречаемости знаков на отрезках классических МП ЛРП и их усложнениях для скрученных МП ЛРП.

В главе 3 диссертации впервые обобщен ряд результатов по восстановлению начального заполнения МП ЛРП по ее полиномиально-разрядному усложнению, полученных А.А. Нечаевым, А.С. Кузьминым и их учениками для случая скрученных МП ЛРП. Показано, что при некоторых ограничениях такое восстановление однозначно, т.е. соответствующий БВГ не имеет эквивалентных ключей. Приводятся соответствующие алгоритмы восстановления.

Теоретическая и практическая значимость диссертации определяется

1. развитием теории линейных рекуррент над некоммутативным модулем;

2. описанием новых классов скрученных МП-многочленов;

3. распространением некоторых ранее известных результатов по восстанов-

лению усложненных ЛРП на случай скрученных ЛРП.

Работа носит теоретический характер.

Методы исследования. Для решения задач исследования применяются методы теории линейной алгебры, теории колец и модулей, проводятся эксперименты на ЭВМ.

Основные результаты, выносимые на защиту

1. методы построения многочленов, генерирующих МП ЛРП, в частности, нередуцируемые МП ЛРП;

2. критерий свойства «быть скрученной МП ЛРП» в терминах координатных последовательностей, обобщение свойств множества мультипликаторов классических ЛРП для случая скрученных МП ЛРП, а также связь между линейной сложностью и мощностью множества мультипликаторов;

3. обоснование способов выбора параметров БВГ, гарантирующих отсутствие эквивалентных ключей.

Степень достоверности и апробация результатов. Достоверность полученных результатов определяется наличем строгих математических доказательств. Основные результаты диссертационного исследования апробированы:

1. на симпозиуме СТСгур1 2012 (1-3 июля 2012г.)

2. на симпозиуме СТСгур! 2014 (24-26 июня 2014г.)

3. на симпозиуме СТСгур! 2015 (3-5 июня 2015г.)

4. на симпозиуме СТСгур! 2016 (6-8 июня 2016г.)

5. на научном семинаре «Кольца и модули» (механико-математический факультет МГУ имени М.В. Ломоносова) в 2015 и 2017 годах.

Публикации. Основные результаты диссертации опубликованы в работах [70-74].

Диссертация состоит из трех глав. Главы нумеруются арабскими цифрами, начиная с единицы. Параграфы имеют двойную нумерацию: первое число представляет собой номер главы, второе — номер параграфа внутри главы. Нумерация предложений, теорем — двойная: первое число представляет собой номер главы, второе — номер предложения, теоремы в данной главе. Нумерация формул — тройная: первое число есть номер главы, второе — номер параграфа, третье — номер формулы в параграфе.

Автор выражает искреннюю благодарность научному руководителю кандидату физико-математических наук доценту Маркову Виктору Тимофеевичу, доктору физико-математических наук профессору

Нечаеву Александру Александровичу , а также доктору физико-математи-

за постановку за-

ческих наук профессору Кузьмину Алексею Сергеевичу

дачи и поддержку в процессе написания диссертации.

Глава 1. Методы построения скрученных рекуррент максимального периода над кольцами Галуа

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

В §1.1 вводятся необходимые определения, формулируется задача и дается краткий обзор результатов исследований скрученных рекуррентных последовательностей, опубликованных отечественными и зарубежными авторами.

В §1.2 приводится характеристический критерий свойства «быть скрученной рекуррентой максимального периода», вводится класс линеаризуемых рекуррент максимального периода, а также приводится обоснования преимущества остальных рекуррент максимального периода (нелинеаризуемых) по ряду криптографических параметров. Приводится доказательство возможности сведения задачи построения класса всех рекуррент над кольцом Галуа к аналогичной задаче над его полем вычетов.

В §3.3 приводится класс нелинеаризуемых рекуррент максимального периода, построение которого основано на нахождении определяющих коэффициентов скрученной рекурренты максимального периода, а также оценивается его мощность.

Результаты §1.2 опубликованы в работе [70], §1.3 — в работе [74].

§ 1.1 Постановка задачи и обзор предшествующих

результатов

В данном параграфе будут даны необходимые определения и представлен основной объект исследования, а также будет приведен обзор предшествующих результатов, опубликованных отечественными и зарубежными ав-

торами.

Всюду далее Б — кольцо Галуа, Я — некоторое его подкольцо Галуа [7,11,14] и С = С(дБ) — кольцо линейных преобразований модуля дБ. На кольце Б задается структура левого С-модуля.

Множество Б^ всех последовательностей над Б есть левый модуль над кольцом многочленов С [ж], в котором умножение последовательности V £ Б ^ на многочлен Ф(ж) = ^ ¿> о ^жг £ С [ж] определяется равенством

Ф(ж)V = и £ Б^ : и(г) = ^^^(г + ^)), для г > 0.

¿>о

Последовательность V £ Б <!> назовем (Я-)скрученной линейной рекуррентной последовательностью (ЛРП) порядка т > 0 над кольцом Б, если она есть ЛРП порядка т над модулем СБ [11], т.е.

Ф(ж^ = 0 (1.1.1)

для некоторого унитарного многочлена

ф(ж) = жт - ^то_1жт-1 - ... - ^о £ С [ж] (1.1.2)

степени т, называемого характеристическим многочленом ЛРПV, иначе говоря, если последовательность V удовлетворяет некоторому закону рекурсии

Уг £ N0 : v(г + т) = ^т_1^(г + т _ 1)) + ... + ^оМг)). (1.1.3)

Характеристический многочлен последовательности V минимально возможной степени будем называть ее минимальным многочленом. В частности, если Ф(ж) £ Б [ж] то V называется классической ЛРП. (Здесь мы отождествляем Б и множество гомотетий Б порождаемых элементами из Б в кольце С.) Далее будем оговорок считать, что некоторый многочлен Ф(ж) £ С [ж] степени т обладает тем или иным свойством, если этим свойством обладает рекуррентная последовательность V с начальным заполнением равным v[0,m _ 1] = (0,0, ...,е) (импульсная последовательность) и многочленом Ф(ж) в качестве характеристического.

Кольцо Я будем называть также кольцом кручения. Исходя из определения, одна и та же последовательность элементов Б может быть рассмотрена как ЛРП над разными кольцами кручения, в частности, если V € Б^ есть Я-скрученная ЛРП порядка т, то она является также Я'-скрученной ЛРП порядка т для любого подкольца Я' кольца Я, так как в этом случае С (дБ) < С(дБ). Там, где конкретный вид кольца кручения ясен из контекста или не имеет значения, его упоминание будет опускаться.

Совокупность всех ЛРП V над кольцом Б с характеристическим многочленом Ф обозначим через Ьв(Ф). Также будем использовать обозначение Ьв(Ф)* = {V € Св(Ф) : Т(V) = Т(Ф)}.

Пусть далее р — простое число и Я = ОЯ(с^,р^) < Б = ОЯ(с"^,р^) — кольца Галуа характеристики рЛ состоящие из с^' и с" элементов соответственно, где с = рг .В частности, любая ЛРП и порядка т над Б, т.е. последовательность, аннулируемая некоторым унитарным многочленом О(х) € Б[х] степени т, является Я-скрученной ЛРП порядка т над Б для любого подкольца Я < Б, и известно [7, 10, 11], что ее период удовлетворяет условиям Т(и) < Т(О) < т = (с"т - 1)р^-1. Здесь Т(О)— период многочлена О(х) € Б[х]. В случае, когдаТ(О) = т = (|Б|т — 1)р^-1, многочлен О(х) называется многочленом максимального периода (МП многочленом) над кольцом Б. Указанная верхняя оценка дословно обобщается на периоды скрученных ЛРП (см. §1.2). В случае, когда Т(V) = т, будем называть последовательность V скрученной ЛРП максимального периода (МП ЛРП). Совокупность всех унитарных многочленов максимального периода над кольцом С степени т обозначим через 8МРв(т) (или 8МРд,в(т) если необходимо подчеркнуть кольцо кручения).

Для проведения некоторых доказательств и сравнения полученных результатов с результатами предшествующих авторов полезно сформулировать обсуждаемые понятия на матричном языке.

Имеет место изоморфизм

С = Я",", (1.1.4)

где Яп,п — кольцо всех п х п — матриц над Я. Зафиксируем базис а = (а0, а1,..., ап-1) свободного модуля дБ и обозначим через а^ = (а0,..., ап-1 )т £ столбец координат элемента а £ Б в базисе а:

П_1 П_1

а = ^^ а^а = ^^ а^ = аа^.

¿=о ¿=о

Тогда каждому линейному преобразованию ф £ С модуля дБ соответствует единственная матрица А(ф) = Аа(ф) £ Яп,п такая, что для любого а £ Б

ф(а)^ = А(ф )а^,

называемая матрицей линейного преобразования ф в базисе а. Очевидно, последовательность V £

Б Ш является скрученной ЛРП порядка т , т.е. удовлетворяет некоторому соотношению (1.1.3), тогда и только тогда, когда столбцы координат ^(г) членов этой последовательности в базисе а удовлетворяют соотношению

Уг £ N0 : ^(г + т) = А(фт-1)^(г + т _ 1) + ... + А(ф0)^(г). (1.1.5)

Соотношение (1.1.5) будем называть законом рекурсии скрученной ЛРП V в матричном виде, а последовательности v0, v1,..., vn_1 £ Я^ получаемые из разложения

V = о^о + +----+ ап_^п_1 (1.1.6)

будем называть координатными последовательностями рекурренты V.

Согласно (1.1.4) матрицы А5 = А(ф5) £ Япхп, й £ 0,т _ 1, в (1.1.5) могут быть произвольными и закон рекурсии (1.1.5) можно записать компактнее:

Уг £ N0 : ^(г + т) = Ат-1^(г + т _ 1) + ... + А0^(г),

Ао,..., А

т_1 £ Яи,щ. (1.1.7)

Началом систематического исследования скрученных (матричных) рекуррентных последовательностей зарубежными авторами можно считать

конференцию Fast Software Encryption в 1994 г., на которой затрагивались вопросы создания генераторов ПСП, которые бы оперировали векторами: «Как создать быстрые и защищенные регистры сдвига с обратной связью, основанные на операциях с векторами, использующие в полной мере современные процессоры и технологии параллелизма, B. Preneel» [30], [31, §2.2].

Стоит отметить, что некоторые поточные шифры, такие как SOBER [65,66], SNOW [67,68], и Turing [69], использовали именно такие векторные генераторы над конечным полем.

Одним из первых результатов в этой области является статья [32, 1995 г.] в которой рассматривается общий случай скрученных рекуррент над полем S = GF(pn). В ней ставится вопрос об общем количестве скрученных рекуррент максимального периода для фиксированных параметров (p,m,n), который эквивалентно сводится к подсчету для заданного примитивного а Е K = GF(pmn) = R(a) количества n-мерных подпространств RV < RK (ориг. a-splitting subspaces) таких, что

K = V 0 aV am-1V. (1.1.8)

Также автором той работы показано, что координатные последовательности скрученной рекурренты максимального периода являются классическими линейными рекуррентами максимального периода над полем R = GF(p). На основе этого был предложен критерий свойства «быть скрученной рекуррен-той максимального периода» заключающийся в проверке того, что некоторая система вида {ДО |в Е K,i Е 0,n — 1,j Е 0,m — 1} (определяемая кандидатом) является базисом пространства rK. Аналогичный критерий принадлежности к классу классических линейных рекуррент максимального периода доказан А.С. Кузьминым в 1995 г., но с более сильным эквивалентным условием.

В работе [33, 2000 г.] исследуется задача поиска скрученных рекуррент максимального периода с трехчленными законами рекурсии над полями. Построен трехчлен максимального периода над S = GF(216).

В работе [34, 2002 г.] рассматривается частный случай матричного генератора (ориг. linear TSR) со следующим законом рекурсии:

+ m) = T(a0v;(i) +-----Ь am-1v;(i + m - 1)), (1.1.9)

где Т £ Яп,п и а0,... ,ат-1 £ Я, Я = (д). Отмечалась высокая эффективность при реализации таких законов рекурсии на современных процессорах и более сложное аналитическое строение (линейная сложность), чем у классических рекуррент максимального периода. Поиск таких генераторов, имеющих максимальный период, производился перебором.

В работе [36, 2007 г.] рассматривается общий вид скрученных рекуррент максимального периода над полем Б = (2П) (ориг. а-ЬРБК). Предложен переборный алгоритм для поиска таких рекуррент. Также авторами выдвинуто в качестве гипотезы утверждение об общем числе скрученных многочленов максимального периода, которое было проверено авторами для большого числа пар (т,п), но не было доказано ими в общем случае.

Теорема 1.1.

Для сравнения заметим, что мощность множества MPs(m) С SMPs(m) классических линейных рекуррент максимального периода над полем S = GF(qn) порядка m равна:

В статье [38, 2007 г.] изучаются признаки, при которых скрученная ре-куррента над Б = (2П) не имеет максимального периода. С использованием этих признаков строится алгоритм отбраковки для построения трехчленных скрученных законов рекурсии. Также в работе приводятся найденные таким образом трехчлены максимального периода для тп < 100.

В статьях [39-42, 2009 г.] проводится анализ координатных последовательностей скрученных рекуррент максимального периода над полем Б =

(1.1.10)

(1.1.11)

О^(2"). В работе [39] предлагается критерий свойства «быть рекуррентой максимального периода порядка т» на основе функции след, применяемой к вектору из п элементов над полем О^(2т"), и проверки соответствующего равенства. На основе этого критерия в статье [40] предложен алгоритм поиска рекуррент максимального периода. Приведены экспериментальные результаты для случая т = 2,п = 3. Далее с помощью координатного представления в работе [41] доказывается сформулированная несколько выше теорема 1.1 для случая п = 2, а в работе [42] представлен практический способ нахождения линейной сложности скрученной рекурренты максимального периода и показано, что ее величина всегда равна кт, для некоторого 1 < к < п,

причем в [70] показано, что число к может принимать все значения из 1,п.

В работах [43,44, 2011 г.] изучается общий вид Я-скрученных рекуррент над полем Б = О^(с") (Я = О^(с)). В работе [43] предложено обобщение теоремы 1.1.

Теорема 1.2.

|SMPs(m)| = ^(qmn 1) • • q(m—1)(n—1)n. (1.1.12)

mn qn — 1

В этой же работе теорема 1.2 доказана для случая m = 1,n > 1. В работе [44] теорема 1.2 доказана для случая m > 1,n = 2. (При n = 1, т.е. для S = R, формула (1.1.12) с очевидностью вытекает из (1.1.11))

В работе [45, 2012 г.] авторы представляют класс рекуррент максимального периода над полем S = GF(2n) порядка m > 3, построенный методом сдвигов координатных последовательностей (ориг. Z-primitive a-LFSRs), мощность которого равна

y(2mn — 1) R, , 2„—1 y(2""' — 1) |r;„i ,...3)

mn •|R-1.-11^2 = mn • 2П-—Г■ (1ЛЛ3)

Указанный класс в точности совпадает с классом линеаризуемых рекуррент, представленным в работе [70, 2011г.], что будет показано далее.

В работе [47, 2013 г.] доказана гипотеза о числе подпространств вида (1.1.8), сформулированная в [46], которая очевидным образом влечет спра-

ведливость теоремы 1.2. Стоит заметить, что доказательство указанной теоремы не является конструктивным, т.е. не позволяет строить скрученные МП ЛРП непереборным способом. В [49] на основе этой статьи получено точное количество законов рекурсии вида (1.1.9).

В работе [48, 2013 г.] сформулирован метод построения многочленов максимального периода, на основе блочных матриц Вандермонда, но для его применения необходимо осуществлять проверку обратимости таких матриц.

В данной главе будет исследоваться возможность построения скрученных рекуррент максимального периода над кольцами Галуа без использования методов перебора и проверки каких-либо отбраковывающих условий.

Список литературы диссертационного исследования кандидат наук Зайцев, Сергей Николаевич, 2018 год

Список литературы

[1] Словарь криптографических терминов, под ред. Погорелова Б.А. и Сач-кова В.Н, МЦНМО, М., 2006, 94 с.

[2] М.М. Глухов, В.П. Елизаров, А.А. Нечаев, Алгебра, в 2-х т, М.: Гелиос, 2003, 336 + 416 с.

[3] А. П. Алфёров, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин, Основы криптографии, Гелиос АРВ, М., 2005, 480 с.

[4] К. Шеннон, Работы по теории информации и кибернетике: Теория связи в секретных системах., ИЛ, М., 1963.

[5] Р. Лидл, Г. Нидеррайтер., Конечные поля, 1,2, Мир, М., 822 с.

[6] A.A. Nechaev, "Handbook of Algebra", Finite ring with applications, 5, 213320

[7] А. С. Кузьмин, А. А. Нечаев, "Линейные рекуррентные последовательности над кольцами Галуа", Алгебра и логика, 3:2 (1995), 169-189

[8] В. Л. Куракин, "Алгоритм Берлекэмпа-Месси над конечными кольцами, модулями и бимодулями", Дискрет. матем., 10:4 (1998), 3-34.

[9] А. А. Нечаев, "Код Кердока в циклической форме", Discrete Math. Appl., 1:4 (1989), 123-139.

[10] А.А. Нечаев, "Цикловые типы линейных подстановок над конечными коммутативными кольцами", Матем. сб., 184:3 (1994), 21-56.

[11] V.L. Kurakin, A.S. Kuzmin, A.V. Mikhalev, A.A. Nechaev, "Linear recurring sequences over rings and modules.", J. Math. Sci., 76:6 (1995), 2793-2915.

[12] В.Л. Куракин, "Функция переноса в первый разряд в кольце Галуа.", Дикрет. матем., 24:2 (2012), 21-36.

[13] T. Nakayama, "On Frobeniuscan Algebras", I. Ann. of Math., 40 (1939), 611-633..

[14] А. С. Кузьмин, А. А. Нечаев, "Построение помехоустойчивых кодов с использованием линейных рекуррент над кольцами Галуа", Успехи математических наук, 47:5 (1992), 183-184..

[15] А. С. Кузьмин, В. Л. Куракин, А. А. Нечаев, "Псевдослучайные и полилинейные последовательности", В сб.:Труды по дискретной математике, 1, 139-202.

[16] А. С. Кузьмин, В. Л. Куракин, А. А. Нечаев, "Свойства линейных и полилинейных рекуррент над кольцами Галуа", В сб.:Труды по дискретной математике, 2, 191-222.

[17] А. С. Кузьмин, В. Л. Куракин, А. А. Нечаев, "Свойства линейных и полилинейных рекуррент над кольцами Галуа (II)", Обозрение прикл. и про-мышл. матем. Сер. дискрет. матем., 7:1, 5-59.

[18] А. С. Кузьмин, В. Л. Куракин, А. А. Нечаев, "Структурные, аналитические и статистические свойства линейных и полилинейных рекуррент", В сб.:Труды по дискретной математике, 3, 155-194.

[19] А. С. Кузьмин, В. Л. Куракин, А. А. Нечаев, "Вполне равномерные линейные рекурренты", В сб.:Труды по дискретной математике, 5, 103-158.

[20] А. А. Нечаев, "Линейные рекуррентные последовательности над коммутативными кольцами", Дискрет. матем., 3:4, 107-121.

[21] А. С. Кузьмин, "Нижние оценки рангов координатных последовательностей над кольцами Галуа", УМН, 48:3, 193-194.

[22] О. В. Камловский, "Частотные характеристики разрядных последовательностей линейных рекуррент над кольцами Галуа", Известия Российской академии наук. Серия математическая, 77:6, 71-96.

[23] О. В. Камловский, "Уточнение оценок для числа появлений элементов в линейных рекуррентных последовательностях над кольцами Галуа", Фундамент. и прикл. матем., 17:7, 97-115.

[24] О. В. Камловский, "Метод тригонометрических сумм для исследования

частот r-грамм в старших координатных последовательностях линейных рекуррент над кольцом Z2«", Матем. вопр. криптогр., 1:4 (2010), 33-62.

[25] О. В. Камловский, "Количество появлений элементов в выходных последовательностях фильтрующих генераторов", ПДМ, 2013, №3, 11-25.

[26] О. В. Камловский, "Метод В.М. Сидельникова для оценки числа знаков на отрезках линейных рекуррентных последовательностей над кольцами Галуа", Матем. заметки, 91:3 (2012), 371-382.

[27] О. В. Камловский, "Спектральный метод для оценки числа решений систем нелинейных уравнений с линейными рекуррентными аргументами", в печати.

[28] M.A. Goltvanitsa, "Digit sequences of skew linear recurrences of maximal period over Galois rings", Matem. vopr. kriptogr., 6:2, 19-27.

[29] M. A. Goltvanitsa, "Об одном классе скрученных рекуррент максимального периода над кольцом Галуа", Системы высокой доступности, №3, 28-49.

[30] H. Krawczyk, "The Shrinking Generator: Some Practical Considerations", Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, 45-46..

[31] B. Preneel, "Introduction to the Proceedings of the Fast Software Encryption 1994 Workshop (Ed. Bart Preneel)", LNCS, 1995, №1008, 1-5..

[32] Harald Niederreiter, "The Multiple-Recursive Matrix Method for Pseudorandom Number Generation", Finite Field and their Applications, 1 (1995), 3-30.

[33] Kurakin V. L., Mikhalev A. V., Nechaev A. A., Tsypyschev V. N., "Linear and polylinear recurring sequences over Abelian groups and modules", J. Math. Sci., 102:6 (2000), 4598-4626.

[34] B. Tsaban and U. Vishne, "Efficient Linear Shift Registers with Maximal Period", Finite Fields and Their Applications, 2:8 (2002), 256-267..

[35] S.W. Golomb, "Sequences with randomness properties", Final Report, Baltimore, Md., 1955.

[36] G. Zeng, W. Han, K. He, "High Efficiency Feedback Shift Registers: a-LFSR", Cryptology ePrint Archive: Report 2007/114 http://eprint.iacr.org/2007/114, 2007.

[37] Wenbao Han, Xianghui Liu, Guang Zeng and Gangmin Tan, "Word-oriented Linear Feedback Shift Registers: a-LFSRs", Higher Education Press and International Press Beijing-Boston, 2011.

[38] Guang Zeng, Kaicheng He, Wenbao Han, "A Trinomial Type of a-LFSR Oriented Toward Software Implementation.", Science In China Series F: Information Science, 50:3 (2007).

[39] Zhang M, Zeng G, Han WB, He KC, "Trace Representation of Primitive a-LFSR Sequence and Its Application", Journal of Electronics & Information Technology, 31:4 (2009), 942-945.

[40] Liu XH, Han WB, Zeng G, "Construction of Primitive a-LFSR Sequences from m-sequences.", Journal of Sichuan University (Natural Science Edition), 46(6) (2009), 1645-1649..

[41] Xianghui Liu, Meng Zhang, Wenbao Han, Guang Zeng, "Research on Counting of Primitive a-LFSR", Computer Engineering, 35:18 (2009), 154155.

[42] Liu Xianghui, Zeng Guang, Han Wenbao, "Research on Linear Complexity of Primitive a-LFSR Sequences", Journal of Electronics & Information Technology, 31:12 (2009), 2897-2900.

[43] Shudhir R. Ghorpade, Sartaj UL Hasan and Meena Kumari, "Primitive polynomials, singer cycles, and word-oriented linear feedback shift registers", Designs, Codes and Cryptography, 58:2 (2011), 123-134.

[44] Sudhir R. Ghorpade, Samrith Ram, "Block companion singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields", Finite Fields and Their Applications, 2011.

[45] Tan Gangmin, Zeng Guang, Han Wenbao, Liu Xianghui, "Construction and Enumeration of a Class of Primitive a-LFSR Sequences", Journal of Software, 23:4 (2012), 952-961.

[46] Sudhir R. Ghorpade and Samrith Ram, "Enumeration of Splitting Subspaces over Finite Fields", Contemporary Mathematics, 574 (2012).

[47] Eric Chen and Dennis Tseng, "The splitting subspace conjecture", Finite Fields and their Applications, 24:0 (2013), 15-28.

[48] Lachaud G., "Word oriented LFSR and construction of block companion matrices in a given conjugacy class", Crypto'Puces 2013 May 27-31, Porquerolles. Institut de Mathematiques de Luminy CNRS/AMU, Marseille., 2013.

[49] Daniel Panario, "The number of irreducible transformation shift registers", Conference: «Mathematics of Communications: Sequences, Codes and Designs», 2015.

[50] Кузьмин А.С., Нечаев А.А., "Восстановление линейной рекурренты максимального периода над кольцом Галуа по ее старшей координатной последовательности", Дискр. мат., 23:3-31 (2011).

[51] Кузьмин А.С., Маршалко Г.Б., Нечаев А.А., "Восстановление линейной рекурренты над примарным кольцом вычетов по ее усложнению", Математические вопросы криптографии, 1:2 (2010), 31-56.

[52] Былков Д.Н., Нечаев А.А., "Алгоритм восстановления ЛРП над кольцом R = Zpn по линейному усложнению ее старшей координатной последовательности", Дискр. мат, 22:4 (2010), 104-120.

[53] Былков Д.Н., "Восстановление линейной рекурренты максимального периода над кольцом Галуа характеристики p3 по ее старшей разрядной последовательности", Дискр. мат., 22:4 (2010), 104-120.

[54] Min-Qiang Huang, Zong-Duo Dai, "Projective maps of linear recurring sequences with maximal p-adic periods", Fibonacci Quart., 30:2 (1992), 139143.

[55] Xuan-Yong Zhu, Wen-Feng Qi, "Compression mappings on primitive sequences over Zpn", IEEE Trans. Inform. Theory, 50:10 (2004), 2442-2448.

[56] Xuan-Yong Zhu, Wen-Feng Qi, "Further result of compressing maps on primitive sequences modulo odd prime powers", IEEE Trans. Inform. Theory, 53:8 (2007), 2985-2990.

[57] Xuan-Yong Zhu, Wen-Feng Qi, "Further result of compressing maps on primitive sequences over Z,", Math. Comp, 77 (2008), 1623-1637.

[58] Xuan-Yong Zhu, Wen-Feng Qi, "Further results on the distinctness of binary sequences derived from primitive sequences modulo square-free odd integers", IEEE Trans. Inform. Theory, 59:6 (2013), 4013-4019.

[59] Tian Tian, Wen-Feng Qi, "Injectivity of compressing map on primitive sequences over Zp", IEEE Trans. Inform. Theory, 53:8 (2007), 2960-2966.

[60] Xuan-Yong Zhu and Wen-Feng Qi, "Uniqueness of the distribution of zeroes of primitive level sequences over Zpe ", Finite Fields and Their Applications, 11:1, 30-44.

[61] Zong-Duo Dai, "Binary sequences derived from ML-sequences over rings I: periods and minimal polynomials", J. Cryptology, 5:4 (1992), 193-207.

[62] Weng-Feng Qi, Xuan-Yong Zhu, "Compressing maps on primitive sequences over Z2n and its Galois extension", Finite Fields Appl., 8:4 (2002), 570-588.

[63] Weng-Feng Qi, "Compressing maps on primitive sequences over Z2n and analysis of their derivative sequences", PhD Thesis. Zhengzhou Inform. Eng. Univ., Zhengzhou, China, 1997.

[64] Weng-Feng Qi, Jun-Hui Yang, Jin-Jun Zhou, "ML-sequences over rings Z2n", Lecture Notes Computer Sci., 1514 (1998), 315-325.

[65] P. Hawkes and G.G. Rose, Primitive Specification and Supporting Documentation for SOBER-t16 Submission to NESSIE, Proceedings of the first NESSIE Workshop (2000)

[66] P. Hawkes and G.G. Rose, Primitive Specification and Supporting

Documentation for SOBER-t32 Submission to NESSIE, Proceedings of the first NESSIE Workshop, (2000)

[67] P. Ekdahl and T. Johansson, SNOW - a new stream cipher, Proceedings of the first NESSIE Workshop, (2000)

[68] P. Ekdahl and T. Johansson, A New Version of the Stream Cipher SNOW, Selected Areas in Cryptography, LNCS 2595 (2002) 47-61

[69] P. Hawkes and G.G. Rose. Turing: A Fast Stream Cipher, Fast Software Encryption, LNCS 2887 (2003) 24-26

Публикации автора по теме диссертации

[70] М. А. Гольтваница, С. Н. Зайцев, А. А. Нечаев, "Скрученные линейные рекурренты максимального периода над кольцами Галуа", Фундаментальная и прикладная математика, 17:3 (2011/2012), 5-23.

[71] M.A. Goltvanitsa, A. A. Nechaev, S.N. Zaitsev, "Skew LRS of Maximal Period over Galois Rings", Matem. Vopr. Kriptorg, 4:2 (2013), 59-72.

[72] S.N. Zaitsev, "Description of Maximal Skew Linear Recurrences in Terms of Multipliers", Matem. Vopr. Kriptogr, 5:2 (2014), 57-70.

[73] С. Н. Зайцев, "Восстановление скрученной рекурренты над кольцом Галуа нечетной характеристики по полиномиальному усложнению ее разрядов", Системы высокой доступности, 2015, №3, 13-27.

[74] С. Н. Зайцев, "Треугольный класс скрученных МП-многочленов максимального периода", Проблемы передачи информации, 52:4 (2016), 65-75.