Destul de structură este de fapt definibilă în ceea ce privește funcția rotundă de criptare bloc și din această structură, se pot produce invarianți ai funcției rotunde de criptare bloc care măsoară securitatea criptografică.
O parte din acest răspuns este în esență aceeași cu al meu raspunsul anterior aici, deci în acest caz, vom omite dovezile rezultatelor.
Dacă $G,H$ sunt grupuri, atunci spunem că o funcție $\phi:G\rightarrow H$ este un homomorfism heap dacă există un homomorfism de grup $\psi:G\rightarrow H$ împreună cu o $b\în H$ Unde $\phi(g)=b\psi(g)$ pentru toți $b\în B.$ În mod echivalent, cartografierea $\phi:G\rightarrow H$ este un homomorfism heap dacă și numai dacă
$\phi(xy^{-1}z)=\phi(x)\phi(y)^{-1}\phi(z)$ oricând $x,y,z\în G$. Se spune că un homomorfism heap bijectiv este un automorfism heap.
Pentru această postare, lăsați $U_{0},\dots,U_{n-1},V_{0},\dots,V_{n-1}$ fie grupuri. Să presupunem că $I_{i}:U_{i}\rightarrow V_{i}$ este un izomorfism de grup ori de câte ori $0\leq i<n$. Lăsa $K=U_{0}\times\dots\times U_{n-1},X=V_{0}\times\dots\times V_{n-1}$.
Apoi definiți un izomorfism de grup $\iota:K\rightarrow X$ prin închiriere
$\iota(u_{0},\dots,u_{n-1})=(I_{0}(u_{0}),\dots,I_{n-1}(u_{n-1})) $.
Dacă $0\leq i<n$, apoi lasa $s_{i}:V_{i}\rightarrow V_{i}$ fi o bijecție arbitrară.
Definiți o mapare $S:V_{0}\times\dots\times V_{n-1}\rightarrow V_{0}\times\dots\times V_{n-1}$ prin închiriere $S(v_{0},\dots,v_{n-1})=(s_{0}(v_{0}),\dots,s_{n-1}(v_{n-1}))$.
Lăsa $\Gamma:X\rightarrow X$ fi un automorfism heap. Lăsa $P=\Gamma\circ S$și definiți o mapare $F:K\ori X\săgeata la dreapta X$ prin închiriere
$F(k,x)=\iota(k)P(x)$.
Propunere: Mapările $K^{2}\time X\rightarrow X,(j,k,x)\mapsto\iota(jk^{-1})x$ și $X^{3}\rightarrow X,(x,y,z)\mapsto xy^{-1}z$ sunt definibile de ordinul întâi în $(K,X,F)$.
Lăsa $\pi_{i}:X\rightarrow V_{i}$ fie homomorfismul grupului de proiecție. Lăsa $\simeq_{i}$ fie relația de echivalență pe $X$ unde ne-am stabilit $x\simeq_{i}y$ dacă și numai dacă $\pi_{i}(x)=\pi_{i}(y)$. Susţin că ansamblul relaţiilor de echivalenţă $\{\simeq_{0},\dots,\simeq_{n-1}\}$ este de ordin superior definibil în $(K,X,F)$ sub ipoteze rezonabile despre cifrul bloc $F$, dar pentru a demonstra această afirmație, va trebui să trecem peste câteva leme. Din definibilitatea lui $\{\simeq_{0},\dots,\simeq_{n-1}\}$, putem produce mulți invarianți ai funcției rotunde de criptare bloc care măsoară neliniaritatea și, de asemenea, efectul de avalanșă.
Pentru $0\leq i<n$, și $j\în U_{i}$, lăsa $s_{i}^{j}$ fi permutarea lui $V_{i}$ definit prin închiriere $s_{i}^{j}(v)=I_{i}(j)s_{i}(v)$.
Dacă $0\leq i<n$, apoi lasa $H_{i}$ fi grupul tuturor permutărilor de $V_{i}$ generat de $s_{i}^{j}\circ(s_{i}^{k})^{-1},(s_{i}^{j})^{-1}\circ s_{i}^{ k}$.
Lăsa $H$ fi grupul tuturor permutărilor de $X$ generate de toate permutările formei $F_{j}^{-1}\circ F_{k},F_{j}\circ F_{k}^{-1}$. Observă asta
$F_{j}\circ F_{k}^{-1}(x)=\iota(jk^{-1})(x)$ și $F_{j}^{-1}\circ F_{k}(x)=S^{-1}[\Gamma^{-1}[\iota(j^{-1}k)]S(x )]$. În special,
$H$ este generată de permutările formei $x\mapsto\iota(m)(x)$ împreună cu permutările formei $S^{-1}[\iota(m)S(x)]$. Spus altfel, $H$ este generată de permutările formei
$$(x_{0},\dots,x_{n-1})\mapsto(I_{0}(m_{0})(x_{0}),\dots,I_{n-1}(m_{ n-1})(x_{n-1}))$$ și
$$(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} ))]).$$
Prin urmare, $H$ constă din toate permutările formei $h_{0}\time\dots\times h_{n-1}$ Unde $h_{i}\în H_{i}$ oricând $0\leq i<n$.
Prin urmare $H\simeq H_{0}\times\dots\times H_{n-1}$ ca produs direct extern. S-ar putea să scriem și noi $H$ ca produs intern direct $H_{0}^{\sharp},\dots,H_{n-1}^{\sharp}$ Unde $H_{i}^{\sharp}$ constă din toate mapările $h\în H$ unde dacă $h_{0},\dots,h_{n-1}$ sunt mapările unde $h(x_{0},\dots,x_{n-1})=(h_{0}(x_{0}),\dots,h_{n-1}(x_{n-1}))$ pentru toți $x_{0},\dots,x_{n-1}$, atunci
$h_{j}$ este funcția de identitate oricând $j\neq i$. Atunci $H_{i}^{\sharp}\simeq H_{i}$ oricând $0\leq i<n.$
Noi spunem că un grup $G$ este supraindecompozibilă dacă oricând $A,B$ sunt subgrupuri de $G$ cu $ab=ba$ oricând $a\în A,b\în B$ și $G=AB$, atunci $|A|=1$ sau $|B|=1$ (anunțați-mă în comentarii dacă vă puteți gândi la un cuvânt mai bun decât „superindecompozibil”).
Teorema (Krull-Schmidt): Să presupunem că $G$ este un grup care satisface condiția lanțului ascendent și condiția lanțului descendent pe subgrupuri normale (orice grup finit satisface această proprietate). Mai mult, să presupunem că $G$ este scris ca un produs direct intern al subgrupurilor netriviale direct indecompuse în două moduri diferite, și anume $G=G_{0}\time\dots\times G_{n-1}$ și $G=H_{0}\times\dots H_{n-1}$. Apoi există o permutare $\rho$ de $\{0,\dots,n-1\}$ astfel încât
$G_{i}\simeq H_{\rho(i)}$ pentru $0\leq i<n$ si unde
$$G=G_{0}\times\dots\times G_{r}\times H_{\rho(r+1)}\times\dots H_{\rho(n-1)}$$ oricând $0\leq r\leq n-1$.
Lema: Să presupunem că $G$ este un grup finit. Dacă $G$ este un produs direct intern al subgrupurilor superindecompozibile, atunci ori de câte ori factorăm $G$ ca produse interne directe $G=G_{0}\time\dots\times G_{m-1}$ și $G=H_{0}\time\dots\times H_{n-1}$, atunci $m=n$, și există o oarecare permutare $\rho:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ Unde $H_{i}=G_{\rho(i)}$ pentru $0\leq i<n$.
Teoremă: Există o formulă de ordin superior $\phi$ astfel încât dacă grupurile $H_{0},\dots,H_{n-1}$ sunt deci indecompuse $(K,X,F)\modele\phi(z)$ dacă și numai dacă $z=\{\simeq_{0},\dots,\simeq_{n-1}\}$.
Dovada: Observați că grupul $H$ este de ordin superior definibil în structură $(K,X,F)$. În plus, grupul $H$ are o factorizare unică până la permutare
$H^{\sharp}_{0}\times\dots\times H^{\sharp}_{n-1}$ în factorii săi incompuși. Prin urmare, ansamblul tuturor factorilor necompozibili $\{H^{\sharp}_{0},\dots,H^{\sharp}_{n-1}\}$ este definibil în $(K,X,F)$.
Acum, pentru fiecare $i$, lăsa $\hat{\simeq}_{i}$ fi relația de echivalență în care stabilim
$x\hat{\simeq}_{i}y$ dacă și numai dacă $h(x)=y$ pentru unii $h\în H^{\sharp}_{i}$. Lăsa
$\simeq_{i}$ fie relația de echivalență pe $X$ generat de
$\bigcup\{\hat{\simeq}_{j}\mid j\neq i\}$. Atunci $\{\simeq_{0},\dots,\simeq_{n-1}\}$ este definibil din $\{H^{\sharp}_{0},\dots,H^{\sharp}_{n-1}\}$. Prin urmare, setul
$\{\simeq_{0},\dots,\simeq_{n-1}\}$ este definibil în $(K,X,F)$. $\pătrat$
Din definibilitatea lui $\{\simeq_{0},\dots,\simeq_{n-1}\}$, putem defini destul de mulți invarianți ai funcției rotunde de criptare bloc.
Dacă $T_{1},T_{2}$ sunt grupuri, și $f_{i}:T_{i}\rightarrow T_{i}$ pentru $i\în\{1,2\}$, atunci spunem asta $f_{1},f_{2}$ sunt echivalente afine dacă există automorfisme heap $L_{1}:T_{1}\rightarrow T_{2},L_{2}:T_{2}\rightarrow T_{1}$ Unde
$f_{2}=L_{1}f_{1}L_{2}$. Noi spunem că o cartografiere $M$ este invariant sub echivalenţă afină dacă $M(f)=M(g)$ oricând $f,g$ sunt afin echivalente.
Noi spunem că o pereche $(k,\Delta)$ este o S-boxificare dacă $\Delta$ este un automorfism heap și oricând $x\simeq_{i}y$, atunci $\Delta\circ F_{k}(x)\simeq_{i}\Delta\circ F_{k}(y)$. Colecția tuturor S-boxificărilor este definită de ordin superior în $(K,X,F)$. Observați că există o S-boxificare și anume maparea $(e,\Gamma^{-1})$. Să presupunem că acum
$(k,\Delta)$ este o S-boxificare. Atunci este ușor să arăți că fiecare $\simeq_{i}$ este o congruență cu privire la $\Delta\Gamma^{-1}$. Prin urmare $\Delta=E\Gamma^{-1}$ pentru un anumit automorfism heap $E$ unde fiecare $\simeq_{i}$ este o congruență cu privire la $E$. Prin urmare, $\Delta\circ F_{k}=E'\circ S$ pentru un anumit automorfism heap $E'$. Prin urmare, algebra coeficientului $(X,\Delta\circ F_{k})/\simeq_{i}$ este afin echivalent cu $(V_{i},s_{i})$ pentru $0\leq i<n$. Din aceste observații, obținem următorul fapt.
Fapt: Dacă cartografierea $M$ este invariant sub echivalență afină și definibil în logica de ordin superior, apoi maparea $M^{+}$ definit prin închiriere
$M^{+}(F)=\{M(s_{0}),\dots,M(s_{n-1})\}$ este de ordin superior definibil în structură $(K,X,F)$. Prin urmare, $M^{+}$ este un parametru invariant al funcției rotunde.
