Susțin că, pentru o clasă mare de funcții rotunde de criptare bloc, inclusiv funcția rotundă AES, structura afină pe spațiul cheie rotund și, de asemenea, pe spațiul bloc este definibilă din funcția rotundă cu criptare bloc. Prin urmare, singurele automorfisme posibile pentru AES și cifrurile bloc aferente sunt transformările afine.
Cazul când $K$ este un grup care acţionează asupra $X$
Să presupunem că $K$ este un grup care acționează pe platou $X$ unde pentru fiecare $k\în K\setminus\{e\}$, este ceva $x\în X$ cu $k\cdot x\neq x$. Să presupunem că $F_{k}(x)=F(k,x)=k\cdot P(x)$ pentru unele permutări $P:X\săgeată la dreapta X$.
Observă asta $F_{k}^{-1}(x)=P^{-1}(k^{-1}\cdot x)$. Observăm că
$$F_{j}(F_{k}^{-1}(x))=j\cdot P(F_{k}^{-1}(x))=j\cdot P(P^{-1 }(k^{-1}\cdot x))
=j\cdot k^{-1}\cdot x.$$
În special, maparea de la $K^{4}\x$ la $X$ definit de $(i,j,k,l,x)\mapsto i\cdot j^{-1}\cdot k\cdot l^{-1}\cdot x$ este definibil. Acum, observă asta $ij^{-1}kl^{-1}=e$ dacă și numai dacă $x=i\cdot j^{-1}\cdot k\cdot l^{-1}\cdot x$ pentru toți $x\în X.$ Prin urmare, setul tuturor $(w,x,y,z)\în K^{4}$ Unde $wx^{-1}yz^{-1}=e$ este definibilă din punct de vedere al funcției $F$. Prin urmare, funcția $K^{3}\rightarrow K,(x,y,z)\mapsto xy^{-1}z$ este definibilă din punct de vedere al funcției $F$. Operațiunea $K^{3}\rightarrow K,(x,y,z)\mapsto xy^{-1}z$ se numește operație heap, iar operația heap poate fi gândită ca o operație din care puteți recupera majoritatea informațiilor din grup, dar determinați care element al grupului a fost identitatea din operația heap; pe de altă parte, puteți recupera cu ușurință operația de grup din operația heap împreună cu identitatea grupului. Operația heap ar trebui gândită ca o generalizare non-abeliană a noțiunii de spațiu afin.
Propoziție: $(\phi,\psi)$ este un automorfism al funcției rotunde $F$. Apoi lasa $a=\phi(e)$, si lasa $L:K\săgeată la dreapta K$ fi maparea definită de $L(k)=a^{-1}\phi(k)$. Atunci $L$ este un automorfism de grup.
Dovada: Observați asta $\phi(k)=aL(k)$ pentru fiecare $k\în K$. Prin urmare,
$$L(h^{-1}k)=a^{-1}\phi(h^{-1}k)=a^{-1}\phi(eh^{-1}k)=a ^{-1}\phi(e)\phi(h)^{-1}\phi(k)$$
$$=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).$$
Prin urmare, cartografierea $L$ este un homomorfism de grup. De cand $\phi$ este bijectiva, $L$ este de asemenea bijectiva. Q.E.D.
Acum definiți $M(k)=\phi(k)a^{-1}$. Atunci $M$ este un automorfism unde
$\phi(k)=M(k)a$ pentru $k\în K$. Prin urmare,
$$\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).$$ Prin urmare,
$\psi(k\cdot x)=M(k)\psi(x)$ pentru fiecare $k\în K$.
Cazul când $K$ și $X$ sunt grupări izomorfe și acțiunea de grup este înmulțirea stângă
Să presupunem că acum $K,X$ sunt grupuri și $\iota:K\rightarrow X$ este un izomorfism. Atunci să presupunem că acțiunea lui $K$ pe $X$ este definit de $k\cdot x=\iota(k)x$ pentru fiecare $k\în K,x\în X$. Atunci $F_{k}(x)=F(k,x)=k\cdot P(x)=\iota(k)P(x)$ pentru fiecare $k\în K,x\în X$.
Avem $\psi(\iota(k)x)=\iota(M(k))\psi(x)$ pentru toți $k,x$. În special, dacă $b=\psi(e)$, atunci $$\psi(\iota(k))=\psi(\iota(k)e)=\iota(M(k))\psi(e)=\iota(M(k))b.$$ Spus altfel, dacă $x=\iota(k)$, atunci $\psi(x)=\iota(M(k))b=\iota(M(\iota^{-1}(x)))b$. Pentru restul acestei postări, vom scrie $M'=\iota\circ M\iota^{-1}$ si lasa $L'=\iota\circ L\circ\iota^{-1}$.
De fapt, puteți defini cu ușurință operația $X^{3}\rightarrow X,(x,y,z)\mapsto xy^{-1}z$ din operatie $K^{2}\time X\rightarrow X(j,k,x)\mapsto\iota(jk^{-1})x$.
Conjugarea cu P
În cazul în care $K$ pur și simplu acționează asupra $X$ dar unde $X$ nu este neapărat un grup, avem $$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)).$$
Acum, să presupunem că suntem în cazul în care $k\cdot x=\iota(k)x$ și $\iota:K\rightarrow X$ este un izomorfism de grup. Atunci
Observă asta $F_{j}^{-1}F_{k}(x)=P^{-1}[\iota(j^{-1}k)\cdot P(x)].$
Să presupunem că $F_{j}^{-1}F_{k}(u)=v$. Atunci $F_{j}^{-1}F_{k}(x)=P^{-1}[P(v)P(u)^{-1}P(x)]$, deci conjugați operația heap
$(x,y,z)\mapsto P^{-1}[P(x)P(y)^{-1}P(z)]$ este de asemenea definibil din $F$.
Prin urmare, mapările $\psi,P\psi P^{-1}$ trebuie să fie ambele automorfisme heap.
rețele SP
Să presupunem că $K=U^{n},X=V^{n}$ Unde $U,V$ sunt grupuri, și $I:U\rightarrow V$ este un izomorfism. Să presupunem că $\iota:K\rightarrow X$ este izomorfismul definit prin lasare $\iota((r_{k})_{k})=(I(r_{k}))_{k}$.
Lăsa $s:V\săgeată la dreapta V$ fi o bijectie. Definiți o mapare $S:V\săgeată la dreapta V$ prin închiriere $S((v_{k})_{k})=(s(v_{k}))_{k}$. Lăsa $\Gamma:X\rightarrow X$ fi un automorfism heap.
Să presupunem că $P=\Gamma\circ S$. Ca și înainte, presupunem că $F_{k}(x)=\iota(k)P(x)$.
Observă asta $P^{-1}[P(x)P(y)^{-1}P(z)]=S^{-1}[S(x)S(y)^{-1}S(z )]$, deci mapările $\psi,S\psi S^{-1}$ trebuie să fie ambele automorfisme heap.
Lăsa $\mathcal{V}=(V,\Omega,\mho)$ fie structura algebrică unde $\Omega,\mho$ sunt operaţiile ternare definite prin închiriere
$\Omega(x,y,z)=xy^{-1}z,\mho(x,y,z)=s^{-1}[s(x)s(y)^{-1}s (z)]$. Atunci $\psi$ trebuie să fie un automorfism al $\mathcal{V}^{n}$. Vom limita acum posibilitățile pentru automorfisme $\psi$ când funcţia $s$ satisface proprietăți frumoase.
Noi spunem asta $s$ este înclinat-rigid dacă oricând
$E:\mathcal{V}\times\mathcal{V}\rightarrow\mathcal{V}$ este un endomorfism,
cartografierea $x\mapsto E(e,x)$ este o mapare constantă sau maparea
$x\mapsto E(x,e)$ este o mapare constantă.
Teorema: Dacă maparea $s$ este înclinat-rigid, apoi există o bijecție $W:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ alături de automorfisme
$\psi_{0},\dots,\psi_{n-1}$ de $\mathcal{V}$ astfel încât
$\psi((x_{k})_{k=0}^{n-1})=(\psi_{j}(x_{W(j)}))_{j=0}^{n- 1}$ oricând $x_{0},\dots,x_{n-1}\în V$.
Dovada:
Definiți o mapare $\text{in}_{j}:V\rightarrow V^{n}$ prin închiriere
$\text{in}_{j}(r)=(r_{k})_{k=0}^{n-1}$ prin închiriere $r=r_{j}$ și $r_{k}=e$ oricând $k\neq j$. Definiți o mapare $\text{jn}_{j}:V^{n}\rightarrow V$ prin închiriere $\text{jn}_{j}(r_{k})_{k=0}^{n-1}=r_{j}.$
Acum, observă asta $\text{jn}_{j}\circ\psi\circ\text{in}_{i}:\mathcal{V}\rightarrow\mathcal{V}$ este un endomorfism pentru toți $i,j$, asa ca lasa
$\psi_{i,j}=\text{jn}_{j}\circ\psi\circ\text{in}_{i}$. De cand $\mathcal{V}^{n}$ este generat de subalgebrele formei
$\text{in}_{i}[\mathcal{V}]$, observăm că automorfismul $(\theta,\psi)$ este complet determinată de matricea de endomorfisme $(\psi_{i,j})_{i,j}$ de $\mathcal{V}$.
Să presupunem că $s$ este înclinat-rigid. Presupune $i\neq j$. Lăsa
$\text{in}_{i,j}:\mathcal{V}^{2}\rightarrow\mathcal{V}^{n}$ fi maparea definită prin letting $\text{in}_{i,j}(u,v)=(v_{k})_{k}$ exact când $v_{i}=u,v_{j}=v$, și $v_{k}=e$ oricând $k\nu\în\{i,j\}$.
Presupune $i\neq j$ și $E=\text{jn}_{k}\circ\psi\circ\text{in}_{i,j}$.
Atunci $E$ este un homomorfism din $\mathcal{V}^{2}$ la $\mathcal{V}.$
În plus, $E(x,e)=\psi_{i,k}(x),E(e,x)=\psi_{j,k}(x)$, deci maparea $\psi_{i,k}$ este o mapare constantă sau maparea $\psi_{j,k}$ este o mapare constantă.
Pentru fiecare $n$, este un $n+1$termen -ary $t$ în limba de $\mathcal{V}$ astfel încât $t(x_{1},\dots,x_{n},e)=x_{1}\dots x_{n}$ si mai general ca $$t(x_{1},\dots,x_{n},a)=x_{1}a^{-1}x_{2}\dots x_{n-1}a^{-1}x_{ n}.$$
Avem
$$(x_{k})_{k=0}^{n-1}=t(\text{in}_{0}(x_{0}),\dots,\text{in}_{n -1}(x_{k}),e),$$ asa de
$$\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})),\ text{jn}_{j}\psi(e)).$$ Prin urmare, există unele $i$ Unde
cartografierea $\text{jn}_{j}\psi\text{in}_{i'}$ este o funcție constantă oricând $i'\neq i.$ Prin urmare, există o funcție $W:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ unde pentru toti $j$, există un anumit endomorfism
$\psi_{j}:\mathcal{V}\rightarrow\mathcal{V}$ cu
$\text{jn}_{j}\psi((x_{k})_{k=0}^{n-1})=\psi_{j}(x_{W(j)})$.
Prin urmare, avem $\psi((x_{k})_{k=0}^{n-1})=(\psi_{j}(x_{W(j)}))_{j=0}^{n- 1}$. De la cartografiere $\psi$ este un automorfism şi din moment ce $\mathcal{V}$ este finită, știm că fiecare mapare $\psi_{j}$ trebuie să fie și un automorfism și maparea $W$ trebuie să fie o bijecție.
Q.E.D.
Teorema de mai sus afirmă că oricând $s$ este rigidă oblică, grupul automorfismului $F$ este deci un subgrup al produsului coroană de $\text{Aut}(\mathcal{V})$ cu grupul simetric $S_{n}$.
De asemenea, putem garanta că grupul de automorfism al $F$ este rezonabil de îmblânzit în diferite ipoteze despre cutiile S.
Lăsa $H$ fie grupul de permutări ale $X$ generate de toate permutările formei $F_{j}\circ F_{k}^{-1},F_{j}^{-1}\circ F_{k}$. Vom arăta acum că în ipoteze rezonabile, descompunerea lui $H$ are un produs intern direct al grupurilor direct necompuse este unic.
Dintr-o versiune slăbită a teoremei Krull-Schmidt, știm că dacă $G_{1},\dots,G_{\alpha},H_{1},\dots,H_{\beta}$ sunt grupuri finite direct indecompuse și
$G_{1}\times\dots\times G_{\alpha}\simeq H_{1}\times\dots\times H_{\beta}$, atunci $\alpha=\beta$, și există o bijecție $\zeta:\{1,\dots,\alpha\}\rightarrow\{1,\dots,\beta\}$ Unde $G_{i}\simeq H_{\zeta(i)}$ pentru $1\leq i\leq\alpha$.
Dacă $j\în U$, apoi lasa $s_{j}$ fi permutarea lui $V$ definit prin închiriere
$s_{j}(v)=I(j)s(v)$ oricând $v\în V$. Lăsa $H^{-}$ fie grupul de permutări ale $V$ generate de mapări $s_{j}\circ s_{k}^{-1},s_{j}^{-1}\circ s_{k}$.
Lema: Să presupunem că pt $1\leq i\leq n$, $\Delta_{i}$ este un grup finit non-abelian cu $|\Delta_{i}|>1$ si unde daca $A,B\subseteq\Delta_{i}$ sunt subgrupuri astfel încât $ab=ba$ oricând $a\în A,b\în B$ si unde $\Delta_{i}=AB$, atunci fie $|A|=1$ sau $|B|=1.$ Apoi oricând $\phi:\Delta_{1}\times\dots\times\Delta_{n}\rightarrow\Delta_{1}\times\dots\times\Delta_{n}$ este un automorfism, există o permutare $\rho$ de $\{1,\puncte,n\}$ și izomorfisme $\phi_{i}:\Delta_{\rho(i)}\rightarrow\Delta_{i}$ Unde
$\phi(x_{1},\dots,x_{n})=(\phi_{1}(x_{\rho(1)}),\dots,\phi_{n}(x_{\rho(n )}))$.
Dovada: Observati ca daca $A_{1},\dots,A_{r}$ sunt subgrupuri de $\Delta_{i}$ și $ab=ba$ oricând $a\in A_{i},b\in A_{j},i\neq j$ și $\Delta_{i}=A_{1}\dots A_{r}$, atunci există o $i$ Unde $\Delta_{i}=A_{i}$ si unde
$|A_{j}|=1$ oricând $j\neq i$. Această observație poate fi stabilită prin inducție pe $r$.
Pentru $i,j\în\{1,\puncte,n\}$, lăsa $\pi_{j}:\Delta_{1}\times\dots\times\Delta_{n}\rightarrow\Delta_{j}$ fie maparea proiecției și lasă $\iota_{i}:\Delta_{i}\rightarrow\Delta_{1}\times\dots\times\Delta_{n}$ fi maparea incluziunii. Apoi oricând $i_{1}\neq i_{2}$ și
$a\in\pi_{j}[\phi[\iota_{i_{1}}[\Delta_{i_{1}}]]],b\in\pi_{j}[\phi[\iota_{i_ {2}}[\Delta_{i_{2}}]]]$, avem $ab=ba$. De cand
$\Delta_{j}$ este generat de subgrupuri $\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]$, știm asta pentru toți $j$, există cel mult unul $i$ Unde $|\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]|>1$ si pentru asa ceva $i$, avem
$\Delta_{j}=\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]$. Cu alte cuvinte, există o funcție $\rho:\{1,\dots,n\}\rightarrow\{1,\dots,n\}$ Unde
$\pi_{j}[\phi[\iota_{\rho(j)}[\Delta_{\rho(j)}]]]=\Delta_{j}$ pentru toți $j$ dar unde $|\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]|=1$ oricând $\rho(j)\neq i$.
Prin urmare, avem
$\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)})).$
De cand $\phi$ este un izomorfism, maparea $\rho$ este o bijecție și
$\pi_{j}\phi\iota_{\rho(j)}$ este un izomorfism din $\Delta_{\rho(j)}$ la $\Delta_{j}$ pentru toți $j$.
Q.E.D.
Lema: Să presupunem că $G$ este un grup care este factorizabil ca produs direct intern al subgrupurilor $\Delta_{1},\dots,\Delta_{m}$. În plus, să presupunem că pentru toți $i$, dacă $A,B$ sunt subgrupuri de $\Delta_{i}$ cu
$ab=ba$ pentru fiecare $a\în A,b\în B$ și $\Delta_{i}=AB$. Atunci dacă $\Delta_{1}^{\sharp},\dots,\Delta_{n}^{\sharp}$ este o altă factorizare a $G$ ca produs direct intern al subgrupurilor, atunci $m=n$, și există o oarecare permutare $\rho$ de $\{1,\dots,m\}$ Unde $\Delta_{i}=\Delta_{\rho(i)}^{\sharp}$ pentru toți $i$.
Dovada: Prin teorema Krull-Schmidt, știm asta $m=n$, și există o permutare $\rho$ de $\{1,\dots,m\}$ Unde $\Delta_{i}\simeq \Delta_{\rho(i)}^{\sharp}$ pentru toți $i$. Prin urmare, există un anumit automorfism $\phi$ de $G$ Unde $\phi$ se limitează la o mapare izomorfism $\Delta_{i}$ pe $\Delta_{\rho(i)}^{\sharp}$ pentru toți $i$. Cu toate acestea, după lema de mai sus, știm că există o anumită permutare $f$ de $\{1,\dots,m\}$ Unde $\phi[\Delta_{i}]=\Delta_{f(i)}$ pentru toți $i$. Prin urmare,
$\Delta_{\rho(i)}^{\sharp}=\Delta_{f(i)}$ pentru toți $i$. Q.E.D.
Teorema: Să presupunem că oricând $A,B$ sunt subgrupuri de $H^{-}$ cu
$ab=ba$ pentru $a\în A,b\în B$, fie $|A|=1$ sau $|B|=1$. Atunci dacă $(\phi,\psi)$ este un automorfism al $F$, apoi există o bijecție $W:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ alături de automorfisme
$\psi_{0},\dots,\psi_{n-1}$ de $\mathcal{V}$ astfel încât
$\psi(x_{0},\dots,x_{n-1})=(\psi_{0}(x_{W(0)}),\dots,\psi_{n-1}(x_{W (n-1)}))$ oricând $x_{0},\dots,x_{n-1}\în V.$
Dovada: Să presupunem că $(\phi,\psi)$ este un automorfism al $V$. Atunci $\psi$ păstrează grupul $H$ in sensul că $H=\psi H\psi^{-1}$. Prin urmare, dacă $H$ este factorizat ca un produs intern direct al subgrupurilor $H_{0},\dots,H_{n-1}$, apoi grupul $H$ este definibil în $(F,K,X)$, și setul de subgrupuri $\{H_{0},\dots,H_{n-1}\}$ este de asemenea definibilă în $(F,K,X)$.
Prin urmare, există o bijecție $\rho:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ astfel încât $H_{\rho(i)}=\psi H_{i}\psi^{-1}$ pentru toți $i$. Prin urmare, avem $H_{\rho(i)}\psi=\psi H_{i}$.
Să presupunem că $\pi_{0},\dots,\pi_{n-1}:X\rightarrow V$ sunt funcțiile de proiecție. Să presupunem că $\hat{H}_{i}$ este grupul generat de toți $H_{j}$este așa încât $i\neq j$.
Atunci $\pi_{i}(x)=\pi_{i}(y)$ dacă și numai dacă $h(x)=y$ pentru unii $h\in\hat{H}_{i}$ dacă și numai dacă $\psi^{-1}h'\psi(x)=y$ pentru unii $h'\in\hat{H}_{\rho(i)}$ dacă și numai dacă $h'\psi(x)=\psi(y)$ pentru unii
$h'\in\psi\hat{H}_{i}\psi^{-1}=\hat{H}_{\rho(i)}$ dacă și numai dacă
$\pi_{\rho(i)}\psi(x)=\pi_{\rho(i)}(\psi(y))$.
Prin urmare, $\psi(x_{0},\dots,x_{n-1})=(\psi_{0}(x_{\rho^{-1}(0)}),\dots,\psi_{n- 1}(x_{\rho^{-1}(n-1)})$ pentru unele bijectii
$\psi_{0},\dots,\psi_{n-1}$. În plus, bijecțiile $\psi_{0},\dots,\psi_{n-1}$ trebuie să fie automorfisme ale $\mathcal{V}$.
Q.E.D.
Teorema de mai sus se aplică atunci când $H^{-}$ este grupul alternativ sau simetric pe un set de mai mult de $4$ elemente. În special, teorema de mai sus se aplică cifrului bloc AES. O dovadă că pentru AES, grupul $H^{-}$ este grupul alternant poate fi găsit în lucrarea lui Ralph Wernsdorf care demonstrează că permutările rotunde ale cifrului bloc AES generează grupul alternativ al tuturor permutărilor de $\{1,\dots,2^{128}\}.$
