Немалую часть структуры на самом деле можно определить в терминах функции раунда блочного шифра, и из этой структуры можно создать инварианты функции раунда блочного шифра, которые измеряют криптографическую безопасность.
Часть этого ответа по существу такая же, как мой предыдущий ответ здесь, поэтому в этом случае мы опускаем доказательства результатов.
Если $G,H$ являются группами, то мы говорим, что функция $\фи:G\стрелка вправо H$ является гомоморфизмом кучи, если существует гомоморфизм групп $\psi:G\стрелка вправо H$ вместе с $б\в Н$ куда $\фи(г)=b\пси(г)$ для всех $б\в Б.$ Эквивалентно, отображение $\фи:G\стрелка вправо H$ является гомоморфизмом кучи тогда и только тогда, когда
$\phi(xy^{-1}z)=\phi(x)\phi(y)^{-1}\phi(z)$ в любое время $х,у,г\в G$. Биективный гомоморфизм кучи называется автоморфизмом кучи.
Для этого поста пусть $U_{0},\dots,U_{n-1},V_{0},\dots,V_{n-1}$ быть группами. Предположим, что $I_{i}:U_{i}\rightarrow V_{i}$ является групповым изоморфизмом всякий раз, когда $0\leq i<n$. Позволять $K=U_{0}\times\dots\times U_{n-1},X=V_{0}\times\dots\times V_{n-1}$.
Затем определим групповой изоморфизм $\iota:K\стрелка вправо X$ позволив
$\iota(u_{0},\dots,u_{n-1})=(I_{0}(u_{0}),\dots,I_{n-1}(u_{n-1})) $.
Если $0\leq i<n$, тогда пусть $s_{i}:V_{i}\rightarrow V_{i}$ быть произвольной биекцией.
Определить сопоставление $S:V_{0}\times\dots\times V_{n-1}\стрелка вправо V_{0}\times\dots\times V_{n-1}$ позволив $S(v_{0},\dots,v_{n-1})=(s_{0}(v_{0}),\dots,s_{n-1}(v_{n-1}))$.
Позволять $\Гамма:X\стрелка вправо X$ быть автоморфизмом кучи. Позволять $P=\Гамма\цирк S$и определить отображение $F:K\раз X\стрелка вправо X$ позволив
$F(k,x)=\iota(k)P(x)$.
Предложение: Отображения $K^{2}\times X\стрелка вправо X,(j,k,x)\mapsto\iota(jk^{-1})x$ и $X^{3}\rightarrow X,(x,y,z)\mapsto xy^{-1}z$ определимы в первом порядке в $(К,Х,F)$.
Позволять $\pi_{i}:X\стрелка вправо V_{i}$ — гомоморфизм проекционной группы. Позволять $\simeq_{i}$ отношение эквивалентности на $Х$ где мы устанавливаем $x\simeq_{i}y$ если и только если $\pi_{i}(x)=\pi_{i}(y)$. Я утверждаю, что множество отношений эквивалентности $\{\simeq_{0},\dots,\simeq_{n-1}\}$ является более высоким порядком, определяемым в $(К,Х,F)$ при разумных гипотезах о блочном шифре $F$, но для доказательства этого утверждения нам потребуется пройтись по нескольким леммам. Из определимости $\{\simeq_{0},\dots,\simeq_{n-1}\}$, мы можем создать множество инвариантов раундовой функции блочного шифра, которые измеряют нелинейность, а также лавинный эффект.
За $0\leq i<n$, и $j\inU_{i}$, позволять $s_{я}^{j}$ быть перестановкой $V_{я}$ определяется, позволяя $s_{i}^{j}(v)=I_{i}(j)s_{i}(v)$.
Если $0\leq i<n$, тогда пусть $H_{i}$ быть группой всех перестановок $V_{я}$ Сгенерированно с помощью $s_{i}^{j}\circ(s_{i}^{k})^{-1},(s_{i}^{j})^{-1}\circ s_{i}^{ к}$.
Позволять $Ч$ быть группой всех перестановок $Х$ порождается всеми перестановками вида $F_{j}^{-1}\circ F_{k},F_{j}\circ F_{k}^{-1}$. Обратите внимание, что
$F_{j}\circ F_{k}^{-1}(x)=\iota(jk^{-1})(x)$ и $F_{j}^{-1}\circ F_{k}(x)=S^{-1}[\Gamma^{-1}[\iota(j^{-1}k)]S(x )]$. В частности,
$Ч$ порождается перестановками вида $x\mapsto\iota(m)(x)$ наряду с перестановками формы $S^{-1}[\iota(m)S(x)]$. Сказано иначе, $Ч$ порождается перестановками вида
$$(x_{0},\dots,x_{n-1})\mapsto(I_{0}(m_{0})(x_{0}),\dots,I_{n-1}(m_{ п-1})(х_{п-1}))$$ и
$$(x_{0},\dots,x_{n-1})\mapsto(s_{0}^{-1}[I_{0}(m_{0})(s_{0}(x_{n -1}))],\dots,s_{n-1}^{-1}[I_{n-1}(m_{n-1})(s_{n-1}(x_{n-1} )))]).$$
Таким образом, $Ч$ состоит из всех перестановок вида $h_{0}\times\dots\times h_{n-1}$ куда $h_{i}\in H_{i}$ в любое время $0\leq i<n$.
Следовательно $H\simeq H_{0}\times\dots\times H_{n-1}$ как внешний прямой продукт. Мы также можем написать $Ч$ как внутренний прямой продукт $H_{0}^{\sharp},\dots,H_{n-1}^{\sharp}$ куда $H_{i}^{\sharp}$ состоит из всех отображений $ч\в ч$ где если $h_{0},\dots,h_{n-1}$ отображения, где $h(x_{0},\dots,x_{n-1})=(h_{0}(x_{0}),\dots,h_{n-1}(x_{n-1}))$ для всех $x_{0},\dots,x_{n-1}$, тогда
$h_{j}$ является тождественной функцией всякий раз, когда $j\neq i$. затем $H_{i}^{\sharp}\simeq H_{i}$ в любое время $0\leq i<n.$
Мы говорим, что группа $G$ супернеразложим, если всякий раз, когда $А,Б$ являются подгруппами $G$ с $аб=ба$ в любое время $а\в А,б\в В$ и $G=АВ$, тогда $|А|=1$ или же $|В|=1$ (дайте мне знать в комментариях, если вы можете придумать слово получше, чем «супернеразложимый»).
Теорема (Крулль-Шмидт): Предположим, что $G$ — группа, удовлетворяющая условию возрастания цепи и условию убывания цепи на нормальных подгруппах (любая конечная группа удовлетворяет этому свойству). Кроме того, предположим, что $G$ записывается как внутреннее прямое произведение нетривиальных прямо неразложимых подгрупп двумя разными способами, а именно $G=G_{0}\раз\точки\раз G_{n-1}$ и $G=H_{0}\times\dots H_{n-1}$. Тогда существует перестановка $\ро$ из $\{0,\dots,n-1\}$ такой, что
$G_{i}\simeq H _{\rho(i)}$ за $0\leq i<n$ и где
$$G=G_{0}\times\dots\times G_{r}\times H _{\rho(r+1)}\times\dots H_{\rho(n-1)}$$ в любое время $0\leq r\leq n-1$.
Лемма. Предположим, что $G$ является конечной группой. Если $G$ является внутренним прямым произведением супернеразложимых подгрупп, то всякий раз, когда мы факторизуем $G$ как внутренние прямые продукты $G=G_{0}\times\dots\times G_{m-1}$ и $G=H_{0}\раз\точки\раз H_{n-1}$, тогда $м=n$, и есть некоторая перестановка $\rho:\{0,\dots,n-1\}\стрелка вправо\{0,\dots,n-1\}$ куда $H_{i}=G_{\rho(i)}$ за $0\leq i<n$.
Теорема: Существует формула более высокого порядка $\фи$ такое, что если группы $H_{0},\dots,H_{n-1}$ неразложимы, то $(К,Х,F)\модели\фи(г)$ если и только если $z=\{\simeq_{0},\dots,\simeq_{n-1}\}$.
Доказательство. Заметим, что группа $Ч$ является более высоким порядком, определимым в структуре $(К,Х,F)$. Кроме того, группа $Ч$ имеет уникальную факторизацию с точностью до перестановки
$H^{\sharp}_{0}\times\dots\times H^{\sharp}_{n-1}$ на его неразложимые множители. Следовательно, множество всех неразложимых множителей $\{H^{\sharp}_{0},\dots,H^{\sharp}_{n-1}\}$ определяется в $(К,Х,F)$.
Теперь для каждого $я$, позволять $\шляпа{\simeq}_{i}$ — отношение эквивалентности, где мы устанавливаем
$ х \ шляпа {\ simeq} _ {я} у $ если и только если $ч(х)=у$ для некоторых $ ч \ в Н ^ {\ острые} _ {я} $. Позволять
$\simeq_{i}$ отношение эквивалентности на $Х$ Сгенерированно с помощью
$\bigcup\{\шляпа{\simeq}_{j}\mid j\neq i\}$. затем $\{\simeq_{0},\dots,\simeq_{n-1}\}$ определяется из $\{H^{\sharp}_{0},\dots,H^{\sharp}_{n-1}\}$. Таким образом, множество
$\{\simeq_{0},\dots,\simeq_{n-1}\}$ определяется в $(К,Х,F)$. $\квадрат$
Из определимости $\{\simeq_{0},\dots,\simeq_{n-1}\}$, мы можем определить довольно много инвариантов функции раунда блочного шифра.
Если $T_{1},T_{2}$ являются группами, и $f_{i}:T_{i}\rightarrow T_{i}$ за $я\в\{1,2\}$, то мы говорим, что $f_{1},f_{2}$ аффинно эквивалентны, если существуют автоморфизмы кучи $L_{1}:T_{1}\rightarrow T_{2},L_{2}:T_{2}\rightarrow T_{1}$ куда
$f_{2}=L_{1}f_{1}L_{2}$. Мы говорим, что отображение $ млн $ инвариантен относительно аффинной эквивалентности, если $М(ф)=М(г)$ в любое время $ф,г$ аффинно эквивалентны.
Мы говорим, что пара $(к,\Дельта)$ является S-боксификацией, если $\Дельта$ является автоморфизмом кучи, и всякий раз, когда $x\simeq_{i}y$, тогда $\Delta\circ F_{k}(x)\simeq_{i}\Delta\circ F_{k}(y)$. Совокупность всех S-боксов более высокого порядка определима в $(К,Х,F)$. Заметим, что существует S-боксификация, а именно отображение $(е,\гамма^{-1})$. Предположим теперь, что
$(к,\Дельта)$ является S-боксированием. Тогда нетрудно показать, что каждый $\simeq_{i}$ является конгруэнтностью относительно $\Дельта\Гамма^{-1}$. Следовательно $\Delta=E\Гамма^{-1}$ для некоторого автоморфизма кучи $Е$ где каждый $\simeq_{i}$ является конгруэнтностью относительно $Е$. Следовательно, $\Delta\circ F_{k}=E'\circ S$ для некоторого автоморфизма кучи $E'$. Следовательно, фактор-алгебра $(X,\Delta\circ F_{k})/\simeq_{i}$ аффинно эквивалентно $(V_{я},s_{я})$ за $0\leq i<n$. Из этих наблюдений получаем следующий факт.
Факт: если отображение $ млн $ инвариантно относительно аффинной эквивалентности и определимо в логике более высокого порядка, то отображение $М^{+}$ определяется, позволяя
$M^{+}(F)=\{M(s_{0}),\dots,M(s_{n-1})\}$ является более высоким порядком, определимым в структуре $(К,Х,F)$. Следовательно, $М^{+}$ является инвариантным параметром круглой функции.
