Методы построения MDS матриц над конечными полями для криптографических приложений тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Малахов Станислав Сергеевич

• Малахов Станислав Сергеевич
• кандидат наук
• 2026

Оглавление диссертации кандидат наук Малахов Станислав Сергеевич

2.1 Введение к разделу

2.2 Описание метода

2.3 Применение метода к матрицам специального вида

2.4 Экспериментальные исследования

2.5 Выводы к разделу

3 О би-регулярных циркулянтных матрицах

3.1 Введение к разделу

3.2 Необходимые и достаточные условия би-регулярности циркулянтной матрицы

3.3 Построение би-регулярных матриц переменных

3.4 Выводы к разделу

4 Проверка признака МЮ8 у циркулянтных матриц и построение циркулянтных МЮ8 матриц

4.1 Введение к разделу

4.2 Эквивалентные подматрицы циркулянтной матрицы

4.3 Транспонированные подматрицы циркулянтной матрицы

4.4 Подмножество М подматриц, достаточное для проверки признака МББ

4.5 Эмпирические результаты

4.5.1 Сравнение экспериментальных методов МВБ тестирования

4.5.2 Поиск циркулянтных МББ матриц размера 8 х

4.5.3 Поиск циркулянтных МББ матриц размера 16 х

4.6 Прямое построение циркулянтных МББ матриц размера 17 х

4.7 Выводы к разделу

5 Заключение 61 Список литературы 63 А Замеры времени МЮЭ тестирования 70 В Списки циркулянтных МЮ8 матриц 71 С Эмпирические функции вероятности

Определения и обозначения

В диссертации применяются следующие определения:

Матрица с большим числом единичных элементов — (к х т)-матрица, число единичных элементов в которой близко к максимальному числу г>&,т, при котором матрица соответствующего размера может быть МЮБ матрицей

Матрица с малым числом различных элементов — (к х т)-матрица, число различных элементов в которой близко к минимальному числу Ск,т, при котором матрица соответствующего размера может быть МЮБ матрицей

В диссертации применяются следующие обозначения:

N — множество {1, 2, 3,... } натуральных чисел

Z — множество {..., -2, —1, 0,1, 2,... } целых чисел

¥я, СР(^) — конечное поле из q элементов

Е* — мультипликативная группа , включающая все элементы за исключением аддитивного нейтрального элемента '0'

{а) — циклическая группа, образованная элементом а

[ж] — кольцо многочленов от одной переменной х с коэффициентами из поля А, М — произвольная матрица I — единичная матрица

Ь — циркулянтная (т х т)-матрица, полученная циклическим сдвигом влево строки (ао,..., ат-\): Ь[г; ]] = а^).

шоа т

И — циркулянтная (т х т)-матрица, полученная циклическим сдвигом вправо строки (ао,... ,ат-г): Я[ц ] ] = а^—).

шоа т

б,, г, ] — векторы (кортежи) — упорядоченные наборы координат (элементов)

М [г0,... ,ги-\; ]0,... — матрица размера и х V, образованная из строк г0,... ,1и-\ и

столбцов ]0,... ,jv-l матрицы М

[а,к,в\ — линейный код с длиной кодового слова п, размерности к и минимальным расстоянием Хэмминга й между кодовыми словами

шг (б) — циклический сдвиг координат вектора (элементов кортежа) б на г позиций влево

[ж] — целая часть х, наибольшее целое число, не превосходящее х

НОД(а, Ь) — наибольший общий делитель целых неотрицательных а и Ь, а + Ь =

Введение

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

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

Современный подход к синтезу блочных криптографических алгоритмов основывается на принципах, введенных Клодом Шенноном в [1]. Шеннон предложил преобразовывать информацию итеративно, реализовывая сложные криптографические преобразования с помощью последовательности простых однотипных отображений. Как правило, одна итерация блочного криптографического алгоритма заключается в воздействии на порцию входных данных композицией отображений, в совокупности реализующих перемешивание и рассеивание данных. В классе широко распространенных XSL алгоритмов перемешивание достигается применением нелинейной подстановки, а рассеивание реализуется линейным преобразованием. Кроме того, для параметризации криптографического преобразования на каждой итерации применяют итерационный ключ. Считается, что перемешивание нарушает статистическую и аналитическую взаимосвязь между знаками блока входных данных и блока выходных данных. Рассеивание в свою очередь обеспечивает зависимость каждого знака выхода от многих знаков входа.

Стойкость и характеристики криптографического алгоритма во многом зависят от свойств отображений, использованных при его синтезе. Так, в работах [2] и [3] Шнорр и Воденэ показали, что недостаточная зависимость знаков выхода от знаков входа может скомпрометировать криптографический алгоритм. Воденэ заключил, что оптимальный с точки зрения криптографического анализа рассеивающий уровень должен строиться с помощью отображения, для которого изменение j из m знаков входного блока приводит к изменению m — j + 1 из m знаков выходного блока.

Следуя [4], рассеивающую способность отображения L : (Fç)п ^ (Fç)т можно описать с помощью коэффициента рассеивания

Если pl = m + 1, то рассеивание, которое реализует отображение L, называют совершенным [5, 6]. В рамках диссертации исследуются отображения, реализующие совершенное в указанном смысле рассеивание.

Отображение L в блочном алгоритме будем называть рассеивающим уровнем.

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

Линейные преобразованиям, которые реализуют совершенное рассеивание, описываются MDS (Maximum Distance Separable) матрицами. Исключительная особенность MDS

матриц состоит в том, что все их миноры порядка и, и > 1, отличны от нуля.

В связи с развитием методов разностного анализа [7, 8, 9, 10, 11] MDS матрицы используются во многих криптографических алгоритмах, включая шифры Rijndael [4], Anubis [12], Khazad [13], IDEA NXT 64/128 (FOX 64/128) [14], SQUAR [15], Twofish [16], Кузнечик [17], а также хэш-функции Whirlpool [18] и Стрибог [17]. Некоторые из указанных алгоритмов стали национальными или международными стандартами информационной безопасности (AES [19], Кузнечик [20] и Стрибог [17]). При этом использование стандартизированных алгоритмов критически важно для создания сертифицированных средств криптографической защиты информации — СКЗИ. Область применения некоторых СК-ЗИ накладывает ограничения на доступные вычислительные ресурсы, что порождает интерес к эффективно вычислимым отображениям. Так, микроконтроллеры MIK51AB72D, MIK51BC16D, MIK51SC72D продукции АО "Микрон", поддерживающие криптографические алгоритмы [19, 20, 17], оборудованы RAM объема 6-8 Кбайт и CPU с частотой 33 МГц. Такие микроконтроллеры используются в российских машиносчитываемых проездных документах и банковских картах, а также идентификационных картах систем контроля удаленного доступа. MDS матрицы успешно используются в условиях ресурсных ограничений [21], а матрицы с большим числом единичных и малым числом различных элементов над полями характеристики 2 вызывают особый интерес с точки зрения уменьшения вычислительной сложности умножения векторов на матрицу [5, 8, 22].

Известны два основных подхода к построению MDS матриц [22] — прямое построение и экспериментальное. Прямое построение предполагает, что некоторая матрица обладает свойством MDS благодаря своим алгебраическим качествам и нет необходимости дополнительно проверять признак MDS. В качестве примера можно привести неединичную подматрицу систематической порождающей матрицы кода Рида-Соломона, которая может быть эффективно построена над конечными полями [23]. Недостаток прямого построения состоит в том, что строить матрицы с заданными эксплуатационными характеристиками, как правило, аналитически сложно. Экспериментальное построение состоит в выборе случайной матрицы из некоторого множества с последующей проверкой того, что все миноры матрицы невырождены. Такой подход позволяет выбирать подходящие элементы, но проверка может быть вычислительно сложной для матриц больших размеров. Тем не менее, для определенных типов матриц проверка быть ускорена за счет сокращения множества вычисляемых миноров [24]. Отсюда мотивация к изучению экспериментального подхода в этой диссертационной работе.

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

Объект исследования — матрицы специального вида и циркулянтные матрицы. Предмет исследования — методы проверки признака MDS и построения MDS матриц, значимых для криптографических приложений.

Степень разработанности темы

Известно [23], что любая порождающая матрица G = [I\М] задает MDS код, если матрица М обладает свойством MDS, а любая порождающая матрица G = [I\М] MDS кода содержит MDS подматрицу М.

Один из основных методов прямого построения MDS матриц использует коды Рида-Соломона, которые могут быть эффективно найдены над произвольными полями. В работе [25] для кода Рида-Соломона, заданного многочленом, описан способ построения порождающей матрицы G = [I\М] в систематическом виде, из которой можно выбрать MDS подматрицу М. Тем не менее, такой способ построения MDS матриц не обеспечивает оптимальный выбор их элементов. Кроме того, известен эффективный прямой метод построения MDS матриц размера к х т с помощью матриц Коши вида а^ = (xi + yj)-1, где хг + Уз = 0, г Е {0,... ,к — 1}, j Е {0,... ,т — 1} [23]. В [26] отмечено, что любой код Рида-Соломона эквивалентен коду, порожденному MDS матрицей Коши. В [27] и [28] авторы предложили строить MDS матрицы с помощью матриц Вандермонда, причем полученная матрица эквивалентна матрице Коши [22], и тем самым также задает код Рида-Соломона.

Экспериментальные методы построения матриц MDS были использованы для синтеза, например, шифров Rijndael [4] и SQUARE [15] и хэш-функции Whirlpool [18]. В этих трех случаях разработчики использовали циркулянтные матрицы MDS. Между тем, цирку-лянтные матрицы обладают некоторыми преимуществами перед матрицами других типов, которые можно считать существенными. Во-первых, они компактны и требуют небольшого объема памяти для их хранения. Во-вторых, они могут иметь относительно немного различных элементов, оставаясь MDS. В-третьих, случайно выбранная циркулянтная матрица с большей вероятностью будет MDS, чем случайная матрица той же размерности [15]. Однако, также присутствует существенный недостаток: циркулянтные матрицы размерности 4 х 4, 8 х 8,16 х 16,... не могут быть инволютивными или ортогональными [22] над полями характеристики 2. Тем не менее, недостаток не имеет значения для хэш-функций и сетей Фейстеля, поскольку в обоих случаях не используются обратные матрицы. Отсюда мотивация изучать в диссертации в том числе циркулянтные матрицы.

Заметим, что в [29] описывается метод прямого построения циркулянтных MDS матриц Коши размера х 2—1 над Fg для нечетных q. Метод можно распространить для четных q, чтобы строить циркулянтные MDS матрицы Коши размера к х k,k\q — 1.

В целом методы построения MDS матриц рассматривались ранее многими авторами, например, [5, 8, 21, 30, 31, 32, 33, 34, 35, 36, 37]. В работах [5, 8, 30, 31, 32] рассматривались MDS матрицы малого размера, в частности, размера 4 х 4. В работах [33, 34, 35] исследовались MDS матрицы, являющиеся степенью сопровождающей матрицы. В работе [5] получены оценки для максимального числа единиц и минимального числа различных элементов в MDS матрицах нескольких видов. В [37] авторы описали возможные группы автоморфизмов MDS матриц над полями характеристики 2 и экспериментально показали, что для матриц размера 8 х 8 и 9 х 9 вероятность случайно выбрать MDS матрицу из множества матриц с соответствующей нетривиальной группой автоморфизмов тем выше, чем

группа автоморфизмов больше. Это позволяет ограничивать область поиска МВБ матриц при экспериментальном построении. Кроме того, авторы экспериментально установили новые оптимальные соотношения между числом единичных и различных элементов в МВБ матрицах размера 8 х 8 и 9 х 9.

В более широком плане тема диссертации лежит в области синтеза и анализа блочных криптографических алгоритмов, которая активно развивается в России. Наряду с линейными отображениями изучаются криптографические и эксплуатационные характеристики нелинейных перемешивающих функций, а также способы их реализации (например, [38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53]). В работах [54, 55] изучается матрично-графовый подход к оценке перемешивающих свойств биективных преобразований регистров сдвига, а также оцениваются характеристики множеств существенных и нелинейных переменных композиции преобразований векторного пространства. В работе [56] описаны криптографические приложения основных результатов исследования примитивности и локальной примитивности орграфов и неотрицательных матриц для оценки перемешивающих свойств преобразований блочных шифров. В статьях [57, 58] предлагаются и исследуются новые шифры, в том числе с длинами блоков 256-1056 бит.

Значительное внимание уделяется анализу блочных шифров и их структурных компонентов [10, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 69, 70, 71]. В частности, в статье [9] показана двойственность линейного и разностного методов в криптографии. Ряд работ посвящен исследованию инвариантных подпространств циркулянтных матриц, рекурсивных матриц, матриц с нетривиальной группой автоморфизмов (например, [72, 73]).

Цели и задачи диссертационного исследования

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

I. матрица содержит как можно больше единичных элементов,

II. матрица содержит как можно меньше различных элементов.

В рамках диссертационного исследования были решены следующие задачи.

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

II Построены новые циркулянтные матрицы переменных с областью Е* возможных значений размера до 32 х 32, которые удовлетворяют дополнительным ограничениям. При этом построенными матрицами переменных исчерпываются виды циркулянтных МВБ матриц, содержащих заданное (максимальное) количество единичных и небольшое число различных элементов.

III С использованием разработанных методов были найдены MDS матрицы размера 8 х 8 над F28, удовлетворяющие дополнительным ограничениям вместе со своими обратными матрицами. Впервые экспериментально получены циркулянтные MDS матрицы размера до 16 х 16 над конечными полями характеристики 2. Кроме того, теоретически были получены циркулянтные MDS матрицы Коши размера 17 х 17 над F28, из которых могут быть тривиально получены MDS матрицы размера 16 х 16, удовлетворяющие дополнительным ограничениям, путем выбора подматриц соответствующего размера.

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

На защиту выносятся следующие основные результаты.

1 Теорема 3.1 о необходимых и достаточных условиях би-регулярности циркулянтной матрицы (Theorem 1 в [74]).

2 Теорема 4.1 о необходимом и достаточном условии эквивалентности подматриц циркулянтной матрицы и ее следствие 4.1, а также предложение 4.2 о наличии транспонированных подматриц циркулянтной матрицы и его следствие 4.2 о симметрических подматрицах (соответственно Theorem 1, Corollary 1, Proposition 3, Corollary 2 в [75]).

3 Алгоритм 2 построения множества подматриц, достаточного для проверки свойства MDS у циркулянтной матрицы (Algorithm 1 в [75]).

4 Теорема 4.2 о том, что множество подматриц, построенное с помощью алгоритма 2, может включать все подматрицы, необходимые для вычисления определителя любой другой подматрицы из этого множества методом Лапласа (Theorem 4 в [75]).

Личный вклад автора

Цели и задачи диссертационного исследования были определены автором совместно с научным руководителем. Автор самостоятельно получил основные результаты 1-4, выносимые на защиту, и решил задачи I—III.

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

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

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

диссертационного исследования MDS матрицы специального вида, а также циркулянтные MDS матрицы размера 8 х 8 над F28, могут использоваться в алгоритме хеширования Стрибог [17]. Построенные в рамках диссертационного исследования MDS матрицы размера 16 х 16, полученные из циркулянтных MDS матриц Коши размера 17 х 17 над F28, могут использоваться в алгоритме шифрования Кузнечик [20].

Научная новизна

Основные результаты, выносимые на защиту являются новыми, и имеют теоретическую и практическую значимость.

Методология и методы исследования

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

Степень достоверности и апробация результатов

Основные результаты, выносимые на защиту, были представлены на конференциях

о The Sixth China-Russia Conference on Numerical Algebra with Applications (CRCNAA 2017) в докладе "Experimental methods of constructing MDS matrices of a special form";

о Engineering Technologies and Informatics: Innovations and Applications (En&T-2021) в докладе "On the construction of bi-regular circulant matrices, relating to MDS matrices"

и опубликованы в следующих работах [75, 74, 24, 76]. Все работы опубликованы в научных изданиях, индексированных в базе данных Scopus. Публикация из списка A журналов НИУ ВШЭ:

о Malakhov, S.S. On the circulant matrix MDS testing and the search for circulant MDS matrices. Cryptogr. Commun. 17, 87-119 (2025), DOI: /10.1007/s12095-024-00746-7

Публикации из списка С журналов НИУ ВШЭ:

о S. S. Malakhov, M. I. Rozhkov, "The construction of circulant matrices related to MDS matrices", Prikl. Diskr. Mat., 2022, no. 56, 17-27, DOI: /10.17223/20710410/56/2

о Rozhkov, M.I., Malakhov, S.S. Experimental Methods for Constructing MDS Matrices of a Special Form. J. Appl. Ind. Math. 13, 302-309 (2019), DOI: /10.1134/S199047891902011X

Прочие публикации из базы данных Scopus:

о S. S. Malakhov and M. I. Rozhkov, "On construction of bi-regular circulant matrices, relating to MDS matrices,"2021 International Conference Engineering Technologies and Computer Science (EnT), Moscow, Russian Federation, 2021, pp. 56-58, DOI: /10.1109/ EnT52731.2021.00016.

Структура диссертации

Диссертация состоит из четырех разделов, не считая введения.

В диссертации исследуются следующие методы построения MDS матриц:

— экспериментальный метод на основе предварительной классификации миноров матриц переменных (раздел 2);

— экспериментальный метод для циркулянтных матриц на основе предварительного построения би-регулярной циркулянтной матрицы переменных и предварительного построения для такой матрицы специального подмножества подматриц, достаточного для проверки признака MDS (раздел 4);

— прямой метод для матриц над полями характеристики 2 на основе циркулянтных MDS матриц Коши (раздел 4).

В разделе 2 исследуется метод, позволяющий проверять признак MDS у матриц, удовлетворяющих заранее известной структуре. Метод основан на предварительной символьной обработке (классификации) миноров матрицы и удалении повторяющихся миноров, а также миноров, отличающихся только знаком. Метод был применен к матрицам размера 8 х 8 двух типов, впервые введенных в [5]. Были получены теоретические и экспериментальные оценки вычислительной сложности предложенного метода, и с его помощью построены некоторые классы MDS матриц.

В разделе 3 предложен подход к построению таких циркулянтных матриц, которые могут быть MDS матрицами, используемыми в криптографии. Здесь рассмотрены би-регулярные циркулянтные матрицы, на которые наложены ограничения с тем, чтобы матрицы имели максимальное число вхождений некоторого элемента и минимальное количество различных элементов. Полученные результаты включают верхнюю границу числа вхождений некоторого элемента, при котором циркулянтная матрица остается би-регулярной, а также необходимые и достаточные условия би-регулярности циркулянтной матрицы. Кроме того, в разделе описан эффективный алгоритм проверки би-регулярности циркулянтной матрицы. С помощью этого алгоритма были построены би-регулярные цир-кулянтные матрицы переменных порядка до 31 с максимальным числом вхождений некоторого элемента, и вместе с тем установлено отсутствие би-регулярных циркулянтных матриц (и следовательно, MDS матриц) порядка 32 с более чем 5 вхождениями одного элемента.

В разделе 4 рассмотрен новый детерминированный метод, который ускоряет проверку признака МВБ у циркулянтной матрицы и поиск циркулянтных МВБ матриц по сравнению с общим методом, основанном на вычислении всех миноров матрицы. Метод заключается в том, чтобы проверить признак МВБ посредством вычисления определителей только тех подматриц, которые лежат в специальном подмножестве, построенном заранее. Показано, что в циркулянтной матрице размера т х т число подматриц, достаточное для проверки признака МВБ, примерно в 2т раз меньше общего числа подматриц. Кроме того, в предложен новый алгоритм прямого построения такого уменьшенного множества подматриц, позволяющий при экспериментальном построении циркулянтных МВБ матриц избежать предварительной классификацией миноров, рассмотренной в разделе 2. Доказано, что определитель подматрицы, входящей в построенное подмножество, всегда можно вычислить методом Лапласа с помощью определителей подматриц меньшего порядка из этого же множества. Вместе с тем приведен метод прямого построения циркулянтных МВБ матриц размера к х к, к\д — 1, а также пример одной из таких матриц размера 17 х 17 над ОЕ(28).

В заключении приведены общие выводы диссертационного исследования.

Автор благодарит Михаила Ивановича Рожкова за научное руководство, внимание к диссертационному исследованию и ценные советы.

Автор благодарит Андрея Александровича Дмуха и Алексея Юрьевича Нестеренко за комментарии и замечания к диссертации.

1 Основные подходы к построению MDS матриц

Приведем определение квадратной MDS матрицы над конечным полем.

Определение 1.1. Пусть М = Мтхт — матрица с элементами из некоторого конечного поля Fg. М — MDS матрица, если min^ex w (х) = т + 1, где w (х) — вес вектора х, х G X = | ..., хт, М (х\,..., хт)Т^ |, т.е. минимальный вес сред всех ненулевых векторов х, образованных сцеплением векторов (х\,... ,хт) размерности т с векторами М (х\,... ,хт)Т размерности т, равен т +1.

MDS матрицы тесно связаны с MDS кодами (Maximum Distance Separable), являющимися подклассом линейных кодов.

Определение 1.2. Линейный [п, k, d] код — линейное пространство из векторов длины п размерности к над полем Fg с минимальным расстоянием Хемминга d между кодовыми словами.

Для линейных [n,k,d] кодов известно соотоношение: k < п — d +1; если достигается граница Синглтона, т.е. если выполняется равенство d = п — к + 1, то код называется MDS кодом. Укажем далее связь между MDS матрицами и MDS кодами, для чего рассмотрим линейный [n,k,d] код с порождающей матрицей вида G = [I\А], где I — единичная матрица. Если в качестве матрицы А выбрана матрица Мтхт, то линейный [п, к, d] код принимает вид [2т, т, т + 1]. Следующие два утверждения раскрывают взаимосвязь между MDS кодами и MDS матрицами.

Теорема 1.1 ([23]). [n,k,d] код с порождающей матрицей [Jkxk\Akx(n-k)] является MDS кодом, если и только если каждая квадратная подматрица А невырожденная.

Теорема 1.2 ([23]). Матрица М размера т х п обладает свойством MDS, если и только если каждый ее минор порядка и, и > 1, отличен от нуля.

Из теорем 1.1 и 1.2 следует, что MDS код имеет в качестве A MDS матрицу и наоборот.

Как правило в алгоритмах защиты информации используют MDS матрицы размера 4 х 4, 8 х 8 или 16 х 16 [4, 12, 13, 14, 15, 16, 17, 18, 17]. При этом особую роль играют матрицы размера 16 х 16 над полем F28, поскольку позволяют целиком преобразовывать блоки длины 128 бит современных блочных алгоритмов.

Интерес к MDS матрицам обусловлен тем, что изменение одного знака входного вектора (x\,...,xs) влечет изменение всех г координат выходного вектора (х\,...,хг) = М (x\,...,Xs)T. Существенным вопросом остается построение подобных матриц и проверка признака MDS у произвольных матриц. В настоящее время известны различные формы матриц, которые могут обладать свойством MDS, например, циркулянтные матрицы вида

R (ai,...,an)

(а\ а2

ап а\

\0>2 «3 11

ап

&П-1

Такие объекты применяются в алгоритмах защиты информации, обеспечивающих как конфиденциальность, так и целостность данных. Для алгоритма АЕБ ([4])

R (02i6, 03i6, 01i6, 01ie)

является матрицей размера 4 х 4 над полем F28, заданным многочленом х8 + х4 + х3 + х +1; для алгоритма Whirlpool ([18])

R (01i6, 01i6, 04i6, 01i6, 08i6, 05i6, 02i6, 09i6)

является матрицей размера 8 х 8 над F28, заданным многочленом х8 + х4 + х3 + х2 +1. Удобство циркулянтов состоит в том, что достаточно задать первую (одну) строку матрицы, при этом остальные строки задаются циклическим сдвигом.

Циркулянты — не единственный класс матриц, который рассматривался исследователями. В [28] показывается, как построить MDS код из матриц Вандермонда.

Определение 1.3. Матрицей Вандермонда называется двумерный массив вида

V г.

(Xi,..., х,п)

1 1 1 \

xi Х2 • •

2 i 2 х2 . ф2

\х i х2 ™т— i

или его транспонированная форма.

Приведем две теоремы, доказанные в [28].

Теорема 1.3. Пусть V (а1,... ,аг) — матрица Вандермонда. Для любых (а1,... ,аг) и (Ь1, . . . , Ьг) из У таких, что щ, Ь^ — 2г различных элементов, матрица V(а1,..., аг)-1х V (Ь1,... ,ЬГ) не имеет вырожденных квадратных подматриц.

Теорема 1.4. Пусть V (а1,..., аи) — невырожденная матрица Вандермонда размера к х к, а V (Ь1,... ,Ьп-к) имеет размер к х (п — к). Тогда код, ассоциированный с матрицей @ = [1к|V (а1,..., ак)-1 х V (Ь1,..., Ьп-к)], — ИББ код, если только все щразличны, г е {1,... ,к} ,3 е{1,...,п — к}.

Результаты теорем 1.3 и 1.4 позволяют строить МВБ коды, которые, как было показано выше, тесно связаны с МВБ матрицами.

Еще один изучаемый класс матриц — матрицы Адамара, которые используются при построении блочных АЕБ-подобных алгоритмов: АпиЫя, Khazad ([12, 13] соответственно).

Определение 1.4. Квадратная матрица Н (а0,... ,ат-1) порядка т = 2*,1 е N вида = а^ называется матрицей Адамара.

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

Рассеивающий уровень шифра Khazad задает отображение 9 : (F28 )8 ^ (F28 )8 на основе MDS кода [16, 8, 9] с порождающей матрицей G = [I\Н], где матрица Адамара Н (0116, 03i6, 04i6, 05i6, 06i6, 08i6, 0&i6, 07i6). Ее явный вид можно найти в [13].

Линейное отображение 9 : (F28 )8 ^ (F28)8 алгоритма Anubis задается проще: с использованием MDS кода [8, 4, 5] с порождающей матрицей Н (1i6, 2i6, 4i6, 6i6); явный вид матрицы приведен в [12].

Элементы матриц алгоритмов Anubis и Khazad лежат в поле F28, заданном многочленом х8 + х4 + х3 + х + 1. Обе матрицы были найдены перебором.

Гуо и др. в [77] предъявили MDS матрицу, удобную для аппаратной реализации, в рамках семейства PHOTON низкоресурсных алгоритмов, обеспечивающих проверку целостности информации. Она не представляет собой инволюцию, поэтому требует вычисления матрицы обратного преобразования, хотя и оно эффективно реализуемо аппаратными средствами. Рассмотрим матрицу

А

0 1 0 0 •• ■ 0 0 0 0

0 0 1 0 •• ■ 0 0 0 0

= 0 0 0 0 •• ■0 1 0 0

0 0 0 0 •• ■0 0 1 0

0 0 0 0 •• ■0 0 0 1

Z2 ^з •• ■ Zd- 4 Zd-3 Zd-2 Zd-i)

G{0,.. .,d — 1 } выбираются так, что Ad — MDS матрица.

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

f (х)

X

— (Zq + ZiX + + ■ ■ ■ + Zd-iXd-^ .

Сопровождающую матрицу можно сокращено записать с помощью строки коэффициентов характеристического многочлена: А = Serial (Zq, ... , Zd-i). Перебором авторы нашли коэффициенты, обеспечивающие для Ad свойство MDS. В работе [77] приводятся шесть MDS матриц размера d х d,d G {5, 6, 7, 8}.

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

Список литературы диссертационного исследования кандидат наук Малахов Станислав Сергеевич, 2026 год

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

[1] C. E. Shannon. "Communication theory of secrecy systems". In: The Bell system technical journal 28.4 (1949), pp. 656-715.

[2] C. P. Schnorr and S. Vaudenay. "Black box cryptanalysis of hash networks based on multipermutations". In: Workshop on the Theory and Application of of Cryptographic Techniques. Springer. 1994, pp. 47-57.

[3] S. Vaudenay. "On the need for multipermutations: Cryptanalysis of MD4 and SAFER". In: International Workshop on Fast Software Encryption. Springer. 1994, pp. 286-297.

[4] J. Daemen and V. Rijmen. The design of Rijndael. Vol. 2. Springer, 2002.

[5] P. Junod and S. Vaudenay. "Perfect diffusion primitives for block ciphers". In: International Workshop on Selected Areas in Cryptography. Springer. 2004, pp. 84-99.

[6] M. Sajadieh, M. Dakhilalian, and H. Mala. "Perfect involutory diffusion layers based on invertibility of some linear functions". In: IET information security 5.4 (2011), pp. 228236.

[7] E. Biham and A. Shamir. "Differential cryptanalysis of DES-like cryptosystems". In: Journal of CRYPTOLOGY 4.1 (1991), pp. 3-72.

[8] A. V. Anashkin. "Complete description of a class of MDS-matrices over finite field of characteristic 2". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 8.4 (2017), pp. 5-28.

[9] F. M. Malyshev. "The duality of differential and linear methods in cryptography". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 5.3 (2014), pp. 35-47.

[10] F. M. Malyshev and D. I. Trifonov. "Diffusion properties of XSLP-ciphers". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 7.3 (2016), pp. 47-60.

[11] M. Matsui. "On correlation between the order of S-boxes and the strength of DES". In: Workshop on the Theory and Application of of Cryptographic Techniques. Springer. 1994, pp. 366-375.

[12] V. Rijmen and P. S. L. M. Barreto. "The anubis block cipher". In: Submission to NESSIE (2000).

[13] P. S. L. M. Barreto and V. Rijmen. "The Khazad legacy-level block cipher". In: Primitive submitted to NESSIE 97 (2000), p. 106.

[14] P. Junod and S. Vaudenay. "FOX: a new family of block ciphers". In: International Workshop on Selected Areas in Cryptography. Springer. 2004, pp. 114-129.

[15] J. Daemen, L. Knudsen, and V. Rijmen. "The block cipher Square". In: Fast Software Encryption. Ed. by E. Biham. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997, pp. 149-165. isbn: 978-3-540-69243-0.

[16] B. Schneier et al. "Twofish: A 128-bit block cipher". In: NIST AES Proposal 15.1 (1998), pp. 23-91.

[17] GOST R 34-11-2012: Information technology. Cryptographic data security. Hashing function. (in Russian). 2012.

[18] P. S. L. M. Barreto and V. Rijmen. "The Whirlpool hashing function". In: First open NESSIE Workshop, Leuven, Belgium. Vol. 13. 2000, p. 14.

[19] M. Dworkin et al. Advanced Encryption Standard (AES). 2001.

[20] GOST R 34-12-2015: Information technology. Cryptographic data security. Block ciphers. (in Russian). 2015.

[21] K. C. Gupta and I. G. Ray. "On constructions of MDS matrices from companion matrices for lightweight cryptography". In: International Conference on Availability, Reliability, and Security. Springer. 2013, pp. 29-43.

[22] K. C. Gupta et al. "Cryptographically significant MDS matrices over finite fields: A brief survey and some generalized results". In: Advances in Mathematics of Communications 13.4 (2019), pp. 779-843. issn: 1930-5346.

[23] F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Vol. 16. Elsevier, 1977.

[24] M. I. Rozhkov and S. S. Malakhov. "Experimental methods for constructing MDS matrices of a special form". In: Journal of Applied and Industrial Mathematics 13.2 (2019), pp. 302-309.

[25] D. J. J. Versfeld et al. "On systematic generator matrices for Reed-Solomon codes". In: IEEE Transactions on Information Theory 56.6 (2010), pp. 2549-2550.

[26] R. Roth and G. Seroussi. "On generator matrices of MDS codes (Corresp.)" In: IEEE Transactions on Information Theory 31.6 (1985), pp. 826-830.

[27] J. Lacan and J. Fimes. "A construction of matrices with no singular square submatrices". In: International conference on finite fields and applications. Springer. 2003, pp. 145147.

[28] J. Lacan and J. Fimes. "Systematic MDS erasure codes based on Vandermonde matrices". In: IEEE Communications Letters 8.9 (2004), pp. 570-572.

[29] R. M. Roth and A. Lempel. "On MDS codes via Cauchy matrices". In: IEEE transactions on information theory 35.6 (1989), pp. 1314-1319.

[30] D. Augot and M. Finiasz. "Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions". In: 2013 IEEE International Symposium on Information Theory. IEEE. 2013, pp. 1551-1555.

[31] A. V. Belov, A. B. Los, and M. I. Rozhkov. "Some Approaches to Construct MDS Matrices over a Finite Field". In: Commun. Appl. Math. Comp 31.2 (2017), pp. 143152.

[32] A. V. Belov, A. B. Los, and M. I. Rozhkov. "Some classes of the MDS matrices over a finite field". In: Lobachevskii Journal of Mathematics 38.5 (2017), pp. 880-883.

[33] E. Couselo et al. "Recursive MDS-codes and recursive differentiable quasigroups". In: Discrete Mathematics and Applications 8.3 (1998), pp. 217-246.

[34] E. Couselo et al. "Parameters of recursive MDS-codes". In: Discrete Mathematics and Applications 10.5 (2000), pp. 433-454.

[35] K. C. Gupta and I. G. Ray. "On constructions of circulant MDS matrices for lightweight cryptography". In: International Conference on Information Security Practice and Experience. Springer. 2014, pp. 564-576.

[36] A. M. Youssef, S. Mister, and S. E. Tavares. "On the design of linear transformations for substitution permutation encryption networks". In: Workshop on Selected Areas of Cryptography (SAC'96): Workshop Record. 1997, pp. 40-48.

[37] D. A. Burov and S. V. Kostarev. "Using the automorphism group to construct MDS-matrices". In: Prikladnaya Diskretnaya Matematika. Supplement 18 (2025), pp. 14-19.

[38] O. A. Logachev, A. A. Salnikov, and V. V. Yashchenko. "Bent functions on a finite Abelian group". In: Discrete Mathematics and Applications 7.6 (1997), pp. 547-564.

[39] O. A. Logachev, S. V. Smyshlyaev, and V. V. Yashchenko. "New methods of investigation of perfectly balanced Boolean functions". In: Diskretnaya Matematika 21.2 (2009), pp. 51-74.

[40] V. M. Fomichev and P. V. Ovchinnikov. "On the construction of s-boxes of 4 x 4 size". In: Prikladnaya Diskretnaya Matematika. Supplement 10 (2017), pp. 104-106.

[41] O. A. Logachev, S. N. Fedorov, and V. V. Yashchenko. "Boolean functions as points on the hypersphere in the Euclidean space". In: Discrete Mathematics and Applications 29.2 (2019), pp. 89-101.

[42] F. M. Malyshev. "Functional circuits defining families of permutations of the space GF(2)n". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 10.3 (2019), pp. 81-87.

[43] D. B. Fomin. "New classes of 8-bit permutations based on a butterfly structure". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 10.2 (2019), pp. 169-180.

[44] D. B. Fomin and D. I. Trifonov. "Hardware implementation of one class of 8-bit permutations". In: Prikladnaya Diskretnaya Matematika. Supplement 12 (2019), pp. 134137.

[45] D. A. Burov. "On relationship between the parameters characterizing nonlinearity and nonhomomorphy of vector spaces transformation". In: Discrete Mathematics and Applications 29.5 (2019), pp. 287-294.

[46] D. B. Fomin. "On the algebraic degree and differential uniformity of permutations on the space V2m constructed via (2m, m)-functions". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 11.4 (2020), pp. 133-149.

[47] D. B. Fomin. "On the way of constructing differentially 2$-uniform permutations over F22m". In: Prikladnaya Diskretnaya Matematika. Supplement 14 (2021), pp. 51-55.

[48] V. M. Fomichev. "On the Degree of Nonlinearity of the Coordinate Polynomials for a Product of Transformations of a Binary Vector Space". In: Journal of Applied and Industrial Mathematics 15.2 (2021), pp. 212-222.

[49] S. A. Davydov and I. A. Kruglov. "A method of construction of differentially 4-uniform permutations over Vm for even m". In: Discrete Mathematics and Applications 31.6 (2021), pp. 383-388.

[50] M. A. Kovrizhnykh and D. B. Fomin. "Heuristic algorithm for obtaining permutations with given cryptographic properties using a generalized construction". In: Prikladnaya Diskretnaya Matematika 3 (2022), pp. 5-21.

[51] D. B. Fomin and M. A. Kovrizhnykh. "On differential uniformity of permutations derived using a generalized construction". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 13.2 (2022), pp. 37-52.

[52] D. B. Fomin and D. I. Trifonov. "Computational work for some TU-based permutations". In: Prikladnaya Diskretnaya Matematika 2 (2025), pp. 29-55.

[53] D. A. Burov and I. M. Karabeynikov. "Diffusion of systems of blocks for the translation group F™+ of the vector space F™ by permutations with nontrivial automorphism group". In: Diskretnaya Matematika 37.3 (2025), pp. 50-71.

[54] A. M. Koreneva and V. M. Fomichev. "Mixing properties of modified additive generators". In: Journal of Applied and Industrial Mathematics 11.2 (2017), pp. 215-226.

[55] V. M. Fomichev. "Estimating nonlinearity characteristics for iterative transformations of a vector space". In: Journal of Applied and Industrial Mathematics 14.4 (2020), pp. 610622.

[56] Y. E. Avezova. "Primitivity and local primitivity of digraphs and nonnegative matrices". In: Journal of Applied and Industrial Mathematics 12.3 (2018), pp. 453-469.

[57] V. M. Fomichev et al. "Evaluation of the maximum performance of block encryption algorithms". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 10.2 (2019), pp. 181-191.

[58] V. Fomichev and A. Koreneva. "Encryption performance and security of certain wide block ciphers". In: Journal of Computer Virology and Hacking Techniques 16.3 (2020), pp. 197-216.

[59] A. V. Erokhin, F. M. Malyshev, and A. E. Trishin. "Multidimensional linear method and diffusion characteristics of linear medium of ciphering transform". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 8.4 (2017), pp. 29-62.

[60] D. A. Burov and B. A. Pogorelov. "An attack on 6 rounds of Khazad". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 7.2 (2016), pp. 3546.

[61] D. A. Burov and B. A. Pogorelov. "The permutation group insight on the diffusion property of linear mappings". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 9.2 (2018), pp. 47-58.

[62] F. M. Malyshev. "Probabilistic characteristics of differential and linear relations for non-homogeneous linear medium". In: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] 10.1 (2019), pp. 41-72.

[63] D. I. Trifonov and D. B. Fomin. "Invariant subspaces in SPN block cipher". In: Priklad-naya Diskretnaya Matematika 4 (2021), pp. 58-76.

[64] V. M. Fomichev, A. Kurochkin, and A. Chuhno. "The difference relations and impossible differentials construction for the KB-256 algorithm". In: Prikladnaya Diskretnaya Matematika. Supplement 15 (2022), pp. 73-77.

[65] F. M. Malyshev. "Methods of linear and differential relations in cryptography". In: Diskretnaya Matematika 34.1 (2022), pp. 36-63.

[66] D. I. Trifonov. "Flaws of hypercube-like ciphers". In: Prikladnaya Diskretnaya Matematika 3 (2022), pp. 52-66.

[67] D. A. Burov. "On the existence of special nonlinear invariants for round functions of XSL-ciphers". In: Discrete Mathematics and Applications 33.2 (2023), pp. 65-75.

[68] R. Astrakhantsev et al. "Differences with high probability and impossible differentials for the KB-256 cipher". In: Journal of Computer Virology and Hacking Techniques 20.3 (2024), pp. 525-531.

[69] D. A. Burov. "On a relationship between linear and differential characteristics of binary vector spaces mappings and diffusion characteristics over blocks of imprimitivity systems of translation group of the binary vector space". In: Discrete Mathematics and Applications 34.3 (2024), pp. 121-144.

[70] D. A. Burov. "Linear diffusion layer and nonlinear invariants for XSL-algorithms". In: Diskretnaya Matematika 37.2 (2025), pp. 14-40.

[71] A. Chuhno. "On the possibility of modifying the KB-256 algorithm from the searching for impossible differentials view point". In: Prikladnaya Diskretnaya Matematika 1 (2025), pp. 70-79.

[72] S. A. Davydov. "Invariant subspaces of circulant and recursive matrices". In: Diskretnaya Matematika 36.4 (2024), pp. 44-63.

[73] D. A. Burov and S. V. Kostarev. "Invariant subspaces of matrices with a nontrivial automorphism group". In: Prikladnaya Diskretnaya Matematika. Supplement 18 (2025), pp. 19-23.

[74] S. S. Malakhov and M. I. Rozhkov. "The construction of circulant matrices related to MDS matrices". In: Prikladnaya Diskretnaya Matematika 56 (2022), pp. 17-27.

[75] S. S. Malakhov. "On the circulant matrix MDS testing and the search for circulant MDS matrices". In: Cryptography and Communications (2024), pp. 1-33.

[76] S. S. Malakhov and M. I. Rozhkov. "On construction of bi-regular circulant matrices, relating to MDS matrices". In: 2021 International Conference Engineering Technologies and Computer Science (EnT). 2021, pp. 56-58.

[77] J. Guo, T. Peyrin, and A. Poschmann. "The PHOTON family of lightweight hash functions". In: Annual Cryptology Conference. Springer. 2011, pp. 222-239.

[78] D. Augot and M. Finiasz. "Direct construction of recursive MDS diffusion layers using shortened BCH codes". In: International Workshop on Fast Software Encryption. Springer. 2014, pp. 3-17.

[79] M. Y. Malik and J.-S. No. "Dynamic MDS matrices for substantial cryptographic strength". In: arXiv preprint arXiv:1108.6302 (2011).

[80] K. C. Gupta, S. K. Pandey, and I. G. Ray. "Applications of design theory for the constructions of MDS matrices for lightweight cryptography". In: Journal of Mathematical Cryptology 11.2 (2017), pp. 85-116.

[81] I. Reiman. "Uber ein problem von K. Zarankiewicz". In: Acta Mathematica Academiae Scientiarum Hungarica 9.3 (1958), pp. 269-273.

[82] R. Lidl and H. Niederreiter. Introduction to finite fields and their applications. Cambridge university press, 1994.

[83] M. J. Hall. "Combinatorial theory". In: Blaisdell, Waltharn, Mass 196 (1986).

[84] K. Zarankiewicz. "Problem P 101". In: Colloq. Math. Vol. 2. 301. 1951, p. 5.

[85] S. Roman. "A problem of Zarankiewicz". In: Journal of Combinatorial Theory, Series A 18.2 (1975), pp. 187-198. issn: 0097-3165.

[86] K. Cattell et al. "Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF (2)". In: Journal of Algorithms 37.2 (2000), pp. 267-282.

[87] M. Liu and S. M. Sim. "Lightweight MDS Generalized Circulant Matrices". In: Fast Software Encryption. Ed. by T. Peyrin. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016, pp. 101-120. isbn: 978-3-662-52993-5.

Приложение A Замеры времени MDS тестирования

Таблица A.1: Время т\, т2, т3 выполнения алгоритма 3 в секундах, когда MDS тестирование проводится относительно S = Т, относительно М и относительно набора всех подматриц

при обработке фиксированного множества из 4096 матриц L$, элементы которых лежат в {ж, ж + 1, ж2,..., ж2 + х +1}

Ti т2 тз Т2/Т1 Т3/Т2 Т3/Т1 MDS матрицы

69.9 150.5 1244.2 2.2 8.3 17.8 46

при обработке 46 MDS матриц L5 из упомянутого выше множества

П_Г2_Тз Т2/-Г1 Т3/т2 Т3/п_

7.1 41.4 524.8 5.8 12.7 73.9_

при обработке фиксированного множества из 4096 матриц Lq, элементы которых лежат в {ж, ж + 1, ж2,..., ж2 + ж +1}

Ti т2 тз Т2/Т1 Т3/Т2 Т3/Т1 MDS матрицы

~30.0 53.0 435.4 1.8 8.2 14.5 19

при обработке 19 MDS матриц Lq из упомянутого выше множества П_Т2_Тз Т2/Т1 т^/т2 т3/п_

2.8 14.7 189.5 5.3 12.9 67.7_

при обработке фиксированного множества из 4096 матриц L5, элементы которых являются случайными элементами GF(28), отличными от '0' и '1'

Т1 т2 тз Т2/Т1 т^/т2 Т3/Т1 MDS матрицы

~232.6 1259.4 11808.8 5.4 9.4 50.8 132

при обработке 132 MDS матриц L5 из упомянутого выше множества

П_Т2_Т3 Т2/Т1 т^/т2 Т3/Т1_

82.8 406.5 5384.6 6.9 13.2 91.6_

при обработке фиксированного множества из 4096 матриц Lq, элементы которых являются случайными элементами GF(28), отличными от '0' и '1'

Tj_Т2_т3 Т2/Т1 Т3/Т2 Т3/Т1_MDS matrices_

223.3 1132.5 10598.9 5.1 9.4 47.5_148_

при обработке 148 MDS матриц Lq из упомянутого выше множества

П Т~2_Т3 Т2/Т1 Т3/Т2 Т3/Т1_

86.1 410.6 5415.5 4.8 13.2 62.9

Приложение Б Списки циркулянтных МВ8 матриц

Таблица В.1: МББ матрицы Ь5, Ь6 над [ж] / (ж8 + х6 + х3 + х2 + 1) с элементами из {1,х,х +1,ж2,... ,х2 + х +1}, а также соответствующие обратные матрицы (Х5)-1 , (Х6)-1 , заданные одной строкой. Обратные матрицы имеют повторяющийся элемент хя, 0 < в < 8. Десятичные числа N = с0 + с\2 + • • • + сп2п обозначают элементы поля с0 + с\х + • • • + спхп

Ь 5 (^Г

(01, ,01, ,06, 12, 06, ,09, 12, 03) (186, ,070, ,056, ,184,016, ,182, ,016, ,047)

(01, ,01, ,09, ,08, 09, ,10, ,08, 14) (230, ,016, ,067, ,016,111, ,218, ,141, 206)

(01, ,01, 12, ,14, 12, ,10, ,14, 04) (160, ,043, 116, ,070,159, ,001, ,001, 028)

Ь 6 (£еГ

(01, ,01, ,04, ,01, 15, ,07, ,14, 05) (064, ,201, ,026, ,145,074, ,253, ,151, 064)

(01, ,01, ,05, ,01, 06, ,07, 12, 04) (237, ,178, ,021, ,145,187, ,062, ,128, ,128)

(01, ,01, ,05, ,01, 15, ,08, ,09, 14) (125, ,064, ,064, ,063,094, ,048, ,236, 147)

(01, ,01, ,06, ,01, 09, ,03, ,11, 13) (008, 139, ,081, ,072,209, ,096, ,008, 007)

(01, ,01, ,09, ,01, 15, ,14, ,05, 08) (125, ,063, ,236, ,064,094, ,147, ,064, ,048)

(01, ,01, 11 ,01, 09, ,13, ,06, 03) (008, ,072, ,008, ,139,209, ,007, ,081, ,096)

(01, ,01, 12, ,01, 06, ,04, ,05, 07) (237, ,145, ,128, ,178,187, ,128, ,021, 062)

(01, ,01, ,14, ,01, 15, ,05, ,04, 07) (064, ,145, ,151, ,201,074, ,064, ,026, 253)

Таблица В.2: МББ матрицы Ь6 над [х] / (х + х6 + х3 + х2 + 1) с элементами из {1,х,х + 1,х2,...,х2 + х + 1}, а также соответствующие обратные матрицы (Ьб) , заданные одной строкой. Обратные матрицы имеют несколько повторяющихся элементов. Десятичные числа N = с0 + С\2 + • • • + сп2п обозначают элементы поля с0 + с\х + • • • + спхп

¿6 (Ье)-1

(01,01,03,01,14,11,06,08) (040,119,127,090,044,126,044,040) (01,01,06,01,12,14,15,04) (103,177,081,235,177,138,010,103)

(01.01.06.01.14.08.03.11) (040,090,044,119,044,040,127,126)

(01.01.07.01.03.04.15.12) (128,060,020,062,014,076,062,076)

(01.01.12.01.10.08.14.07) (176,191,191,068,212,176,076,190)

(01.01.14.01.10.07.12.08) (176,068,076,191,212,190,191,176) (01,01,15,01,03,12,07,04) (128,062,062,060,014,076,020,076) (01,01,15,01,12,04,06,14) (103,235,010,177,177,103,081,138)

Таблица В.3: Циркулянтные МББ матрицы Коши размера 17 х 17 над [х] / (х8 + х6 + х3 + х2 + 1), заданные одной строкой. Десятичные числа N = с0 + С\2 + • • • + сп2п обозначают

элементы поля с0 + с\х + • • • + спхп_

(100,032,083,226,026,173,143,114,090,052,212,086,007,005,079,122,196) (160,192,036,121,202,225,240,234,021,009,017,022,252,107,217,153,135) (201,146,141,132,246,131,228,137,112,230,204,207,030,035,013,057,044) (092,071,065,151,076,105,089,220,243,211,149,239,155,163,050,170,043) (109,075,176,209,063,096,184,218,190,011,029,237,068,128,095,039,159) (157,214,250,119,199,111,194,046,025,183,124,059,081,254,117,127,041) (002,164,049,144,067,248,055,103,186,169,099,189,222,181,167,061,139) (166,180,223,188,098,168,187,102,054,249,066,145,048,165,003,138,060) (116,255,080,058,125,182,024,047,195,110,198,118,251,215,156,040,126) (094,129,069,236,028,010,191,219,185,097,062,208,177,074,108,158,038) (051,162,154,238,148,210,242,221,088,104,077,150,064,070,093,042,171) (012,034,031,206,205,231,113,136,229,130,247,133,140,147,200,045,056) (216,106,253,023,016,008,020,235,241,224,203,120,037,193,161,134,152) (078,004,006,087,213,053,091,115,142,172,027,227,082,033,101,197,123)

Таблица В.4: Некоторые MDS матрицы Lw и ¿12 над полем F2 [ж] / (ж22 + ж21 + 1), заданные одной строкой. Десятичные числа N =

ср + с\2 + • • • + Сп2п обозначают элементы поля ср + с\х + • • • + спхп_

(1,1,1075231,3177736,1075231,2263278,3177736,2459033,3895615,2263278,2157291,2951456,2459033,562397,662651,3895615) (1,1,3474782,62033,3474782,3057272,62033,1292048,457441,3057272,2221014,2009098,1292048,3984134,1814386,457441)

(1,1,3021573,1,676565,1889484,736266,1,1008342,676565,2612510,2296334,1853395,3722585,2669745,2333279)

Таблица В.5: Некоторые MBS матрицы Lw над F2 [ж] / (ж23 + ж18 + 1), заданные одной строкой. Десятичные числа N = Ср + Ci2 + • • ■ + сп2п

обозначают элементы поля ср + С\х + • • • + спхп_

(1,1,3466158,3103251,3466158,7456267,3103251,3405462,5894942,7456267,6203146,552147,3405462,7966601,141029,5894942) (1,1,3243520,6583130,3243520,2793702,6583130,1218131,2204937,2793702,3494109,5856912,1218131,3568776,4230092,2204937) (1,1,7251903,2696181,7251903,8187952,2696181,4832199,1893639,8187952,5081409,4472827,4832199,7919505,4522425,1893639) (1,1,1659875,1578917,1659875,2306310,1578917,98249,4315287,2306310,5403877,845774,98249,1346673,3491771,4315287) (1,1,1498094,3325710,1498094,823684,3325710,6699424,3659243,823684,5972679,612443,6699424,1065370,5311394,3659243) (1,1,2550770,7602617,2550770,7516666,7602617,5159233,2970044,7516666,4431858,1388384,5159233,2650393,3752531,2970044)

Таблица В.6: Некоторые MBS матрицы ¿12 над F2 [ж] / (ж23 + ж18 + 1), заданные одной строкой. Десятичные числа N = Ср + Ci2 + • • ■ + сп2п

обозначают элементы поля ср + С\х + • • • + спхп_

(1,1,7395930,1,5618740,8323328,104672,1,2036991,5618740,1721205,4340740,1076177,7890974,1444087,8191983) (1,1,2251939,1,3547424,1226052,4966919,1,3944075,3547424,7835406,1311050,7228852,717124,4266617,3199953) (1,1,4253703,1,2471719,1456513,1843935,1,7898569,2471719,2225940,1227451,4517932,155200,4868273,4707646) (1,1,1718408,1,5843190,2693034,290779,1,6660684,5843190,2118828,1202213,5745585,2721593,1674836,74039) (1,1,5580392,1,2128642,4549061,6556922,1,624062,2128642,4739635,913810,5049663,659087,752537,1047179) (1,1,1041222,1,1417217,6977684,507391,1,3162729,1417217,402312,5080736,5988853,7246892,4311856,2220803) (1,1,4932740,1,3784831,3233054,6437533,1,7975811,3784831,4699410,6940646,2138844,2837297,6485926,4003151) (1,1,7721571,1,771052,1559619,4801210,1,7941746,771052,1585086,7316045,5619241,596310,7237556,2071389) (1,1,7026950,1,3939162,6194167,6957018,1,4912085,3939162,5415382,4154953,7034407,7783412,5981934,7178086)

Таблица В.7: Некоторые МБЭ матрицы £10 над полем [ж] / (ж24 + ж23 + ж21 + ж20 + 1), заданные одной строкой. Десятичные числа

N = с0 + С\2 + • • • + сп2п обозначают элементы поля с0 + С\Х + • • • + спхп_

(1,1,14477196,2932535,14477196,9437708,2932535,13782607,435976,9437708,13313877,12689566,13782607,5404130,15977965,435976) (1,1,11341655,7961298,11341655,1092898,7961298,6122584,7133374,1092898,4047565,11794254,6122584,9556587,15337173,7133374) (1,1,3744312,12451605,3744312,2058840,12451605,9947437,10077432,2058840,9668930,13644577,9947437,11486680,16485772,10077432) (1,1,13924692,11858544,13924692,7978106,11858544,12553748,2598418,7978106,9262574,4361138,12553748,112928,15539512,2598418) (1,1,4421052,2740492,4421052,15478055,2740492,566234,11816568,15478055,15838586,15785579,566234,10529095,688291,11816568) (1,1,151398,7811572,151398,16140094,7811572,14512378,3146548,16140094,12272800,16406420,14512378,13765883,9901079,3146548) (1,1,4561171,2727129,4561171,14311164,2727129,7786807,10995646,14311164,1169591,12976953,7786807,370956,15714334,10995646) (1,1,8998548,1905679,8998548,217472,1905679,12968931,13525817,217472,6516632,13768052,12968931,11977759,4710218,13525817) (1,1,3731042,3194751,3731042,1719816,3194751,9788223,10533794,1719816,11605299,2697935,9788223,8419424,532187,10533794) (1,1,11646413,13248685,11646413,863934,13248685,3149850,9935949,863934,1472533,1030860,3149850,310968,15035864,9935949) (1,1,3463331,13211688,3463331,9035260,13211688,5563085,6521428,9035260,11259674,8574110,5563085,8141315,13816411,6521428) (1,1,1640210,8351074,1640210,16330806,8351074,592314,11837244,16330806,10510436,9156967,592314,14751065,8992323,11837244) со (1,1,13383996,6218617,13383996,9819146,6218617,8912135,7348068,9819146,13180202,3604359,8912135,7052925,10462415,7348068) (1,1,14942343,4948270,14942343,8762543,4948270,1156760,4800507,8762543,14904659,14566181,1156760,5993241,1683199,4800507) (1,1,13156332,12289493,13156332,5688174,12289493,14670008,9970408,5688174,12099788,14746635,14670008,5094169,282469,9970408) (1,1,16728094,9347062,16728094,10866735,9347062,5716831,4578201,10866735,8288656,9671388,5716831,837881,4551721,4578201) (1,1,1204221,14590031,1204221,15369986,14590031,9874190,10963467,15369986,1636909,12792767,9874190,14051603,5836331,10963467) (1,1,9170890,15646312,9170890,6218364,15646312,10977532,12353188,6218364,7411533,11561344,10977532,15796615,4266452,12353188) (1,1,14170812,14363437,14170812,4324403,14363437,10885070,7408459,4324403,2875322,6706444,10885070,13469276,9924057,7408459) (1,1,15216060,741645,15216060,2506945,741645,12619522,8899631,2506945,14988579,1434482,12619522,11197076,13778925,8899631) (1,1,9462915,897292,9462915,1226655,897292,13020159,13729547,1226655,5824460,7763352,13020159,11221513,15620851,13729547) (1,1,14550318,14554106,14550318,10315405,14554106,15556861,2352946,10315405,10707453,3047786,15556861,14022910,1500203,2352946) (1,1,666419,7828221,666419,9250587,7828221,11787992,14918313,9250587,3849482,10797986,11787992,10645802,10618628,14918313) (1,1,5330859,11189584,5330859,810421,11189584,14022168,9770487,810421,4414275,7134651,14022168,4939884,13258076,9770487) (1,1,12300161,2405994,12300161,10927391,2405994,16075391,9453963,10927391,5314882,8431846,16075391,15756075,11992201,9453963) (1,1,12696462,6458173,12696462,2162072,6458173,16557698,15574761,2162072,13491189,4434788,16557698,14713076,8359932,15574761) (1,1,8602146,10271690,8602146,4695840,10271690,16441066,7894407,4695840,15894599,4794973,16441066,14981975,12420496,7894407)

Таблица В.8: Некоторые МВЭ матрицы ¿12 над полем [ж] / (ж24 + ж23 + ж21 + ж20 + 1), заданные одной строкой. Десятичные числа

N = ср + с\2 + • • • + Сп2п обозначают элементы поля ср + с\х + • • • + спхп_

(1,1,4814712,1,15291045,12278355,12546816,1,1294373,15291045,5214300,12443310,11317237,8984994,2382832,4654701) (1,1,8821737,1,4045839,1243658,14901842,1,13135369,4045839,13500770,2561080,8876358,3758028,15702521,4524113) (1,1,14477196,1,2932535,9437708,13782607,1,435976,2932535,13313877,12689566,5404130,15977965,3570854,13748139) (1,1,12387198,1,1601141,13783624,1347919,1,14620431,1601141,732875,16632735,7160243,14985761,8045412,10924758) (1,1,1345028,1,7286686,1118988,2514774,1,14540279,7286686,8988886,15106836,4457077,13682040,4338137,2472236) (1,1,9840559,1,3268826,9163637,11231519,1,9986781,3268826,10512529,13596666,10475305,2806143,12884754,6394757) (1,1,4767465,1,12216141,1556940,5594571,1,7634312,12216141,8347413,13003860,11854422,6305318,5239145,5164116) (1,1,13924692,1,11858544,7978106,12553748,1,2598418,11858544,9262574,4361138,112928,15539512,11060777,7965601) (1,1,9828458,1,2534330,3034145,13922754,1,8628749,2534330,5005625,7198972,14320203,12950614,2795792,8787265) (1,1,15262953,1,12430340,4941876,729700,1,13403520,12430340,10468289,3338573,3814101,13250070,15139617,7646389) (1,1,13706183,1,5143001,2068173,10684553,1,3000506,5143001,572100,14282224,8086710,11428499,11289764,11484654) (1,1,1642972,1,6974384,1851263,3011471,1,2263670,6974384,16438800,13175578,15419238,15294805,2277869,9144664) (1,1,3463331,1,13211688,9035260,5563085,1,6521428,13211688,11259674,8574110,8141315,13816411,11370678,761824) ^ (1,1,13901158,1,14180301,9786021,14215968,1,3727722,14180301,8940561,9419566,10520696,789290,6172721,6844329) (1,1,14485616,1,15578550,1379710,1622412,1,7258493,15578550,903176,5215985,10749688,2906571,16714048,12340932) (1,1,13156332,1,12289493,5688174,14670008,1,9970408,12289493,12099788,14746635,5094169,282469,9657460,14772798) (1,1,16344554,1,16454200,137560,12996243,1,8351769,16454200,2644241,4775658,1169873,2311378,7791369,572253) (1,1,14170812,1,14363437,4324403,10885070,1,7408459,14363437,2875322,6706444,13469276,9924057,9493534,11834884) (1,1,14545771,1,14325042,2711142,8272123,1,7888351,14325042,5734937,15953351,12311030,16477327,16768559,11647619) (1,1,15216060,1,741645,2506945,12619522,1,8899631,741645,14988579,1434482,11197076,13778925,10763672,818817) (1,1,14550318,1,14554106,10315405,15556861,1,2352946,14554106,10707453,3047786,14022910,1500203,14004600,6486466) (1,1,1892583,1,1678057,9573963,6907883,1,16345930,1678057,30439,10140380,11912383,5230645,10292642,7970634) (1,1,666419,1,7828221,9250587,11787992,1,14918313,7828221,3849482,10797986,10645802,10618628,10482743,4284598) (1,1,9546821,1,12771799,6113031,317702,1,5233119,12771799,16509467,15715651,8000954,713066,3036718,1600427) (1,1,3831345,1,4778278,1968389,12055471,1,13559974,4778278,12508793,9131463,4141274,3262414,3231997,1074112) (1,1,9613077,1,5752867,5496165,14960134,1,3726928,5752867,7792273,6934187,9120164,3705470,6117965,12186961) (1,1,8105060,1,11765674,15481872,3889619,1,2693693,11765674,11378056,11703691,9781853,1433171,1889130,12768723) (1,1,4770592,1,2310539,13940944,12449324,1,14722752,2310539,2284511,7295154,8335272,5474912,5169186,5716171)

(1,1,426571,1,3581230,11465776,13148593,1,4623308,3581230,14668427,3985923,6379621,7881626,13527771,16484821)_

Таблица В.9: Некоторые МБЭ матрицы Ею над Е2 [ж] / (ж32 + ж30 + х29 + ж26 + ж24 + .х22 + х21+х18 + ж16 + ж14 + ж13 + ж10 + ж8 + ж6 + ж5 + ж2 +1), заданные одной строкой. Десятичные числа N = Со + С\2 + • • • + сп2п обозначают элементы поля Со + С\Х + • • • + спхп

(1,1,3906643608,2577580526,3906643608,1701769139,2577580526,926462344,2940342415,1701769139,3348300770,348569610,926462344,3032102219,1931833133,2940342415)

(1,1,19187947,3526735185,19187947,1702152647,3526735185,2124984018,2141207595,1702152647,4283878372,3609560897,2124984018,2968904461,3273705827,2141207595)

(1,1,1908626993,3109864485,1908626993,3455167185,3109864485,3489934741,2460798848,3455167185,2173893150,434151055,3489934741,1360290438,1675427434,2460798848)

(1,1,3346477505,955209337,3346477505,2370584368,955209337,381450286,3900202102,2370584368,3618113202,850932025,381450286,2901404383,198698860,3900202102)

(1,1,1411657537,2778006527,1411657537,978081088,2778006527,269343197,57658838,978081088,1583289361,416000649,269343197,443335937,2935472726,57658838)

(1,1,2457209813,3476475914,2457209813,31127709,3476475914,1670428272,4287816006,31127709,3678428092,2261404322,1670428272,1747941033,2978702006,4287816006)

(1,1,1961125939,126540450,1961125939,703436109,126540450,732861730,1627284904,703436109,2925410796,2408499830,732861730,2733111119,1137005031,1627284904)

(1,1,3784422394,3744544058,3784422394,2694953254,3744544058,2808726796,2790263430,2694953254,570250110,3230880400,2808726796,1085484939,1740386000,2790263430)

(1,1,4159425911,2230321528,4159425911,438315689,2230321528,1919338307,1241721988,438315689,1177304949,713131125,1919338307,2985161055,2766567481,1241721988)

(1,1,1480628278,3265171800,1480628278,3622564839,3265171800,1036234676,4201889509,3622564839,3005229808,2784516539,1036234676,622048518,3240994356,4201889509)_

сл

Таблица В.10: Некоторые МБЭ матрицы Ь12 над Е2 [ж]/(ж32 + ж30 + ж29 + ж26 + ж24 + ж22 + ж21 + ж18 + ж16 + ж14+ж13+ж10+ж8 + ж6+ж5 + ж2 + 1), заданные одной строкой. Десятичные числа N = Со + С\2 + • • • + сп2п обозначают элементы поля Со + С\Х + • • • + спхп

(1,1,3906643608,1,2577580526,1701769139,926462344,1,2940342415,2577580526,3348300770,348569610,3032102219,1931833133,3014848784,1544972080)

(1,1,19187947,1,3526735185,1702152647,2124984018,1,2141207595,3526735185,4283878372,3609560897,2968904461,3273705827,1051783840,2498302096)

(1,1,1908626993,1,3109864485,3455167185,3489934741,1,2460798848,3109864485,2173893150,434151055,1360290438,1675427434,1694754197,1912980363)

(1,1,3346477505,1,955209337,2370584368,381450286,1,3900202102,955209337,3618113202,850932025,2901404383,198698860,2531601033,3413993200)

(1,1,2457209813,1,3476475914,31127709,1670428272,1,4287816006,3476475914,3678428092,2261404322,1747941033,2978702006,485017805,1448157591)

(1,1,1961125939,1,126540450,703436109,732861730,1,1627284904,126540450,2925410796,2408499830,2733111119,1137005031,1520801903,1176439688)

(1,1,3784422394,1,3744544058,2694953254,2808726796,1,2790263430,3744544058,570250110,3230880400,1085484939,1740386000,1765260279,115738101)

(1,1,4159425911,1,2230321528,438315689,1919338307,1,1241721988,2230321528,1177304949,713131125,2985161055,2766567481,2944309315,988775677)

(1,1,1480628278,1,3265171800,3622564839,1036234676,1,4201889509,3265171800,3005229808,2784516539,622048518,3240994356,3734693096,1676423721)

Приложение О Эмпирические функции вероятности

Таблица С.1: Эмпирические функции вероятности Рг^Х = и) = ри случайной величины X, представляющей минимальную размерность вырожденных подматриц, полученные из 100 наблюдений случайных матриц над СЕ (2*) \{0,1}, г Е {8,..., 24}. Наблюдение и = то означает нахождение МЮБ матрицы

Поле Рг1 (X = м) = р«

СЕ(28) Р2 = 79 100 Р3 = 21 100

СЕ(29) Р2 = 60 100 Р3 = 40 100

СЕ(210) Р2 = 34 100 Р3 = 66 100

СЕ(2И) Р2 = 16 100 Р3 = 84 100

СЕ(212) Р2 = 11 100 Р3 = 89 100

СЕ(213) Р2 = 5 100 Р3 = 95 100

СЕ(214) Р2 = 3 100 Р3 = 97 100

СЕ(215) Р3 = 96 100 Р4 = 4 100

СЕ(216) Р2 = 1 100 Р3 = 76 100 Р4 = 23 100

СЕ(217) Р3 = 64 100 Р4 = 35 100 Р5 = 1 100

СЕ(218) Р3 = 41 100 Р4 = 54 100 Р5 = 5 100

СЕ(219) Р3 = 25 100 Р4 = 56 100 Р5 = 19 100

СЕ(220) Р3 = 12 100 Р4 = 41 100 Р5 = 43 100 Р6 = 3 100 Р7 = 1 100

СЕ(221) Р3 = 5 100 Р4 = 25 100 Р5 = 53 100 Р6 = 14 100 Р7 = 3 100

СЕ(222) Р3 = 3 100 Р4 = 15 100 Р5 = 34 100 Р6 = 31 100 Р7 = 13 100

СЕ(223) Р3 = 1 100 Р4 = 10 100 Р5 = 18 100 Р6 = 40 100 Р7 = 21 100

СЕ(224) Р3 = 2 100 Р4 = 5 100 Р5 = 8 100 Р6 = 23 100 Р7 = 17 100

Р11 = 1 27

100 = 100

Р8

1

100

Р9

1

100

9 _ з

100 -Р9 = 100 Р^

2 100 6 100

Р8 =

10 100

61 Р9 = 160 Р10 = 100

»

оо

Таблица С.2: Эмпирические функции вероятности Рг2(Х = и) = ри случайной величины X, представляющей минимальную размерность вырожденных подматриц, полученные из 100 наблюдений случайных матриц Ь\2 над СЕ (2*) \ {0,1}, г € {8,..., 24}. Наблюдение и = то означает нахождение МЮБ матрицы

Поле РГ2 (X = и) = р«

СЕ(28) Р2 = 82 100 Р3 = 18 100

СЕ(29) Р2 = 62 100 Р3 = 38 100

СЕ(210) Р2 = 36 100 Р3 = 64 100

СЕ(2И) Р2 = 18 100 Р3 = 82 100

СЕ(212) Р2 = 14 100 Р3 = 86 100

СЕ(213) Р2 = 4 100 Р3 = 96 100

СЕ(214) Р2 = 1 100 Р3 = 99 100

СЕ(215) Р2 = 1 100 Р3 = 96 100 Р4 = 3 100

СЕ(216) Р2 = 1 100 Р3 = 80 100 Р4 = 19 100

СЕ(217) Р3 = 53 100 Р4 = 47 100

СЕ(218) Р3 = 32 100 Р4 = 61 100 Р5 = 7 100

СЕ(219) Р3 = 22 100 Р4 = 55 100 Р5 = 23 100

СЕ(220) Р3 = 14 100 Р4 = 29 100 Р5 = 50 100 Р6 = 7 100

СЕ(221) Р3 = 2 100 Р4 = 24 100 Р5 = 47 100 Р6 = 22 100 Р7 = 3 100 Р8 = 2 100

СЕ(222) Р3 = 3 100 Р4 = 9 100 Р5 = 33 100 Р6 = 38 100 Р7 = 12 100 Р8 = 4 100

СЕ(223) Р3 = 1 100 Р4 = 7 100 Р5 = 25 100 Р6 = 28 100 Р7 = 15 100 Р8 = 9 100

Р11 = 1 100 9 100

СЕ(224) 1 Р3 = 2 100 1 Р4 = 4 100 Р5 = 29 8 100 Р6 = 20 100 Р7 = 25 100 Р8 = 6 100

Р11 = 100 Р12 100 Рж 100

Р<х, =

1

100

_ 4 _ 1

Р9 = ХМ Р10 = Юс

3 100

1

100