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

• Аборнев Александр Викторович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Аборнев Александр Викторович

Введение

Глава 1. Построение нелинейных подстановок,

индуцированных линейными преобразованиями модуля над кольцом Галуа

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

§ 1.2 Классы подстановок, порождённых разрядно-

подстановочными матрицами над кольцом Галуа

характеристики

§ 1.3 Классы подстановок, рекурсивно порожденных над кольцом Ъ4 51 § 1.4 Классы подстановок, порождённые разрядно-инъективными

матрицами

§ 1.5 Выводы

Глава 2. Итеративные преобразования, порождённые

линейно представимыми подстановками

§2.1 Исследуемые свойства итеративных преобразований

§ 2.2 Итеративные преобразования, порождённые

разрядно-подстановочными матрицами

§ 2.3 Преобразования, линейно представимые разрядно-инъективными

матрицами

§2.4 Выводы

Заключение

Список условных обозначений

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

Введение

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

Актуальность темы исследования.

Подстановки (биективные преобразования) на векторном пространстве Рт над полем Галуа Р = GF(q) активно изучаются в связи с различными приложениями, и в том числе в теории защиты информации. Чаще всего подстановки используются как элементы при построении узлов переработки информации. В середине XX века К. Шенноном были теоретически обоснованы основные требования к отображениям, реализуемым в таких узлах. Они получили широкое практическое воплощение и известны как принципы перемешивания, рассеивания и усложнения. В настоящее время при построении биективных преобразований данные требования обеспечиваются композицией нелинейных отображений, заданных таблично над полем СР(2), и линейных рассеивающих преобразований.

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

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

Степень разработанности темы исследования. В современных узлах переработки информации, построенных по итерационному принципу, на каждой итерации реализуется биективное преобразование элементов множества СР(2)т.

Для построения таких преобразований используется специально выбранное нелинейное преобразование пространства малой размерности (например 4 или 8) и линейное преобразование пространства. Выбор таких пре-

образований для итеративных преобразований, используемых в системах защиты информации, имеющих требуемые комбинаторно-алгебраические свойства, в общем случае является трудной задачей. В настоящее время многие отечественные и зарубежные специалисты изучают возможность построения новых классов биективных преобразований с помощью подстановочных многочленов над большим полем GF(2m) (например, GF(2128)). Известны следующие базовые классы подстановчных многочленов: Голд-функции (Gold), функции Касами (Kasami), функция обращения в поле и функции Брекен-Лендер (Bracken-Leander).

Однако использование таких подстановок при больших значениях m проблематично в связи с тем, что не известны эффективные способы их реализации, зачастую отсутствует алгоритм вычисления обратного преобразования, нет возможности перечислять подстановки из данного класса.

Сложность построения подстановок на пространстве обусловлена тем, что в общем виде эта задача эквивалентна задаче построения ортогональных систем многочленов. В теории известны единичные примеры таких классов ортогональных систем (многочлены Диксона).

При построении узлов переработки информации свою эффективность показала теория линейно представимых отображений над кольцами, которая активно развивается отечественными специалистами. В работах Нечаева A.A.1 , Кузьмина A.C. 2, Куракина В.Л., Хонольда Т., эта теория применяется для построения кодов, рекуррентных последовательностей и их усложнений. При таком способе построения отображений высокая алгебраические степень преобразования и большая линейная сложность получаемых последовательностей обеспечиваются открытым Нечаевым A.A. "эффектом самоусложнения", который состоит в том, что усложнение обеспечивается нелинейностью функции переноса в старший разряд. Ещё одним достоин-

1Нечаев, А. А., Хонольд, Т. Полновесные модули и представления кодов // Пробл. передачи информ.

- Новосибирск. - 1999. - Т.35. - Ш. - С.18^39.

2Кузьмип, А. С., Нечаев A.A. Линейно представпмые коды и код Кердока над произвольным полем Галуа характеристики 2 // Успехи математических наук. — 1994. — Т. 49. — JYS5 (299). — С. 165—166.

ством таких отображений является простота их реализации на современных процессорах.

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

Рт

Р = СЕ^) имеет координатное предетавление п = (фх,... , фт), где ф^ — координатные функции, ] Е 1,ш. Далее будем говорить, что подстановка п

линейной функцией. Для случая Р = СЕ(2) это означает, что степень многочлена Жегалкина одной из координатных функций больше 1.

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

Обозначим через 2 регулярную подгруппу симметрической группы например, регулярное представление группы (П, +) или циклической группы. Применение одной подстановки из смежного класса может быть рассмотрено как один раунд итеративного преобразования (п2)к С б(П).

Проблема построения и реализации преобразований итеративного ти-

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

- достаточно большая размерность ш пространства (модуля) (ш > 64);

- нелинейность подстановки п;

- порождение смежным классом пЕ знакопеременной группы;

- 2-транзитивность смежного класса (пЕ)^ при небольших к;

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

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

ш

Приведём необходимые определения и обозначения из [40]. Пусть Я = СЯ(д2,р2) — кольцо Галуа с полем вычетов Я = Я/рЯ = СЕ(д), д = рТ. Подмножество Г(Я) = {а £ Я : ая = а} называют р-адическим разрядным

Я

писать Р = Г(Я).

Каждый элемент а £ Я однозначно представляется в виде

а = ао + ра1, аа £ Р, в £ 0,1, (0.0.1)

ра отображения

: Я ^ Р, 7Да) = ав, в £ 0Д, (0.0.2)

3Глухов, М. М. О числовых параметрах, связанных с заданием конечных групп системами образующих элементов/ М. М. Глухов // Тр. по дискр. матем: Т.1. — М.: ТВП, 1997. — ('.!•''> ()(>.

Р

ав = 7в(а) _ р-адическими разрядами элемента а.

Алгебра (Р, ©, •) с естественным умножением и операцией сложения

есть поле, изоморфное Я.

Пусть Ят,п — множество (т х п)-матриц над Я. Понятия р-адического разложения и значения функции естественным образом (поэлементно) распространяются на матрицы А = (а(щ)) Е Ят,п, при этом будем писать А5 = 78(А) = (7з(а(щ))) Е Рт,т-

В работе предлагаются следующие способы построения подстановок, каждая из которых реализуется одним линейным преобразованием модуля Я(т) над кольцом Галуа Я = СИ^2,р2) и операцией выделения разрядов

Я

1. Подстановки на пространстве столбцов Р(т) длины т.

Каждой матрице А Е Ятхт поставим в соответствие отображение па : Р(т) ^ Р(т) действующее по правилу:

В случае, когда преобразование па является подстановкой, матрица A называется разрядно-подстановочной или (РП-матрицей). Если при этом подстановка па нелинейна, то будем говорить, что РП-матрица A нетривиальна.

Наибольший интерес для приложений представляют РП-матрицы вида A = S(F)m, гДе S(F) — сопровождающая матрица многочлена F(x) = xm m- fX Е R[x\. В данном случае подстановка пА имеет эффективную реализацию с применением линейных рекуррентных последовательностей. Многочлен F степени m называется разрядно-подстановочным (РП-многочленом), если матрица Sm разрядно-подстановочна. РП-многочлен F называется нетривиальным, если нетривиальна РП-матрица S_m-

У а, b Е P : а 0 b = 70(а + b),

(0.0.3)

У и1 Е P(m) : па(П1) = Y1 (Au1).

(0.0.4)

Подстановки п\, к = 2,3,... также являются линейно-представимыми и значительно расширяют построенные классы.

Существование РП-матриц для ш < 14 впервые было установлено автором экспериментально при исследовании свойств линейных рекуррентных последовательностей.

Ят ш

Матрица Ж размера ш х п над кольцом Галуа Я называется разрядно-ишективной (Р И-матрицей) ^ если любая ненулевая строка и £ Ят однозначно восстанавливается по строке 71(ЦЖ) £ Рп.

Пусть п = 2ш и Ж £ Ят,2т — разрядно-пнъектпвная матрица. Заметим, что умножение вектора 71(хЖ) = (у/ | у/') £ Р2т на матрицу (Д;) даёт вектор у/ + руТ" £ Ят. Поэтому отображение пш : Ят ^ Ят вида

Пш (Х) = 71 (ХЖ )(рЕ), (°-0-5)

где Е £ Ят,т — единичная матрица, является подстановкой на модуле Ят.

Подстановки вида (0.0.4) и (0.0.5) будем называть далее линейно пред-ставимыми над кольцом Галуа. Заметим, что каждая подстановка задается ортогональной системой многочленов.

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

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

Целью диссертации является построение новых нетривиальных классов нелинейных подстановок на пространстве (свободном модуле) большой размерности, для которых смежные классы по регулярной подгруппе симметрической группы имеют требуемые комбинаторно-алгебраические свойства.

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

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

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

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

- на векторном пространстве над полем Галуа;

- на модуле над кольцом Галуа, не являющимся полем.

Научная новизна полученных результатов определяется следующими положениями:

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

2. Описаны новые классы ортогональных систем квадратичных форм от большого числа переменных над полем Галуа характеристики 2, а также эффективные способы их перечисления.

3. Предложен оригинальный способ построения множества итеративных преобразований с использованием только просто реализуемых линейно представимых подстановок на пространстве большой размерности.

Методология и методы исследования. При решении задачи построения подстановок применяется и развивается теория многочленов над конечны-

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

Для описания свойств смежных классов по регулярным подгруппам симметрической группы применяются комбинаторные методы и методы теории конечных групп подстановок.

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

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

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

3. Разработкой нового критерия ортогональности для широкого класса систем квадратичных форм над полем Галуа характеристики 2.

4. Описанием семейств ЛРП падЖ4, с помощью которых реализуются нелинейные подстановки на двоичном векторном пространстве.

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

Положения, выносимые на защиту.

1. На множестве векторов произвольной фиксированной длины над полем Галуа характеристики 2 построены классы линейно представимых над кольцом Галуа характеристики 4 подстановок, имеющие две нелинейные координатные функции, и эффективно реализуемые классы нелинейных рекурсивно порождённых подстановок.

2. На множестве векторов произвольной длины над произвольным кольцом Галуа, не являющемся полем, построен класс линейно представимых над

и

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

3. Построены классы эффективно реализуемых множеств итеративных преобразований, порождённых линейно представимой подстановкой и регулярной группой, имеющих гарантированные комбинаторно-алгебраические свойства.

Степень достоверности и апробация результатов. Достоверность полученных результатов определяется наличием строгих математических доказательств. Основные результаты исследования опубликованы в 4 печатных работах, докладывались на конференциях CTCrypt2012,2013, 81ВЕСКУРТ'13,14, конференции "Ломоносовские чтения 2013" в МГУ, а также на научном семинаре МГУ им. Ломоносова.

Благодарности

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

Глава 1. Построение нелинейных подстановок, индуцированных линейными преобразованиями модуля над кольцом Галуа

В данной главе предлагается новый способ построения нелинейных подстановок большой степени, использующий теорию линейно представимых отображений. Данная теория развивается отечественными исследователями в работах [16-18,22] и успешно применялась для построения линейных представлений некоторых кодов (в том числе кода Кердока), и больших классов генераторов псевдослучайных последовательностей. В этих случаях исследовалось представление нелинейных двоичных кодов с помощью отображения Грея. Подстановки, изучаемые в данной работе, задаются одним линейным преобразованием и операцией выделения разрядов элементов кольца Галуа относительно разрядного множества Тейхмюллера. Такие подстановки будем называть линейно представимыми.

Настоящая глава имеет следующую структуру. В параграфе 1.1 даны основные определения и обозначения, приведён краткий обзор известных общих методов построения подстановок большой степени, а также общих свойств подстановок на пространстве, линейно представимых над кольцом. В параграфе 1.2 подробно изучается случай кольца Галуа характеристики 4. Задача построения линейно представимых подстановок сведена к задаче построения ортогональных систем квадратичных функций. Описаны условия, при которых система квадратичных функций может быть дополнена до подстановки диагональными квадратичными функциями. В параграфе 1.3 построены два нетривиальных класса подстановок на пространстве, просто реализуемых с использованием линейных рекуррентных последовательностей (ЛРП). В параграфе 1.4 описан большой и эффективно реализуемый класс линейно представимых подстановок на модуле над кольцом Галуа.

Результаты главы опубликованы в работах [3,5,6].

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

Ят = Я х . . . х Я Я Ят Я

Если Я = Р — поле Галуа, то Рт — пространство размерности ш над Р

Основная задача данной главы — построение нелинейных подстановок п па пространстве Рт и свободном модуле Ят, представимых линейным преобразованием А £ Ят,т над Я и выделением старшего разряда элемента из Я

Задача построения подстановок исторически произошла из криптографии.

В теории известны два принципиальных подхода к построению подстановок па декартовом произведении СР(д)т, д = рг.

1) Тривиальный:

- табличное задание подстановки;

- элементарные преобразования матриц и порождённые ими линейные преобразования;

- линейные многочлены и классы рмногочленов агжрг) над полем СР(д);

г

- степенные многочлены хп, (п, д — 1) = 1;

- треугольные системы многочленов над полем;

- композиция подстановок.

2) Теоретический подход, который даёт уникальные подстановки или классы подстановок.

- подстановочные многочлены Диксона

я*(*,«) = Е А Г — ' ^;

1=0 ^ \ J /

- список нормализованных многочленов (на основе критерия Эрмита).

Подстановочные многочлены над конечным полем и ортогональные системы многочленов.

Пусть Р = СЕ(д) — конечное поле. Всякое отображение И : Рт ^ Рт представляется в векторной форме И = ..., ^т), где функции

^ : Рт ^ Р, г Е 1,т, являются полиномиальными и называются коорди-

ИИ система многочленов ..., называется ортогональной [19] (или регулярной [23]).

Многочлен ^(ж) Е СЕ(дт)[ж] называется подстановочным, если он задаёт биекцию ^ : СЕ(дт) ^ СЕ(дт).

т

членов от т переменных над полем СЕ(д) эквивалентна задаче построения подстановочных многочленов над полем СЕ(дт), т Е N. Построению подстановочных многочленов над полем посвящено много работ зарубежных и отечественных авторов. Хороший обзор приведён в монографии [19], где подробно описан класс степенных многочленов.

Задача описания ортогональных систем многочленов включает в себя задачу описания сбалансированных многочленов.

Многочлен д(ж1,..., жт) Е Р[ж1,..., жт] от т переменных называется сбалансированным (перестановочным) над полем Р, если для любого с Е Р уравнение д(ж1,..., жт) = с имеет ровно дт-1 решений в Рт.

Предложение 1.1. [19] Система многочленов

д1,... ,д8 Е СР (д)[жь.. .,жт], 1 < 5 < т,

является ортогональной тогда и только тогда, когда для любого ненулевого набора (Ь1,..., Е СР(д)в многочлен д = Ь1д1 © ... © является сбалансированным над СР(д).

Следствие 1.1.1. Каждый многочлен, входящий в ортогональную систему, является сбалансированным, многочленом.

Подстановки на основе систем многочленов треугольного ви-

да. Будем называть треугольной систему многочленов вида

= , . . . , Хт—1) + ^1(Хт)

^2 = ^2(Ж1, . . . , Хт—2) + ^2(Хт—1)

; (1.1.1)

^т-1 = ^т—ДжО + ^т—1(^2)

^т ^т(ж1)

где ^ — подстановочные многочлены на Р. Очевидно, она является ортогональной, и отображение Н = (^1,..., ^т) является подстановкой.

Преобразования, используемые в системах защиты информации. Практически важными представителями биективных преобразований являются раундовые преобразования итеративных преобразований. Основными конструкциями для построения таких преобразований являются ХБЬ-семейства, БР-сети, АИХ-схемы, сети Фейстеля и их обобщения, нелинейные регистры с несколькими обратными связями и др.

1.1.1 Построение нелинейных подстановок с помощью линейных преобразований модуля над кольцом Галуа

В данной работе исследуются два новых способа построения нелинейных подстановок на алфавите большой мощности с использованием матриц над кольцом Галуа Я = СЯ(д2,р2).

Пусть Ят,п — множество ш х п-матриц над Я. Понятия р-адического разложения и значения функции 7,5 естественным образом (поэлементно) распространяются на матрицы А = )) £ Ят,п, при этом будем писать Ав = Те (А)- Умножение матриц над полем будем обозначать символом

Нечаевым А.А. предложены следующие два способа построения подстановок.

1. Подстановки на пространстве Р (т)_

Каждой матрице А £ Ятхт можно поставить в соответствие отображение па : Р(т) ^ Р(т), действующее по правилу:

Ум1 £ Р(т) : па(м) = 71 (Ам1) = ^(Аом1) 0 (А^м1). (1.1.2)

В случае, когда преобразование па является подстановкой, матрица А называется разрядно-подстановочной или (РП-матрицей). Если при этом па нелинейна, то будем говорить, что РП-матрица А нетривиальна.

Наибольший интерес для приложений представляют РП-матрицы вида

А = 5 (Р )т, где 5 (Р) =

(

0 10 ... 0 0 0 1 ... 0

0 0 0 ... 1

у 0 /1 /2 ... /т-1

(1.1.3)

— сопровождающая матрица многочлена Р(ж) = жт — ^т-1 /«жг Е Я [ж]. В данном случае подстановка па имеет эффективную реализацию с применением линейных рекуррентных последовательностей.

Подстановки пА, к = 2,3,... также являются линейно-представимыми и расширяют построенные классы.

Существование РП-матриц для т < 14 впервые было установлено автором экспериментально при исследовании свойств линейных рекуррентных последовательностей.

2. Подстановки на модуле Ят.

Матрица Ж размеров т х п над кольцом Галуа Я называется разрядно-ишективной (РИ-матрицей), если любая ненулевая строка и Е Ят однозначно восстанавливается по строке 71(мЖ) Е Рп.

В случе п = 2т каждая РИ-матрица Ж Е Ят,2т задаёт биекцию П : Ят ^ Р2т то правилу п'(ж) = 71(жЖ), ж Е Ят. Тогда отображение : Ят ^ Ят вида

(ж) = 71 (жЖ)

(1.1.4)

где Е Е Ят,т — единичная матрица, является подстановкой па модуле Ят, поскольку умножение вектора 71 (жЖ) = (у/ | У) Е Р2т на матрицу (Д;) дает вектор у/ + руТ" Е Ят.

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

1.1.2 Общие свойства линейно представимых подстановок на

пространстве

Преобразование па для А = )) £ Ят,т является вектор-функцией

вида

( фЛ

па =

, фг: Рт ^ Р, г = 1, ш. (1.1.5)

\ фт /

Функции ф1,..., фт будем называть координатными функциями преобразования па Напомним, что при условии |Р| = д каждая из этих функций

Р

выше д — 1 по каждой переменной. Такие многочлены называются приведён-

ф1 , . . . , фт

->

Пусть А — РП-матрнца и АДг) = (а(г1),..., а^(гш)) — г-я строка матрицы А^, £ = 0,1. Тогда из (1.1.2) следует, чт0 вектор X = (ж1,...,жт)т Р

фг(X) = 71(А(г)ж|) = 71(А0(г)ж|) 0 А1(г)®ж| =

= 71 (ао(г1)ж1 + ... + ао(гш)жт) 0 а1(г1)ж 0 ... 0 а1(гш)жт. (1.1.6)

Теперь для получения окончательного аналитического представления

фг

гцпй полученную функцию (1.1.6).

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

1 (ш,р) = Шъ...,.?т) : ;'1,...,^т £ 0,р — 1 Л + ... + = Р}. В дальнейшем нам понадобятся свойства разрядной функции 71. Предложение 1.2. [18] Пусть Я = СЯ(дп,рп)7 а1? ... 7 ат £ Р, и Н = д/р.

Тогда

Yi(ai + ... + am) = ф —j-—^a^1... a^f

< ■ ■ \ j1j . . . jmj

В частности, если a, b G P, mo

p-1 i

Yi(a + b) = V —--ahj bh(p-j} (mod p).

jj(P - j)j

Если R = Zpn, то q = р,ив формулах предложения 1.2 нужно положить h = 1. Из (1.1.6) и предложения 1.2 следует

Предложение 1.3. Для координатных функций (1.1.6) преобразования справедливы равенства

^¿(xi, . . . , Xm) = ai(i1)xi © ... © ai(im)Xm©

е 0 . j 1 . j(ao(i1)xi)hj1... (ao(im)xm)hjm, (1.1.7)

< ■ ■ \ jij ... jmj

где 2 = 1, т.

Предложение 1.4. Для, матрицы А Е Ят,т следующие утверждения эквивалентны:

А

2. Система многочленов (1.1.7) ортогональна.

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

Общие способы построения РП-матриц.

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

Пусть Я = СЩд2,р2),д = рг, р — произвольное простое число. Через Я* будем обозначать множество обратимых эле ментов кольца Я. Рассмотрим т х т

А =

а(1,1) а(2,1)

а(1,2) а(2,2)

а(1, т — 1) а(1т) а(2, т — 1) 0

\

а(т — 1,1) а(т — 1, 2)

у а(т, 1) 0

над Л со свойствами:

0 0

0

а(тт)

/

(1.1.8)

1. а(г, т — г + 1) Е рЯ\{0}, г Е 1, т;

2. а(г,т — г) Е Л*, г Е 1,т — 1;

3. а(т,т) Е Г(Я)*.

В силу пунктов 2, 3 матрица А0 является обратимой.

Покажем, что указанная матрица является раз рядно-подстановочной. Для этого выпишем явный вид координатных функций определяющего отображения па = (фь ..., фт)т матрицы А, используя равенство (1.1.6). Для

г Е 1, т — 1 имеем

т—г+1

фг = 71(ао(г, 1)Х1 + ... + ао(г,т — г + 1)хт—г+1) © ф аДг,;) Свойство 1 означает, что а0(г,т — г + 1) = 0, следовательно

фг = 71 (а(г, 1)х1 + ... + а(г,т — г)хт—г) © «1(г,т — г + 1)жт—г+ь

Кроме того, фт = а1(т1)ж1.

Таким образом, система многочленов (ф1,...,фт) имеет треуголь-

фг

хт—г+1, г Е 1,т. Следовательно, па — биективное отображение, и А — разряд! ю-подстановочна я матрица.

Наконец, вычислим мощность М класса треугольных РП-матриц над кольцом Я = СЩд2,р2) при фиксированном т.

М = (д — 1) • (д — 1)т • (д(д — 1))т—1(д2Г '' = (д — 1)2тд

(т-2)(т-1)

= (д _ 1)2тд(т—1)2

Из произвольных РП-матриц можно составлять РП-матрицы большего размера.

Предложение 1.5. Пусть А1,...,А^ — квадратные матрицы размеров т1,... , соответственно над кольцом Галуа Я. Тогда, матрица А = Бгад(А1,...,А^)7 к Е N размера т = т1 + ... + является разрядно-подстановочной тогда и только т,огда, когда каждая, из матриц

, ] Е 1, к, разрядно-подстановочна. При этом па = (пах ,... , ПАк)Т-

Доказательство этого утверждения очевидно.

Далее будет описан способ получения новых РП-матриц из исходной с помощью преобразований матриц, сохраняющих свойство быть разрядно-подстановочной.

Список литературы диссертационного исследования кандидат наук Аборнев Александр Викторович, 2018 год

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

[1] Abornev, А. V. Nonlinear permutations on a space over a finite field induced by linear transformations of a module over a Galois ring/ A. A. Nechaev, A. V. Abornev// Математические вопросы, криптографии.— 2013. Т. 4. - №2. - С. 81-100.

(Индекс в базе RSCI Web of Science: RSCI:20134175, ISSN:2220-2617)

[2] Аборнев, А. В. Разрядно-ннъектнвные преобразования модуля над кольцом Галуа/ А. В. Аборнев// ПДМ. Приложение. — 2013. №6. — С. 6^7.

[3] Аборнев, А. В. Подстановки, индуцированные разрядно-инъективными преобразованиями модуля над кольцом Галуа/ А. В. Аборнев// Прикладная дискретная математика. — 2013.— №4. — С. 5-15 (Индекс в базе RSCI Web of Science: RSCI:21155546, ISSN:2071-0410).

[4] Аборнев, А. В. Нелинейные подстановки на векторном пространстве, рекурсивно-порождённые над кольцом Галуа характеристики 4/ А. В. Аборнев// ПДМ. Приложение. — 2014. Ш. — С. 40 41.

[5] Abornev, А. V. Recursively-generated permutations of a binary space/ A. V. Abornev// Математические вопросы, криптографии. — 2014. T 5_ _ №2. _ С. 7-20 (Индекс в базе RSCI Web of Science: RSCI:23048430, ISSN:2220-2617).

[6] Аборнев, А. В. Построение подстановок с использованием разрядно-подстановочных преобразований модуля над кольцом Галуа характеристики 4/ А. В. Аборнев// Прикладная дискретная математика. — 2014.

_ С. 9-19 (Индекс в базе RSCI Web of Science: RSCI:21403880, ISSN:2071-0410).

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

[8] Глухов, М. М. О числовых параметрах, связанных с заданием конечных

групп системами образующих элементов/ М. М. Глухов// Тр. по дискр. матем, ТА. М.: ТВП, 1997. С. 43-66.

[9] Глухов, М. М. О 2-транзитивности произведения регулярных групп подстановок/ М. М. Глухов// Труды по дискретной математике. Москва: Физико-математическая литература, 2000. — С. 37-52.

[10] Глухов, М. М. О матрицах переходов разностей при использовании некоторых модулярных групп/ М. М. Глухов// Матем. вопр. крип-тогр2013.— Т. 4. - №4. - С. 27-47.

[11] Глухов, М. М. Алгебра/ М. М. Глухов, В. П. Елизаров, А. А. Нечаев: т. 2. — Москва: Гелиос АРВ, 2003. — 416 с.

[12] Глухов, М. М. О длинах симметрических и знакопеременных групп подстановок в различных системах образующих (обзор)/ М. М. Глухов, А. Ю. Зубов// Математические вопросы, кибернетики. — 1999.— №8. — С. 2-32.

[13] Гонсалес, С. Параметры рекурсивных МДР-кодов/ С. Гонсалес, Е. Ко-усело, В.Т. Марков, A.A. Нечаев// Дискрет, матем. 2000. Т. 12. — ДЧ. - С. 3-24.

[14] Дьёдонне, Ж. Геометрия классических групп/ Ж. Дьёдонне: Band 5. — Москва: МИР, 1974. - 204 с.

[15] Елизаров, В. П. Конечные кольца (основы теории)/ В. П. Елизаров. — Москва: Гелиос-АРВ, 2006. - 304 с.

[16] Кузьмин, А. С. Статистические свойства линейных рекуррент над кольцами Галуа и квазфробениусовыми модулями характеристики 4/ А. С. Кузьмин, В. Л. Куракин, А. А. Нечаев// Труды по дискретной математике. 2001.— Т. 4. — С. 91-128.

[17] Кузьмин, А. С. Линейно представимые коды и код Кердока над произвольным полем Галуа характеристики 2/ А. С. Кузьмин, А. А. Нечаев// Успехи, математических наук. — 1994. Т. 49. — №5 (299). — С. 165-166.

[18] Кузьмин, А. С. Линейные рекуррентные последовательности над кольцами Галуа/ А. С. Кузьмин, А. А. Нечаев// Алгебра и Логика. 1995. Т. 34. - №2. - С. 169-189.

[19] Лидл, Р. Конечные поля/ Р. Лидл, Г. Нидеррайтер: В 2-х т. Т. 1. Пер. с англ. — М: Мир, 1988. — 430 с.

[20] Малышев, Ф.М. Двойственность разностного и линейного методов в криптографии/ Ф.М. Малышев// Матем. вопр. криптогр..— 2014. Т. 5. - №3. - С. 35-47.

[21] Нечаев, А. А. Критерий полноты систем функций рп-значной логики, содержащих операции сложения и умножения по модулю pn/ А. А. Нечаев// Методы дискретного анализа в решении комбинаторных задач, Сборник трудов, .У°34. Новосибирск, 1980. С. 74-87.

[22] Нечаев, А. А. Полновесные модули и представления кодов/ А. А. Нечаев, Т. Хонольд// Пробл. передачи информ..— 1999.— Т. 35. — №3. — С. 18-39.

[23] Никонов, В. Г. О сложности совместной реализации в базисе ДНФ регулярных систем булевых функций/ В. Г. Никонов, А. В. Саранцев// Матем. вопр. криптогр..— 2010.— Т. 1. — №3. — С. 45-65.

[24] Погорелов, Б. А. Основы теории групп подстановок. I. Общие вопросы./ Б. А. Погорелов. — Москва, 1986. — 316 с.

[25] Погорелов, Б. А. Группы подстановок. I. (Обзор за период 1981-1995)/ Б. А. Погорелов// Труды по дискр. мат., Т.2.— Москва: ТВП, 1998. — С. 237-281.

[26] Рожков, М. И. Биективные отображения, порождаемые фильтрующим генератором/ М. И. Рожков// Прикладная дискретная математика. 2014.— Т. 1. - №23. - С. 27-39.

[27] Саранцев, А. В. Построение регулярных систем однотипных двичных функций с использованием регистра сдвига/ А. В. Саранцев// Лесной вестник. — 2004.^ Т. 1. - №32. - С. 164-169.

[28] Сачков, В. Н. Комбинаторика неотрицательных матриц/ В. Н. Сачков. — М: Научное издательство «ТВП», 2000. — 448 с.

[29] Фомичёв, В. М. Методы дискретной математики в криптологии/ В. М. Фомичёв. — Москва: Диалог-МИФИ, 2010. — 424 с.

[30] Blondeau ,С. Perfect Nonlinear Functions and Cryptography/ С. Blondeau, К. Nyberg// Finite Fields Appl. 2015. T. 32. - C. 120-147

[30] Li, С. H. The finite primitive permutation groups containing an abelian regular subgroup/ Cai Heng Li// Proc. London Math. Soc., MR MR2005881 (2004i:20003) — 87, 2003.^ C. 725-747

[31] Call, G. S. Pascal's matrices/ G. S. Call, D. J. Vellman// American Mathenatical Monthly, 100, 1993.^ C. 372-376

[32] Cameron, P. J. Finite permutation groups and finite simple groups/ P. J. Cameron// Bull. London Math. Soc..- 1981.- T. 13. - M. - C. 1-22

[33] Edelman, A. Pascal Matrices/ A. Edelman, Gilbert Strang// American Mathenatical Monthly- 111, 2004. C. 361-385

[34] Edwards, A. W. F. Pascal's Arithmetical Triangle: The Story of a Mathematical Idea,/ A. W. F. Edwards. — Baltimore: Johns Hopkins University Press, 2002.

[35] Greferath, M. Generalized Frobenius extensions of finite rings and trace functions/ M. Greferath, A. A. Nechaev// 2010 IEEE Information Theory Workshop - ITW 2010, 978-1-4244-8263-4 10. Dublin, 2010.

[36] Gross, J. L. Combinatorial Methods with Computer Applications/ Jonathan L.Gross// Discrete Mathematics and Its Applications: Chapman and Hall/CRC, 2007. - 664 c.

[37] Knapp, W. On Burnside's method./ W. Knapp// J. Algebra. — 1995.— T. 175. - C. 644-660

[38] Kuzmin, A. S. Trace-function on a Galois ring in coding theory/ A. S. Kuzmin, A. A. Nechaev//, 1255. Berlin: Springer, 1997. C. 277-290

[39] Nechaev, A. A. On the structure of finite commutative rings with an identity/ A. A. Nechaev// Mathematical Notes.— 1971. T. 10. — C. 840845

[40] Nechaev, A. A. Finite ring with applications/ A. A.Nechaev// Handbook of Algebra, Vol. 5, M. Hazewinkel, éd.: Elsevier, 2008.^ C. 213-320

[41] Pogorelov, B. A. Primitive permutation group that contain a 2m-cycle/ B. A. Pogorelov// Algebra and Logic.- 1980,- T. 19. - №2. - C. 147-155