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

Инвариантные подпространства матриц с нетривиальной группой автоморфизмов

Д. А. Буров, С. В. Костарев


Аннотация: Зададим действие $S_n \times S_n$ на множестве квадратных матриц порядка $n$ над $\mathbb{F}_{2^r}$: $A^{(g_1,g_2)} = \left(a_{g_1(i), g_2(j)}\right)$ для $A \in \left(\mathbb{F}_{2^r}\right)_{n,n}$, $(g_1,g_2) \in S_n \times S_n$. Группой автоморфизмов $\mathrm{Aut}(A)$ матрицы $A$ назовем множество всех таких $(g_1,g_2) \in S_n \times S_n$, что ${A^{(g_1,g_2)} = A}$. Известно, что если $A$ — максимально рассеивающая (МР-, MDS-) матрица, то $\mathrm{Aut}(A) = (G,\sigma) = \{(g,\sigma(g)): g\in G\}$, $G < S_n$, $\sigma$ — сопряжение в $S_n$. Для разбиения $\{1,\ldots,n\} = \Gamma_1\cup \ldots \cup \Gamma_k$ определим векторы $e_{\Gamma_i} = \sum\limits_{s \in \Gamma_i}e_s$, $i=1,\ldots,k$, где $e_j = (0,\ldots,0,\underset{j}{1},0,\ldots,0) \in \mathbb{F}_{2^r}^n$, $j=1,\ldots,n$. Если $\{1,\ldots,n\} = \Gamma_1\cup\ldots\cup\Gamma_k$ — разбиение на орбиты группы $H < S_n$, то подпространства $W_H = \langle e_{\Gamma_1},\ldots,e_{\Gamma_k}\rangle < \mathbb{F}_{2^r}^n$ будем называть $H$-орбитальными. Доказано, что любое $H$-орбитальное подпространство инвариантно относительно матрицы с группой автоморфизмов $(G,1)$, если $H < G < S_n$. $H$-инвариантные подпространства могут быть использованы в методе инвариантных смежных классов криптоанализа алгоритмов блочного шифрования, поскольку являются инвариантными относительно параллельного действия одинаковых подстановок на координатах, использующегося в ряде алгоритмов блочного шифрования. Описаны подпространства пространства $\mathbb{F}_{2^r}^6$, инвариантные относительно максимально рассеивающего циркулянта порядка $6$ над $\mathbb{F}_{2^r}$ и параллельного действия одинаковых подстановок на координатах.

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

УДК: 519.7

DOI: 10.17223/2226308X/18/3