Я утверждаю, что для большого класса функций раунда блочного шифра, включая функцию раунда AES, аффинная структура в пространстве ключей раунда, а также в пространстве блоков определяется функцией раунда блочного шифра. Следовательно, единственными возможными автоморфизмами для AES и связанных с ним блочных шифров являются аффинные преобразования.
Случай, когда $К$ это группа, действующая на $Х$
Предположим, что $К$ это группа, действующая на съемочной площадке $Х$ где для каждого $k\in K\setminus\{e\}$, существует некоторое $х\в х$ с $k\cdot x\neq x$. Предположим, что $F_{k}(x)=F(k,x)=k\cdot P(x)$ для некоторой перестановки $P:X\стрелка вправо X$.
Обратите внимание, что $F_{k}^{-1}(x)=P^{-1}(k^{-1}\cdot x)$. Мы наблюдаем, что
$$F_{j}(F_{k}^{-1}(x))=j\cdot P(F_{k}^{-1}(x))=j\cdot P(P^{-1 }(к^{-1}\cdot х))
=j\cdot k^{-1}\cdot x.$$
В частности, отображение из $K^{4}\раз X$ к $Х$ определяется $(i,j,k,l,x)\mapsto i\cdot j^{-1}\cdot k\cdot l^{-1}\cdot x$ является определимым. Теперь заметьте, что $ij^{-1}кл^{-1}=е$ если и только если $x=i\cdot j^{-1}\cdot k\cdot l^{-1}\cdot x$ для всех $x\в X.$ Поэтому совокупность всех $(ш,х,у,г)\в К^{4}$ куда $wx^{-1}yz^{-1}=e$ определяется через функцию $F$. Следовательно, функция $K^{3}\rightarrow K,(x,y,z)\mapstoxy^{-1}z$ определяется через функцию $F$. Операция $K^{3}\rightarrow K,(x,y,z)\mapstoxy^{-1}z$ называется операцией с кучей, и операцию с кучей можно рассматривать как операцию, из которой вы можете восстановить большую часть информации из группы, но вы определяете, какой элемент группы был идентификатором из операции с кучей; с другой стороны, вы можете легко восстановить групповую операцию из операции с кучей вместе с идентификатором группы. Операцию с кучей следует рассматривать как неабелевское обобщение понятия аффинного пространства.
Предложение: $(\фи,\пси)$ является автоморфизмом функции раунда $F$. Тогда пусть $а=\фи(е)$, и разреши $L:K\стрелка вправо K$ быть отображением, определенным $L(к)=а^{-1}\фи(к)$. затем $L$ является групповым автоморфизмом.
Доказательство: заметьте, что $\фи(к)=aL(к)$ для каждого $к\в К$. Следовательно,
$$L(h^{-1}k)=a^{-1}\phi(h^{-1}k)=a^{-1}\phi(eh^{-1}k)=a ^{-1}\фи(е)\фи(ч)^{-1}\фи(к)$$
$$=a^{-1}a\phi(h)^{-1}\phi(k)=\phi(h)^{-1}\phi(k)=L(h)^{-1 }a^{-1}aL(k)=L(h)^{-1}L(k).$$
Таким образом, отображение $L$ является групповым гомоморфизмом. С $\фи$ биективен, $L$ также является биективным. КЭД
Теперь определите $М(к)=\фи(к)а^{-1}$. затем $ млн $ является автоморфизмом, где
$\фи(к)=М(к)а$ за $к\в К$. Следовательно,
$$\psi(j\cdot k^{-1}\cdot x)=\phi(j)\phi(k)^{-1}\psi(x)=M(j)aa^{-1} M(k)\psi(x)=M(jk)\psi(x).$$ Следовательно,
$\psi(k\cdot x)=M(k)\psi(x)$ для каждого $к\в К$.
Случай, когда $К$ и $Х$ являются изоморфными группами, а групповое действие — умножение слева
Предположим теперь, что $К,Х$ группы и $\iota:K\стрелка вправо X$ является изоморфизмом. Тогда предположим, что действие $К$ на $Х$ определяется $k\cdot x=\iota(k)x$ для каждого $k\in K,x\in X$. затем $F_{k}(x)=F(k,x)=k\cdot P(x)=\iota(k)P(x)$ для каждого $k\in K,x\in X$.
У нас есть $\psi(\iota(k)x)=\iota(M(k))\psi(x)$ для всех $к,х$. В частности, если $b=\psi(е)$, тогда $$\psi(\iota(k))=\psi(\iota(k)e)=\iota(M(k))\psi(e)=\iota(M(k))b.$$ Сказано иначе, если $х=\йота(к)$, тогда $\psi(x)=\iota(M(k))b=\iota(M(\iota^{-1}(x))b$. В оставшейся части этого поста мы напишем $M'=\iota\circ M\iota^{-1}$ и разреши $L'=\iota\circ L\circ\iota^{-1}$.
На самом деле, вы можете легко определить операцию $X^{3}\rightarrow X,(x,y,z)\mapsto xy^{-1}z$ от операции $K^{2}\times X\стрелка вправо X(j,k,x)\mapsto\iota(jk^{-1})x$.
Спряжение по P
В случае, когда $К$ просто воздействует на $Х$ но где $Х$ не обязательно группа, у нас есть $$F_{j}^{-1}(F_{k}(x))=P^{-1}(j^{-1}\cdot F_{k}(x))=P^{-1 }(j^{-1}\cdot k\cdot P(x))=P^{-1}(j^{-1}k\cdot P(x)).$$
Теперь предположим, что мы находимся в случае, когда $k\cdot x=\iota(k)x$ и $\iota:K\стрелка вправо X$ является групповым изоморфизмом. затем
Обратите внимание, что $F_{j}^{-1}F_{k}(x)=P^{-1}[\iota(j^{-1}k)\cdot P(x)].$
Предположим, что $F_{j}^{-1}F_{k}(u)=v$. затем $F_{j}^{-1}F_{k}(x)=P^{-1}[P(v)P(u)^{-1}P(x)]$, поэтому сопряженная операция кучи
$(x,y,z)\mapsto P^{-1}[P(x)P(y)^{-1}P(z)]$ также определяется из $F$.
Следовательно, отображения $\psi,P\psi P^{-1}$ оба должны быть автоморфизмами кучи.
СП сети
Предположим, что $K=U^{n},X=V^{n}$ куда $U,V$ являются группами, и $I:U\стрелка вправо V$ является изоморфизмом. Предположим, что $\iota:K\стрелка вправо X$ является изоморфизмом, определяемым, полагая $\iota((r_{k})_{k})=(I(r_{k}))_{k}$.
Позволять $s:V\стрелка вправо V$ быть биекцией. Определить сопоставление $S:V\стрелка вправо V$ позволив $S((v_{k})_{k})=(s(v_{k}))_{k}$. Позволять $\Гамма:X\стрелка вправо X$ быть автоморфизмом кучи.
Предположим, что $P=\Гамма\цирк S$. Как и прежде, мы предполагаем, что $F_{k}(x)=\iota(k)P(x)$.
Обратите внимание, что $P^{-1}[P(x)P(y)^{-1}P(z)]=S^{-1}[S(x)S(y)^{-1}S(z )]$, поэтому отображения $\psi,S\psi S^{-1}$ оба должны быть автоморфизмами кучи.
Позволять $\mathcal{V}=(V,\Omega,\mho)$ — алгебраическая структура, где $\Омега,\мхо$ являются тернарными операциями, определенными, позволяя
$\Omega(x,y,z)=xy^{-1}z,\mho(x,y,z)=s^{-1}[s(x)s(y)^{-1}s (г)]$. затем $\psi$ должен быть автоморфизмом $\mathcal{V}^{n}$. Ограничим теперь возможности автоморфизмов $\psi$ когда функция $s$ удовлетворяет хорошим свойствам.
Мы говорим, что $s$ является косожестким, если всякий раз
$E:\mathcal{V}\times\mathcal{V}\стрелка вправо\mathcal{V}$ является эндоморфизмом,
отображение $x\mapsto E(e,x)$ является постоянным отображением или отображением
$x\mapsto E(x,e)$ является постоянным отображением.
Теорема: если отображение $s$ косожёстко, то существует биекция $W:\{0,\dots,n-1\}\стрелка вправо\{0,\dots,n-1\}$ вместе с автоморфизмами
$\psi_{0},\dots,\psi_{n-1}$ из $\mathcal{V}$ такой, что
$\psi((x_{k})_{k=0}^{n-1})=(\psi_{j}(x_{W(j)}))_{j=0}^{n- 1}$ в любое время $x_{0},\dots,x_{n-1}\in V$.
Доказательство:
Определить сопоставление $\text{in}_{j}:V\стрелка вправо V^{n}$ позволив
$\text{in}_{j}(r)=(r_{k})_{k=0}^{n-1}$ позволив $r=r_{j}$ и $r_{k}=e$ в любое время $k\neq j$. Определить сопоставление $\text{jn}_{j}:V^{n}\rightarrow V$ позволив $\text{jn}_{j}(r_{k})_{k=0}^{n-1}=r_{j}.$
Теперь заметьте, что $\text{jn}_{j}\circ\psi\circ\text{in}_{i}:\mathcal{V}\rightarrow\mathcal{V}$ является эндоморфизмом для всех $я,j$, так что давайте
$\psi_{i,j}=\text{jn}_{j}\circ\psi\circ\text{in}_{i}$. С $\mathcal{V}^{n}$ порождается подалгебрами вида
$\text{in}_{i}[\mathcal{V}]$, заметим, что автоморфизм $(\тета,\psi)$ полностью определяется матрицей эндоморфизмов $(\psi_{i,j})_{i,j}$ из $\mathcal{V}$.
Предположим, что $s$ является косожестким. Предполагать $i\neq j$. Позволять
$\text{in}_{i,j}:\mathcal{V}^{2}\rightarrow\mathcal{V}^{n}$ — отображение, определенное, если $\text{in}_{i,j}(u,v)=(v_{k})_{k}$ именно когда $v_{i}=u,v_{j}=v$, и $v_{к}=е$ в любое время $k\not\in\{i,j\}$.
Предполагать $i\neq j$ и $E=\text{jn}_{k}\circ\psi\circ\text{in}_{i,j}$.
затем $Е$ является гомоморфизмом из $\mathcal{V}^{2}$ к $\mathcal{V}.$
Более того, $E(x,e)=\psi_{i,k}(x),E(e,x)=\psi_{j,k}(x)$, поэтому отображение $\psi_{i,k}$ является постоянным отображением или отображением $\psi_{j,k}$ является постоянным отображением.
Для каждого $n$, есть $n+1$-арный термин $t$ на языке $\mathcal{V}$ такой, что $t(x_{1},\dots,x_{n},e)=x_{1}\dots x_{n}$ и вообще это $$t(x_{1},\dots,x_{n},a)=x_{1}a^{-1}x_{2}\dots x_{n-1}a^{-1}x_{ п}.$$
У нас есть
$$(x_{k})_{k=0}^{n-1}=t(\text{in}_{0}(x_{0}),\dots,\text{in}_{n -1}(x_{k}),е),$$ так
$$\text{jn}_{j}\psi((x_{k})_{k=0}^{n-1})=t(\text{jn}_{j}\psi(\text {in}_{0}(x_{0})),\dots,\text{jn}_{j}\psi(\text{in}_{n-1}(x_{k})),\ текст{jn}_{j}\psi(e)).$$ Следовательно, есть некоторые $я$ куда
отображение $\text{jn}_{j}\psi\text{in}_{i'}$ является постоянной функцией всякий раз, когда $i'\neq i.$ Следовательно, существует функция $W:\{0,\dots,n-1\}\стрелка вправо\{0,\dots,n-1\}$ где для всех $j$, есть некоторый эндоморфизм
$\psi_{j}:\mathcal{V}\стрелка вправо\mathcal{V}$ с
$\text{jn}_{j}\psi((x_{k})_{k=0}^{n-1})=\psi_{j}(x_{W(j)})$.
Таким образом, у нас есть $\psi((x_{k})_{k=0}^{n-1})=(\psi_{j}(x_{W(j)}))_{j=0}^{n- 1}$. Поскольку отображение $\psi$ является автоморфизмом, а поскольку $\mathcal{V}$ конечно, мы знаем, что каждое отображение $\psi_{j}$ также должно быть автоморфизмом и отображение $W$ должно быть биекцией.
КЭД
Вышеупомянутая теорема утверждает, что всякий раз, когда $s$ косожестка, группа автоморфизмов $F$ поэтому является подгруппой сплетения $\text{Авт}(\mathcal{V})$ с симметричной группой $S_{n}$.
Мы также можем гарантировать, что группа автоморфизмов $F$ является разумно ручным при различных предположениях о S-блоках.
Позволять $Ч$ быть группой перестановок $Х$ порождается всеми перестановками вида $F_{j}\circ F_{k}^{-1},F_{j}^{-1}\circ F_{k}$. Теперь мы покажем, что при разумных предположениях разложение $Ч$ имеет внутреннее прямое произведение прямо неразложимых групп.
Из ослабленной версии теоремы Крулля-Шмидта мы знаем, что если $G_{1},\dots,G_{\alpha},H_{1},\dots,H_{\beta}$ являются конечными непосредственно неразложимыми группами, и
$G_{1}\times\dots\times G_{\alpha}\simeq H_{1}\times\dots\times H_{\beta}$, тогда $\альфа=\бета$, и есть биекция $\zeta:\{1,\dots,\alpha\}\стрелка вправо\{1,\dots,\beta\}$ куда $G_{i}\simeq H _{\zeta(i)}$ за $1\leq я\leq\альфа$.
Если $j\в U$, тогда пусть $s_{j}$ быть перестановкой $В$ определяется, позволяя
$s_{j}(v)=I(j)s(v)$ в любое время $в\в V$. Позволять $Ч^{-}$ быть группой перестановок $В$ генерируются отображениями $s_{j}\circ s_{k}^{-1},s_{j}^{-1}\circ s_{k}$.
Лемма. Предположим, что для $1\leq i\leq n$, $\Delta_{i}$ является конечной неабелевой группой с $|\Delta_{i}|>1$ и где если $A,B\subseteq\Delta_{i}$ такие подгруппы, что $аб=ба$ в любое время $а\в А,б\в В$ и где $\Delta_{i}=AB$, то либо $|А|=1$ или же $|В|=1.$ Тогда всякий раз, когда $\phi:\Delta_{1}\times\dots\times\Delta_{n}\стрелка вправо\Delta_{1}\times\dots\times\Delta_{n}$ является автоморфизмом, существует перестановка $\ро$ из $\{1,\dots,n\}$ и изоморфизмы $\phi_{i}:\Delta_{\rho(i)}\стрелка вправо\Delta_{i}$ куда
$\phi(x_{1},\dots,x_{n})=(\phi_{1}(x_{\rho(1)}),\dots,\phi_{n}(x_{\rho(n )))$.
Доказательство: Заметим, что если $A_{1},\dots,A_{r}$ являются подгруппами $\Delta_{i}$ и $аб=ба$ в любое время $a\in A_{i},b\in A_{j},i\neq j$ и $\Delta_{i}=A_{1}\dots A_{r}$, то существует $я$ куда $\Delta_{i}=A_{i}$ и где
$|A_{j}|=1$ в любое время $j\neq i$. Это наблюдение можно установить индукцией по $г$.
За $i,j\in\{1,\dots,n\}$, позволять $\pi_{j}:\Delta_{1}\times\dots\times\Delta_{n}\стрелка вправо\Delta_{j}$ — проекционное отображение, и пусть $\iota_{i}:\Delta_{i}\стрелка вправо\Delta_{1}\times\dots\times\Delta_{n}$ — отображение включения. Тогда всякий раз, когда $i_{1}\neq i_{2}$ и
$a\in\pi_{j}[\phi[\iota_{i_{1}}[\Delta_{i_{1}}}]]],b\in\pi_{j}[\phi[\iota_{i_ {2}}[\Delta_{i_{2}}]]]$, у нас есть $аб=ба$. С
$\Delta_{j}$ порождается подгруппами $\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]$, мы знаем, что для всех $j$, существует не более одного $я$ куда $|\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]|>1$ и для таких $я$, у нас есть
$\Delta_{j}=\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]$. Другими словами, существует функция $\rho:\{1,\dots,n\}\стрелка вправо\{1,\dots,n\}$ куда
$\pi_{j}[\phi[\iota_{\rho(j)}[\Delta_{\rho(j)}]]]=\Delta_{j}$ для всех $j$ но где $|\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]|=1$ в любое время $\rho(j)\neq i$.
Таким образом, у нас есть
$\phi(x_{1},\dots,x_{n})=(\pi_{1}\phi\iota_{\rho(1)}(x_{\rho(1)}),\dots,\ pi_ {n} \ phi \ iota _ {\ rho (n)} (x _ {\ rho (n)})). $
С $\фи$ является изоморфизмом, отображение $\ро$ является биекцией, и
$\pi_{j}\phi\iota_{\rho(j)}$ является изоморфизмом от $\Delta_{\rho(j)}$ к $\Delta_{j}$ для всех $j$.
КЭД
Лемма. Предположим, что $G$ группа, факторизуемая как внутреннее прямое произведение подгрупп $\Delta_{1},\dots,\Delta_{m}$. Кроме того, предположим, что для всех $я$, если $А,Б$ являются подгруппами $\Delta_{i}$ с
$аб=ба$ для каждого $а\в А,б\в В$ и $\Delta_{i}=AB$. Тогда, если $\Delta_{1}^{\sharp},\dots,\Delta_{n}^{\sharp}$ является еще одной факторизацией $G$ как внутреннее прямое произведение подгрупп, то $м=n$, и есть некоторая перестановка $\ро$ из $\{1,\dots,м\}$ куда $\Delta_{i}=\Delta_{\rho(i)}^{\sharp}$ для всех $я$.
Доказательство: по теореме Крулля-Шмидта мы знаем, что $м=n$, и есть перестановка $\ро$ из $\{1,\dots,м\}$ куда $\Delta_{i}\simeq \Delta_{\rho(i)}^{\sharp}$ для всех $я$. Следовательно, существует некоторый автоморфизм $\фи$ из $G$ куда $\фи$ ограничивается отображением изоморфизма $\Delta_{i}$ на $\Delta_{\rho(i)}^{\sharp}$ для всех $я$. Однако по приведенной выше лемме мы знаем, что существует некоторая перестановка $f$ из $\{1,\dots,м\}$ куда $\phi[\Delta_{i}]=\Delta_{f(i)}$ для всех $я$. Следовательно,
$\Delta_{\rho(i)}^{\sharp}=\Delta_{f(i)}$ для всех $я$. КЭД
Теорема: Предположим, что всякий раз, когда $А,Б$ являются подгруппами $Ч^{-}$ с
$аб=ба$ за $а\в А,б\в В$, либо $|А|=1$ или же $|В|=1$. Тогда, если $(\фи,\пси)$ является автоморфизмом $F$, то существует биекция $W:\{0,\dots,n-1\}\стрелка вправо\{0,\dots,n-1\}$ вместе с автоморфизмами
$\psi_{0},\dots,\psi_{n-1}$ из $\mathcal{V}$ такой, что
$\psi(x_{0},\dots,x_{n-1})=(\psi_{0}(x_{W(0)}),\dots,\psi_{n-1}(x_{W (n-1)))$ в любое время $x_{0},\dots,x_{n-1}\in V.$
Доказательство. Предположим, что $(\фи,\пси)$ является автоморфизмом $В$. затем $\psi$ сохраняет группу $Ч$ в том смысле, что $H=\psi H\psi^{-1}$. Следовательно, если $Ч$ факторизуется как внутренний прямой продукт подгрупп $H_{0},\dots,H_{n-1}$, то группа $Ч$ определяется в $(Ф,К,Х)$, а множество подгрупп $\{H_{0},\dots,H_{n-1}\}$ также определяется в $(Ф,К,Х)$.
Следовательно, существует биекция $\rho:\{0,\dots,n-1\}\стрелка вправо\{0,\dots,n-1\}$ такой, что $H_{\rho(i)}=\psi H_{i}\psi^{-1}$ для всех $я$. Таким образом, у нас есть $ H _ {\ rho (i)} \ psi = \ psi H_ {i} $.
Предположим, что $\pi_{0},\dots,\pi_{n-1}:X\стрелка вправо V$ являются проекционными функциями. Предположим, что $\шляпа{Н}_{я}$ это группа, созданная всеми $H_{j}$такой, что $i\neq j$.
затем $\pi_{i}(x)=\pi_{i}(y)$ если и только если $ч(х)=у$ для некоторых $h\in\шляпа{H}_{i}$ если и только если $\psi^{-1}h'\psi(x)=y$ для некоторых $ ч '\ в \ шляпа {Н} _ {\ ро (я)} $ если и только если $h'\psi(x)=\psi(y)$ для некоторых
$h'\in\psi\шляпа{H}_{i}\psi^{-1}=\шляпа{H}_{\rho(i)}$ если и только если
$\pi_{\rho(i)}\psi(x)=\pi_{\rho(i)}(\psi(y))$.
Следовательно, $\psi(x_{0},\dots,x_{n-1})=(\psi_{0}(x_{\rho^{-1}(0)}),\dots,\psi_{n- 1}(x_{\rho^{-1}(n-1)})$ для некоторых биекций
$\psi_{0},\dots,\psi_{n-1}$. Кроме того, биекции $\psi_{0},\dots,\psi_{n-1}$ должны быть автоморфизмами $\mathcal{V}$.
КЭД
Вышеупомянутая теорема применима, когда $Ч^{-}$ является либо знакопеременной, либо симметрической группой на множестве более чем $4$ элементы. В частности, приведенная выше теорема применима к блочному шифру AES. Доказательство того, что для AES группа $Ч^{-}$ является чередующейся группой, можно найти в статье Ральфа Вернсдорфа, которая доказывает, что циклические перестановки блочного шифра AES генерируют чередующуюся группу всех перестановок $\{1,\dots,2^{128}\}.$
