Разработка методов построения MDS матриц специального вида над полем GF(256)

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Московский институт электроники и математики им. А.Н. Тихонова

Разработка методов построения MDS матриц специального вида над полем GF(256)

Дуванов Иван Владимирович



АННОТАЦИЯ

В работе проводятся исследования по разработке и оценке эффективности методов построения MDS матриц специального вида над полем GF(256).

Исследуются циклические матрицы размера nЧn, 12?n?16, в каждой строке которых 4 единицы и заданное число различных элементов (от 7 до 12).

Для снижения сложности проверки свойства MDS важной характеристикой является число различных миноров заданного размера. В работе получены точные значения для числа миноров без дубликатов в случае матрицы размера 12Ч12 в каждой строке которой 3 единицы и 7 различных элементов над конечным полем GF(256). Проведены экспериментальные исследования по оценке частоты встречаемости дубликатов случайно выбранного минора заданной размерности kЧk, 5?k?11 для матриц размера nЧn, 13?n?16. Полученные в работе результаты свидетельствуют о возможности снижения сложности проверки свойства MDS у матриц рассмотренного типа (ожидаемое снижение в 20-30 раз).

ABSTRACT

In this work, studies are conducted to develop and evaluate the effectiveness of methods for constructing MDS matrices of a special kind over the GF field (256).

We study cyclic matrices of size n Ч n, 12=n=16, in each row of which there are 4 units and a given number of different elements (from 7 to 12).

To reduce the complexity of checking MDS properties, an important characteristic is the number of different minors of a given size. In this work, we obtained exact values ??for the number of minors without duplicates in the case of a 12 Ч 12 matrix in each row of which there are 3 units and 7 different elements above the final field GF (256). Experimental studies were conducted to estimate the frequency of occurrence of duplicates of a randomly selected minor of a given dimension k Ч k, 5=k=11 for matrices of size n Ч n, 13=n=16. The results obtained in the work indicate the possibility of reducing the complexity of checking the MDS properties of matrices of the considered type (the expected decrease is 20-30 times).



Введение

матрица минор дубликат

В данной работе проводится экспериментальное исследование методов построения MDS матриц размера 12х12 определенного вида в конечных полях . В рамках поставленной задачи найдено число миноров без дубликатов, необходимых для проверки матрицы, заданной шаблоном. Также получены экспериментальные оценки встречаемости миноров для матриц размера nЧn, 13?n?16, заданных шаблоном.

Требования к созданию современных блочных криптографических шифров были введены Клодом Шенноном в [17]. Данные требования, называемые принципами Шеннона, накладывают определенные условия на применяемые в шифре преобразования. Разделяются такие условия на два вида - рассеивание и перемешивание.

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

"Хорошее" рассеивание (в том числе достигаемое с помощью MDS матриц) заключается в том, что при изменении малого числа координат входа изменяется большое число координат выхода.

MDS матрицы применяются для выполнения свойства рассеивания в качестве линейного преобразования текущей итерации во многих криптографических системах, например, AES, FOX64, «Стрибог» и «Кузнечик» Приводится по Нестеренко А.Ю., Лось А.Б., Рожков М.И. Криптографические методы защиты информации: учебник для академического бакалавриата. М. Юрайт, 2016..

В числе первых такую идею высказал Водене (в работе [11]).

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

Данная работа разбита на три главы. В первой главе приводится обзор существующих исследований по теме MDS матриц, во второй главе описывается проведенная работа по нахождению точного числа миноров без дубликатов для матрицы размера 12Ч12, в третьей главе описаны испытания по получению экспериментальной оценки встречаемости миноров для матриц размера nЧn, 13?n?16, заданных шаблоном.



ГЛАВА 1. ОБЗОР ИССЛЕДОВАНИЙ ПО ТЕМЕ MDS МАТРИЦ

1.1 Теория по MDS матрицам

Определение. Матрица c коэффициентами из поля называется MDS-матрицей, если у матрицы любая квадратная подматрица является невырожденной, то есть имеющей определитель, отличный от нуля.[8]

Существуют три типа матриц часто используемые в работе с MDS матрицами: би-регулярные, циркулянтные и сопровождающие.

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

Определение. Матрица размера называется би-регулярной, если таковой является любая ее подматрица.

Определение. Матрица, не являющаяся би-регулярной, называется би-сингулярная.

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

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

Данный тип матриц известен тем, что линейные преобразование, построенные на их основе, решаются с помощью алгоритма быстрого преобразования Фурье. В государственном стандартов шифрования AES, например, цирулянтные матрицы применяются на этапе MixColumns.

Определение. Для заданного многочлена

под его сопровождающей матрицей понимается матрица А вида

и используется обозначение [1]

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

Определение. Пусть d - минимальное кодовое расстояние, тогда , где - максимальное количество возможных кодовых слов длины и минимального расстояния .

Определение. Линейные коды, достигающие равенства в утверждении границы Синглетона, называются MDS-кодами.

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

Связь между MDS-кодами и MDS-матрицами заключается в том, что если - MDS матрица, то

является линейным MDS-кодом размерности n с длиной блока n+m и минимальным кодовым расстоянием m+1 Приводится по Нестеренко А.Ю., Лось А.Б., Рожков М.И. Криптографические методы защиты информации: учебник для академического бакалавриата. М. Юрайт, 2016..

1.2 Методы нахождения MDS матриц

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

Одним из способов поиска новой MDS матрицы является метод умножения уже имеющейся MDS матрицы на ненулевой элемент поля.

1.2.1 Метод поиска MDS матриц на основе сопровождающих матриц

Еще одним вариантом поиска MDS матриц является метод, представленный в [1]. Авторы использовали сопровождающую матрицу

для полинома .

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

в поле, где

и - корень неприводимого многочлена .

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

Также теме получения MDS матриц из сопровождающих посвящена работа [2]. Там изучаются сопровождающие матрицы нескольких типов и выводятся ограничения на переменные, необходимые для получения MDS матрицы. В частности, обобщается результаты статьи [1]: авторы рассматривают матрицы вида , которая в своем частном проявлении является матрицей, рассмотренной в [1], и высказывают для них несколько предложений.

1.2.2 Метод поиска MDS матриц на основе матриц Вандермонда

В [3] работе рассматривается вариант конструирования MDS матриц на основе свойства матриц Вандермонда.

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

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

1.2.3 Метод поиска MDS матриц на основе матриц Коши.

Определение. Матрицей Коши, основанной на переменных называется матрица, чьи элементы представимы в виде

.

Лемма. Пусть даны , и матрица

,

которая является матрицей Коши. Тогда ее определитель имеет вид

Следовательно, при соблюдении условий и определители всех квадратных подматриц матрицы Коши отличны от 0 в любом поле A.M. Youssef, S. Mister and S.E. Tavares, On the Design of Linear Transformations for Substitution Permutation Encryption Networks, Department Of Electrical and Computer Engineering, Queen's University, Kingston, Ontario, Canada.

1.2.4 Метод поиска MDS матриц для низкоресурсной криптографии.

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

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

Определение. Матрица размера называется инволютивной, если для нее справедливо , где - единичная матрица размера .

1.2.5 Метод поиска MDS матриц на основе технической реализации

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

1.2.6 Метод поиска MDS матриц на основе случайных матрицы и вектора

В работе [15] рассматривается подход к построению MDS матриц размера 4х4, основанный на эффективном алгоритме умножения вектора на выбранную матрицу.

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

В [15] приводится два алгоритма, для построения случайной матрицы в поле и для построения случайной матрицы, обладающей свойством MDS. Дополнительным требованием к алгоритму построения MDS матрицы является ограничение на подаваемую на вход случайно генерируемую матрицу М, а именно: значение не генерируется предварительно, а вычисляется в результате работы алгоритма.

1.2.7 Метод поиска MDS матриц на основе кодов Рида-Соломона

Одной из известных возможностей построения MDS матриц является их генерация на основе одного из классов MDS кода, и именно коды Рида-Соломона.

Определение. Пусть Тогда нормированный полином минимальной степени над полем , корнями которого являются идущих подряд степеней , является порождающим полиномом кода Рида-Соломона над полем и имеет вид

При этом длина кода имеет значение , а минимальное расстояние равно .

Большое количество исследований [17-19] на эту тему объясняется относительной простотой предложенных методов построения MDS матриц. Кроме того, использование кодов Рида-Соломона позволяет строить MDS матрицы необходимого размера. Общая идея этого пути основывается на известном доказательстве того, что код Рида-Соломона является MDS кодом и состоит в построении кода Рида-Соломона с подходящими параметрами.

Интересные результаты представлены в работе [16], где авторы предлагают алгоритм построения рекурсивных MDS матриц на основе кода Рида-Соломона.

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

.

Предложение. Пусть - MDS код (т.е. ). Если , то с его помощью можно построить рекурсивную MDS матрицу размера .

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

Выход алгоритма: рекурсивная матрица над полем .

Шаг 1. Выбрать , удовлетворяющее условию . Составить код Рида-Соломона , где или .

Шаг 2. Представить порождающую матрицу в виде , где - матрица размера .

Шаг 3. Выбрать квадратную подматрицу размера матрицы . Выбранная матрица будет рекурсивной MDS матрицей.

Также в работе приводится вычислительная сложность алгоритма:

Выбор

Расчет

Поиск порождающей матрицы кода Рида-Соломона:

Представление порождающей матрицы в новом виде:

Выбор квадратной подматрицы: .

Итоговая вычислительная сложность представленного алгоритма равна

,

что можно сократить до

1.2.8 Метод поиска «эффективных» MDS матриц

Еще одним методом составления MDS-матриц является поиск так называемых «эффективных» матриц. Под эффективной матрицей, авторы [9] понимают матрицы с наибольшим количеством «1» и наименьшим количеством попарно различных элементов. Это введение сделано с точки зрения того, что умножение на 1 «бесплатно» и, следовательно, способно увеличить вычислительную эффективность системы, обрабатывающей MDS матрицы.

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



ГЛАВА 2. РАСЧЕТ ТОЧНОГО ЧИСЛА МИНОРОВ ДЛЯ МАТРИЦЫ РАЗМЕРА 12Ч12

В рамках поставленной задачи ниже приведено точное число миноров для матрицы размера 12Ч12, заданной шаблоном.

Шаблон матрицы размера 12Ч12:

В данном шаблоне 7 различных неединичных элемента. При этом в каждой строке по 3 единицы.

Стандартным методом построения матриц является перебор различных вариантов параметров ,g в надежде случайным образом обнаружить MDS матрицу. Матрицу исследуют на MDS свойство, проверяя определители всех квадратных подматриц на неравенство 0 для конкретных значений параметров. Для этого перед началом работы строится множество всех необходимых для проверки определителей, высчитанных по шаблону в общем виде. Данный метод является вычислительно трудоемким - для проверки одной матрицы размера 12Ч12 требуется вычислить 2 704 155 определителей.

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

В качестве поля используется факторкольцо

где - неприводимый многочлен степени 8, равный

.

Размер подматриц	Общее число миноров, заданного размера	Число миноров после удаления дубликатов	Время работы программы
1x1	144	7	0.1 сек
2x2	4356	195	0.1 сек
3x3		2127	3 сек
4x4		10461	180 сек
5x5		26532	70 минут
6x6	853776	38752	1230 минут
7x7		26833	71 минута
8x8		10572	182 сек
9x9		2193	5 сек
10x10	4356	201	0.1 сек
11x11	144	11	0.1 сек
12x12	1	1	0.1 сек
Всего определителей	2704155	117885

Таблица 1 - число миноров для матрицы размера 12x12

Среднее число встречаемости дубликатов для матрицы размера 12x12 = 22,94.



ГЛАВА 3. ПРОВЕДЕНИЕ ИСПЫТАНИЙ ПО ЭКСПЕРИМЕНТАЛЬНОЙ ОЦЕНКЕ ЧИСЛА РАЗЛИЧНЫХ МИНОРОВ ДЛЯ МАТРИЦ РАЗМЕРА nЧn, 13?n?16

Для матриц размера nЧn, 13?n?16 посчитать точное число миноров без дубликатов не представляется возможным, ввиду трудоемкости задачи. Была проведена экспериментальная оценка числа различных миноров для матриц заданного размера.

3.1 Экспериментальная оценка числа различных миноров для матрицы размера 13Ч13

Для матрицы размера 13Ч13 было выбрано 1000 случайных миноров и проведены испытания по сравнению выбранного минора (размера kЧk) с общим множеством миноров того же размера на поиск дубликатов.

Шаблон матрицы размера 13Ч13:

В шаблоне 9 различных неединичных элемента. При этом в каждой строке по 4 единицы.

Размер подматриц	Общее число миноров, заданного размера	Среднее число встречаемости дубликатов	Число миноров после удаления дубликатов	Время работы программы
1x1	169	18,77	9	0.1 сек
2x2	6084	23,58	258	0.1 сек
3x3	81796	24,87	3289	3 сек
4x4	511225	25,53	20020	330 сек
5x5	1656369	?23,94	?69188	15 минут (1000 испытаний)
6x6	2944656	?24,72	?119120	49 минут (1000 испытаний)
7x7	2944656	?24,59	?119750	51 минута (1000 испытаний)
8x8	1656369	?23,69	?69918	17 минут (1000 испытаний)
9x9	511225	25,35	20166	335 сек
10x10	81796	24,34	3361	3 сек
11x11	6084	22,12	275	0.1 сек
12x12	169	15,36	11	0.1 сек
13x13	1	1	1	0.1 сек
Всего определителей	10400599		?425366

Таблица 2 - число миноров для матрицы размера 13x13

Среднее число встречаемости дубликатов для матрицы размера 13x13 ? 24,45.

3.2 Экспериментальная оценка числа различных миноров для матрицы размера 14Ч14

Для матрицы размера 14Ч14 было выбрано 100 случайных миноров и проведены испытания по сравнению выбранного минора (размера kЧk) с общим множеством миноров того же размера на поиск дубликатов.

Шаблон матрицы размера 14Ч14:

В шаблоне 8 различных неединичных элемента. При этом в каждой строке по 3 единицы.

Размер подматриц	Общее число миноров, заданного размера	Среднее число встречаемости дубликатов	Число миноров после удаления дубликатов	Время работы программы
1x1	196	24,5	8	0.1 сек
2x2	8281	26,54	312	0.1 сек
3x3	132496	26,97	4912	8 сек
4x4	1002001	27,60	36302	900 сек
5x5	4008004	?28,15	?142380	10 минут (100 испытаний)
6x6	9018009	?28,72	?313997	68 минут (100 испытаний)
7x7	11778624	?29,30	?402000	257 минут (100 испытаний)
8x8	9018009	?28,68	?314405	71 минута (100 испытаний)
9x9	4008004	?27,97	?143254	11 минут (100 испытаний)
10x10	1002001	27,11	36957	915 сек
11x11	132496	26,17	5063	9 сек
12x12	8281	24,64	336	0.1 сек
13x13	196	17,8	11	0.1 сек
14x14	1	1	1	0.1 сек
Всего определителей	40116599		?1399938

Таблица 3 - число миноров для матрицы размера 14x14

Среднее число встречаемости дубликатов для матрицы размера 14x14 ? 28,65.

3.3 Экспериментальная оценка числа различных миноров для матрицы размера 15Ч15

Для матрицы размера 15Ч15 было выбрано 100 случайных миноров и проведены испытания по сравнению выбранного минора (размера kЧk) с общим множеством миноров того же размера на поиск дубликатов.

Шаблон матрицы размера 15Ч15:

В данном шаблоне 10 различных неединичных элементов. В каждой строке по четыре единицы.



Размер подматриц	Общее число миноров, заданного размера	Среднее число встречаемости дубликатов	Число миноров после удаления дубликатов	Время работы программы
1x1	225	25	9	0.1 сек
2x2	11025	32,14	343	0.1 сек
3x3	207025	28,12	7363	15 сек
4x4	1863225	26,56	70153	1140 сек
5x5	9018009	?29,35	?307257	18 минут (100 испытаний)
6x6	25050025	?30,8	?813312	94 минуты (100 испытаний)
7x7	41409225	?32,51	?1273738	474 минуты (100 испытаний)
8x8	41409225	?32,37	?1279246	479 минут (100 испытаний)
9x9	25050025	?30,65	?817292	99 минут (100 испытаний)
10x10	9018009	?29,18	?309047	20 минут (100 испытаний)
11x11	1863225	26	71639	1156 сек
12x12	207025	27,74	7462	17 сек
13x13	11025	30,79	358	0.1 сек
14x14	225	20,45	11	0.1 сек
15x15	1	1	1	0.1 сек
Всего определителей	155117519		?4957231

Таблица 4 - число миноров для матрицы размера 15x15

Среднее число встречаемости дубликатов для матрицы размера 15x15 ? 31,29

3.4 Экспериментальная оценка числа различных миноров для матрицы размера 16Ч16

Для матрицы размера 16Ч16 было выбрано 100 случайных миноров (50 миноров для подматриц размера nЧn, 6?n?10) и проведены испытания по сравнению выбранного минора (размера kЧk) с общим множеством миноров того же размера на поиск дубликатов.

Шаблон матрицы размера 16Ч16:

В каждой строке данного шаблона по 4 единицы.

Размер подматриц	Общее число миноров, заданного размера	Среднее число встречаемости дубликатов	Число миноров после удаления дубликатов	Время работы программы
1x1	256	21,33	12	0.1 сек
2x2	14400	28,12	512	0.1 сек
3x3	313600	29,60	10592	19 сек
4x4	3312400	28,79	115028	245 минут
5x5	19079424	?30,3	?629683	35 минут (100 испытаний)
6x6	64128064	?31,2	?2055386	74 минуты (50 испытаний)
7x7	130873600	?31,8	?4115522	168 минут (50 испытаний)
8x8	165636900	?32,2	?5144003	450 минут (50 испытаний)
9x9	130873600	?31,74	?4123302	171 минута (50 испытаний)
10x10	64128064	?30,9	?2075341	78 минут (50 испытаний)
11x11	19079424	?30,1	?633867	39 минут (100 испытаний)
12x12	3312400	28,74	115254	252 минуты
13x13	313600	29,52	10623	20 сек
14x14	14400	27,43	525	0.1 сек
15x15	256	16	16	0.1 сек
16x16	1	1	1	0.1 сек
Всего определителей	601080389		?19029667

Таблица 5 - число миноров для матрицы размера 16x16

Среднее число встречаемости дубликатов для матрицы размера 16x16 ? 31,59

3.5 Сравнение числа встречаемости дубликатов миноров для матриц размера nЧn, 12?n?16

В ходе выполнения работы были получены результаты по встречаемости миноров для матриц размера nЧn, 12?n?16, заданных шаблоном.

Размер матрицы	Среднее число встречаемости дубликатов миноров
12Ч12	23
13Ч13	24
14Ч14	29
15Ч15	31
16Ч16	32

Таблица 6 - среднее число встречаемости дубликатов миноров

Из приведенных результатов в Таблице 6 можно сделать вывод - с увеличением размера матрицы, возрастает число встречаемости дубликатов миноров. Данные результаты позволяют ожидать снижения сложности проверки свойства MDS у матриц рассмотренного типа (в 20-30 раз).



Заключение

В работе получены следующие результаты:

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

Разработан комплекс программ (в среде Wolfram Mathematica 12) для проверки свойства MDS циклических матриц размеров nЧn, 12?n?16.

Подсчитано точное число различных миноров для циклической матрицы размера 12Ч12 в каждой строке которой 3 единицы и 7 различных элементов, над конечным полем GF(256).

Проведены экспериментальные исследования по оценке частоты встречаемости дубликатов случайно выбранного минора, заданной размерности kЧk, 5?k?11 для матриц размера nЧn, 13?n?16 (задаваемых соответствующими шаблонами).



Обзор литературы

J. Guo, T. Peyrin, and A. Poschmann The PHOTON Family of Lightweight Hash Functions, In CRYPTO, pp. 222-239, Springer, 2011.

Kishan Chand Gupta, Indranil Ghosh Ray On Constructions of MDS Matrices from Companion Matrices for Lightweight Cryptography.

Mahdi Sajadieh, Mohammad Dakhilalian Hamid Mala, Behnaz Omoomi, On construction of involutory MDS matrices from Vandermonde Matrices in G F(2q).

A.M. Youssef, S. Mister and S.E. Tavares On the Design of Linear Transformations for Substitution Permutation Encryption Networks, Department Of Electrical and Computer Engineering, Queen's University, Kingston, Ontario, Canada.

Lijing Zhou, Licheng Wang, Yiru Sun On The Efficient Construction of Lightweight MDS Matrices.

Thorsten Kranz, Gregor Leander, Ko Stoffelen, and Friedrich Wiemer, Shorter linear straight-line programs for MDS matrices. IACR Trans. Symm. Cryptol., 2017(4):188-211, 2017.

Sйbastien Duval, Gaлtan Leurent MDS Matrices with Lightweight Circuits.

Нестеренко А. Ю., Лось А. Б., Рожков М. И. Криптографические методы защиты информации: учебник для академического бакалавриата. - М.: Юрайт. - 2016. - 474 c.

Pascal Junod, Serge Vaudenay Perfect Diffusion Primitives for Block Ciphers Building Efficient MDS Matrices.

Малахов С. С. Разработка методов построения MDS матриц специального вида над конечным полем. - М.: МИЭМ НИУ ВШЭ. -2018. - 52 с.

Serge Vaudenay On the Need for Multipermutations: Cryptanalysis of MD4 and SAFER.

Анашкин А. В. Полное описание одного класса MDS-матриц над конечным полем характеристики 2. - М.: Математические вопросы криптографии, т. 8, выпуск 4 - 2017. - 5-28 с.

Belov A.V., Los A.B., Rozhkov M.I. “Some approaches to construct MDS matrices over a finite field”, Communication on Applied Mathematics and Computation, 2017, Vol. 31, No. 2, pp. 143-152.

A.V. Belov, A.B. Los, and M.I. Rozhkov. “Some Classes of the MDS Matrices Over a Finite Field”, Lobachevskii Journal of Mathematics, 2017, Vol. 38, No. 5, pp. 880-883.

Freye P, Diaz N, Diaz R, Perez C Random Generation of MDS matrices.

Tr?n Th? Lэ?ng, Journal of Science and Technology on Information security S? 2.CS (03) 2016 10 Constructing effectively MDS and recursive MDS matrices by Reed-Solomon codes.

Shannon C. E. Communication Theory of Secrecy Systems // Bell System Technical Journal. -- 1949. -- Vol. 28, Issue 4. -- P. 656--715.

J. Daemen, L. Knudsen, and V. Rijmen “The block cipher square”, in Fast Software Encryption (FSE' 97). Springer, pp. 149-165, 1997.

F.J. MacWilliams, N.J.A. Sloane “The theory of error-correcting codes”. Elsevier, 1977.

Muhammad Yasir Malik and Jong-Seon No Dynamic MDS Matrices for Substantial Cryptographic Strength



Приложение

M12=({

{1, c, 1, a, a, 1, b, d, e, f, b, g},

{g, 1, c, 1, a, a, 1, b, d, e, f, b},

{b, g, 1, c, 1, a, a, 1, b, d, e, f},

{f, b, g, 1, c, 1, a, a, 1, b, d, e},

{e, f, b, g, 1, c, 1, a, a, 1, b, d},

{d, e, f, b, g, 1, c, 1, a, a, 1, b},

{b, d, e, f, b, g, 1, c, 1, a, a, 1},

{1, b, d, e, f, b, g, 1, c, 1, a, a},

{a, 1, b, d, e, f, b, g, 1, c, 1, a},

{a, a, 1, b, d, e, f, b, g, 1, c, 1},

{1, a, a, 1, b, d, e, f, b, g, 1, c},

{c, 1, a, a, 1, b, d, e, f, b, g, 1}

});

M13 = ({

{1, 1, a, 1, b, c, d, e, f, 1, g, h, k},

{k, 1, 1, a, 1, b, c, d, e, f, 1, g, h},

{h, k, 1, 1, a, 1, b, c, d, e, f, 1, g},

{g, h, k, 1, 1, a, 1, b, c, d, e, f, 1},

{1, g, h, k, 1, 1, a, 1, b, c, d, e, f},

{f, 1, g, h, k, 1, 1, a, 1, b, c, d, e},

{e, f, 1, g, h, k, 1, 1, a, 1, b, c, d},

{d, e, f, 1, g, h, k, 1, 1, a, 1, b, c},

{c, d, e, f, 1, g, h, k, 1, 1, a, 1, b},

{b, c, d, e, f, 1, g, h, k, 1, 1, a, 1},

{1, b, c, d, e, f, 1, g, h, k, 1, 1, a},

{a, 1, b, c, d, e, f, 1, g, h, k, 1, 1},

{1, a, 1, b, c, d, e, f, 1, g, h, k, 1}

});

M14 = ({

{1, 1, a, 1, b, c, a, d, e, b, f, c, g, h},

{h, 1, 1, a, 1, b, c, a, d, e, b, f, c, g},

{g, h, 1, 1, a, 1, b, c, a, d, e, b, f, c},

{c, g, h, 1, 1, a, 1, b, c, a, d, e, b, f},

{f, c, g, h, 1, 1, a, 1, b, c, a, d, e, b},

{b, f, c, g, h, 1, 1, a, 1, b, c, a, d, e},

{e, b, f, c, g, h, 1, 1, a, 1, b, c, a, d},

{d, e, b, f, c, g, h, 1, 1, a, 1, b, c, a},

{a, d, e, b, f, c, g, h, 1, 1, a, 1, b, c},

{c, a, d, e, b, f, c, g, h, 1, 1, a, 1, b},

{b, c, a, d, e, b, f, c, g, h, 1, 1, a, 1},

{1, b, c, a, d, e, b, f, c, g, h, 1, 1, a},

{a, 1, b, c, a, d, e, b, f, c, g, h, 1, 1},

{1, a, 1, b, c, a, d, e, b, f, c, g, h, 1}

});

M15=({

{1, 1, a, 1, b, c, d, 1, e, f, g, h, a, i, j},

{j, 1, 1, a, 1, b, c, d, 1, e, f, g, h, a, i},

{i, j, 1, 1, a, 1, b, c, d, 1, e, f, g, h, a},

{a, i, j, 1, 1, a, 1, b, c, d, 1, e, f, g, h},

{h, a, i, j, 1, 1, a, 1, b, c, d, 1, e, f, g},

{g, h, a, i, j, 1, 1, a, 1, b, c, d, 1, e, f},

{f, g, h, a, i, j, 1, 1, a, 1, b, c, d, 1, e},

{e, f, g, h, a, i, j, 1, 1, a, 1, b, c, d, 1},

{1, e, f, g, h, a, i, j, 1, 1, a, 1, b, c, d},

{d, 1, e, f, g, h, a, i, j, 1, 1, a, 1, b, c},

{c, d, 1, e, f, g, h, a, i, j, 1, 1, a, 1, b},

{b, c, d, 1, e, f, g, h, a, i, j, 1, 1, a, 1},

{1, b, c, d, 1, e, f, g, h, a, i, j, 1, 1, a},

{a, 1, b, c, d, 1, e, f, g, h, a, i, j, 1, 1},

{1, a, 1, b, c, d, 1, e, f, g, h, a, i, j, 1}

});

M16=({

{1, 1, a, 1, b, c, d, 1, e, f, g, h, j, k, m, t},

{t, 1, 1, a, 1, b, c, d, 1, e, f, g, h, j, k, m},

{m, t, 1, 1, a, 1, b, c, d, 1, e, f, g, h, j, k},

{k, m, t, 1, 1, a, 1, b, c, d, 1, e, f, g, h, j},

{j, k, m, t, 1, 1, a, 1, b, c, d, 1, e, f, g, h},

{h, j, k, m, t, 1, 1, a, 1, b, c, d, 1, e, f, g},

{g, h, j, k, m, t, 1, 1, a, 1, b, c, d, 1, e, f},

{f, g, h, j, k, m, t, 1, 1, a, 1, b, c, d, 1, e},

{e, f, g, h, j, k, m, t, 1, 1, a, 1, b, c, d, 1},

{1, e, f, g, h, j, k, m, t, 1, 1, a, 1, b, c, d},

{d, 1, e, f, g, h, j, k, m, t, 1, 1, a, 1, b, c},

{c, d, 1, e, f, g, h, j, k, m, t, 1, 1, a, 1, b},

{b, c, d, 1, e, f, g, h, j, k, m, t, 1, 1, a, 1},

{1, b, c, d, 1, e, f, g, h, j, k, m, t, 1, 1, a},

{a, 1, b, c, d, 1, e, f, g, h, j, k, m, t, 1, 1},

{1, a, 1, b, c, d, 1, e, f, g, h, j, k, m, t, 1}

});

G=GF[2, {1, 0, 1, 1, 1, 0, 0, 0, 1}]

SetFieldFormat[G, FormatType->FunctionOfCode[g]]

irpol=FieldIrreducible[G, x]

Размещено на Allbest.ru

...