Tôi khẳng định rằng đối với một lớp lớn các hàm làm tròn mật mã khối bao gồm hàm làm tròn AES, cấu trúc affine trên không gian khóa tròn và cả trên không gian khối có thể được xác định từ hàm làm tròn mật mã khối. Do đó, các phép tự đồng cấu duy nhất có thể có đối với AES và các mật mã khối liên quan là các phép biến đổi affine.
Trường hợp khi $K$ là một nhóm hành động trên $X$
Giả sử rằng $K$ là một nhóm hành động trên bộ $X$ mỗi người ở đâu $k\in K\setminus\{e\}$, có một số $x\trong X$ với $k\cdot x\neq x$. Giả sử rằng $F_{k}(x)=F(k,x)=k\cdot P(x)$ cho một số hoán vị $P:X\rightarrow X$.
quan sát rằng $F_{k}^{-1}(x)=P^{-1}(k^{-1}\cdot x)$. Chúng tôi quan sát thấy rằng
$$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.$$
Đặc biệt, ánh xạ từ $K^{4}\times X$ đến $X$ Được định nghĩa bởi $(i,j,k,l,x)\mapsto i\cdot j^{-1}\cdot k\cdot l^{-1}\cdot x$ là xác định được. Bây giờ, hãy quan sát điều đó $ij^{-1}kl^{-1}=e$ nếu và chỉ nếu $x=i\cdot j^{-1}\cdot k\cdot l^{-1}\cdot x$ cho tất cả $x\trong X.$ Do đó, tập hợp tất cả $(w,x,y,z)\in K^{4}$ ở đâu $wx^{-1}yz^{-1}=e$ được xác định theo chức năng $F$. Do đó, chức năng $K^{3}\rightarrow K,(x,y,z)\mapsto xy^{-1}z$ được xác định theo chức năng $F$. các hoạt động $K^{3}\rightarrow K,(x,y,z)\mapsto xy^{-1}z$ được gọi là thao tác heap và thao tác heap có thể được coi là thao tác mà từ đó bạn có thể khôi phục hầu hết thông tin từ nhóm, nhưng bạn xác định phần tử nào của nhóm là danh tính từ thao tác heap; mặt khác, bạn có thể dễ dàng khôi phục thao tác nhóm từ thao tác heap cùng với danh tính của nhóm. Phép toán heap nên được coi là một tổng quát hóa phi abelian của khái niệm không gian afin.
Dự luật: $(\phi,\psi)$ là một tự động cấu hình của chức năng vòng $F$. Sau đó để cho $a=\phi(e)$, và để $L:K\rightarrow K$ là ánh xạ được xác định bởi $L(k)=a^{-1}\phi(k)$. sau đó $L$ là một tự cấu nhóm.
Chứng minh: Quan sát thấy $\phi(k)=aL(k)$ cho mỗi $k\in K$. Vì vậy,
$$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).$$
Vì vậy, việc lập bản đồ $L$ là một đồng cấu nhóm. Từ $\phi$ là khách quan, $L$ là khách quan là tốt. Q.E.D.
Bây giờ xác định $M(k)=\phi(k)a^{-1}$. sau đó $M$ là một automorphism trong đó
$\phi(k)=M(k)a$ vì $k\in K$. Vì vậy,
$$\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).$$ Vì vậy,
$\psi(k\cdot x)=M(k)\psi(x)$ cho mỗi $k\in K$.
Trường hợp khi $K$ và $X$ là các nhóm đẳng cấu và hành động của nhóm là phép nhân trái
Bây giờ giả sử rằng $K,X$ là các nhóm và $\iota:K\rightarrow X$ là một đẳng cấu. Sau đó giả sử rằng hành động của $K$ trên $X$ được định nghĩa bởi $k\cdot x=\iota(k)x$ cho mỗi $k\in K,x\in X$. sau đó $F_{k}(x)=F(k,x)=k\cdot P(x)=\iota(k)P(x)$ cho mỗi $k\in K,x\in X$.
Chúng ta có $\psi(\iota(k)x)=\iota(M(k))\psi(x)$ cho tất cả $k,x$. Đặc biệt, nếu $b=\psi(e)$, sau đó $$\psi(\iota(k))=\psi(\iota(k)e)=\iota(M(k))\psi(e)=\iota(M(k))b.$$ Nói khác đi, nếu $x=\iota(k)$, sau đó $\psi(x)=\iota(M(k))b=\iota(M(\iota^{-1}(x)))b$. Đối với phần còn lại của bài đăng này, chúng tôi sẽ viết $M'=\iota\circ M\iota^{-1}$ và để cho $L'=\iota\circ L\circ\iota^{-1}$.
Trên thực tế, bạn có thể dễ dàng xác định thao tác $X^{3}\rightarrow X,(x,y,z)\mapsto xy^{-1}z$ từ hoạt động $K^{2}\times X\rightarrow X(j,k,x)\mapsto\iota(jk^{-1})x$.
Chia động từ P
trong trường hợp $K$ chỉ đơn giản là hành động trên $X$ nhưng ở đâu $X$ không nhất thiết phải là một nhóm, chúng tôi có $$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)).$$
Bây giờ, giả sử rằng chúng ta đang ở trong trường hợp khi $k\cdot x=\iota(k)x$ và $\iota:K\rightarrow X$ là đẳng cấu nhóm. sau đó
quan sát rằng $F_{j}^{-1}F_{k}(x)=P^{-1}[\iota(j^{-1}k)\cdot P(x)].$
Giả sử rằng $F_{j}^{-1}F_{k}(u)=v$. sau đó $F_{j}^{-1}F_{k}(x)=P^{-1}[P(v)P(u)^{-1}P(x)]$, do đó phép toán đống liên hợp
$(x,y,z)\mapsto P^{-1}[P(x)P(y)^{-1}P(z)]$ cũng được xác định từ $F$.
Do đó, các ánh xạ $\psi,P\psi P^{-1}$ cả hai phải là tự cấu hình đống.
mạng SP
Giả sử rằng $K=U^{n},X=V^{n}$ ở đâu $U,V$ là các nhóm và $I:U\rightarrow V$ là một đẳng cấu. Giả sử rằng $\iota:K\rightarrow X$ là đẳng cấu được xác định bằng cách cho $\iota((r_{k})_{k})=(I(r_{k}))_{k}$.
Để cho $s:V\rightarrow V$ là một lời từ chối. Xác định ánh xạ $S:V\rightarrow V$ bằng cách cho phép $S((v_{k})_{k})=(s(v_{k}))_{k}$. Để cho $\Gamma:X\rightarrow X$ là một heap automorphism.
Giả sử rằng $P=\Gamma\circ S$. Như trước đây, chúng tôi cho rằng $F_{k}(x)=\iota(k)P(x)$.
quan sát rằng $P^{-1}[P(x)P(y)^{-1}P(z)]=S^{-1}[S(x)S(y)^{-1}S(z )]$, do đó các ánh xạ $\psi,S\psi S^{-1}$ cả hai phải là tự cấu hình đống.
Để cho $\mathcal{V}=(V,\Omega,\mho)$ là cấu trúc đại số trong đó $\Omega,\mho$ là các hoạt động bậc ba được xác định bằng cách cho phép
$\Omega(x,y,z)=xy^{-1}z,\mho(x,y,z)=s^{-1}[s(x)s(y)^{-1}s (z)]$. sau đó $\psi$ phải là tự biến hình của $\mathcal{V}^{n}$. Bây giờ chúng ta sẽ giới hạn khả năng tự biến hình $\psi$ khi chức năng $s$ thỏa mãn tính chất tốt đẹp.
chúng tôi nói rằng $s$ là xiên-cứng nhắc nếu bất cứ khi nào
$E:\mathcal{V}\times\mathcal{V}\rightarrow\mathcal{V}$ là một nội hình,
ánh xạ $x\mapsto E(e,x)$ là ánh xạ hằng hoặc ánh xạ
$x\mapsto E(x,e)$ là một ánh xạ không đổi.
Định lý: Nếu ánh xạ $s$ là xiên-cứng, sau đó có một bijection $W:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ cùng với tự biến hình
$\psi_{0},\dots,\psi_{n-1}$ của $\mathcal{V}$ như vậy mà
$\psi((x_{k})_{k=0}^{n-1})=(\psi_{j}(x_{W(j)}))_{j=0}^{n- 1}$ bất cứ khi nào $x_{0},\dots,x_{n-1}\in V$.
Bằng chứng:
Xác định ánh xạ $\text{in}_{j}:V\rightarrow V^{n}$ bằng cách cho phép
$\text{in}_{j}(r)=(r_{k})_{k=0}^{n-1}$ bằng cách cho phép $r=r_{j}$ và $r_{k}=e$ bất cứ khi nào $k\neq j$. Xác định ánh xạ $\text{jn}_{j}:V^{n}\rightarrow V$ bằng cách cho phép $\text{jn}_{j}(r_{k})_{k=0}^{n-1}=r_{j}.$
Bây giờ, hãy quan sát điều đó $\text{jn}_{j}\circ\psi\circ\text{in}_{i}:\mathcal{V}\rightarrow\mathcal{V}$ là một endomorphism cho tất cả $i,j$, vì vậy hãy
$\psi_{i,j}=\text{jn}_{j}\circ\psi\circ\text{in}_{i}$. Từ $\mathcal{V}^{n}$ được sinh ra bởi các đại số con có dạng
$\text{in}_{i}[\mathcal{V}]$, chúng tôi quan sát thấy rằng tính tự động $(\theta,\psi)$ được xác định hoàn toàn bởi ma trận nội hình $(\psi_{i,j})_{i,j}$ của $\mathcal{V}$.
Giả sử rằng $s$ là xiên-cứng nhắc. Giả sử $i\neq j$. Để cho
$\text{in}_{i,j}:\mathcal{V}^{2}\rightarrow\mathcal{V}^{n}$ là ánh xạ được xác định bằng cách cho phép $\text{in}_{i,j}(u,v)=(v_{k})_{k}$ chính xác khi nào $v_{i}=u,v_{j}=v$, và $v_{k}=e$ bất cứ khi nào $k\not\in\{i,j\}$.
Giả sử $i\neq j$ và $E=\text{jn}_{k}\circ\psi\circ\text{in}_{i,j}$.
sau đó $E$ là một đồng cấu từ $\mathcal{V}^{2}$ đến $\mathcal{V}.$
Hơn nữa, $E(x,e)=\psi_{i,k}(x),E(e,x)=\psi_{j,k}(x)$, do đó ánh xạ $\psi_{i,k}$ là ánh xạ hằng hoặc ánh xạ $\psi_{j,k}$ là một ánh xạ không đổi.
Cho mỗi $n$, Đây là một $n+1$thuật ngữ -ary $t$ trong ngôn ngữ của $\mathcal{V}$ như vậy mà $t(x_{1},\dots,x_{n},e)=x_{1}\dots x_{n}$ và nói chung là $$t(x_{1},\dots,x_{n},a)=x_{1}a^{-1}x_{2}\dots x_{n-1}a^{-1}x_{ n}.$$
Chúng ta có
$$(x_{k})_{k=0}^{n-1}=t(\text{in}_{0}(x_{0}),\dots,\text{in}_{n -1}(x_{k}),e),$$ Vì thế
$$\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})),\ văn bản{jn}_{j}\psi(e)).$$ Vì vậy, có một số $i$ ở đâu
ánh xạ $\text{jn}_{j}\psi\text{in}_{i'}$ là một hàm hằng bất cứ khi nào $i'\neq i.$ Do đó, có một chức năng $W:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ ở đâu cho tất cả $j$, có một số nội hình
$\psi_{j}:\mathcal{V}\rightarrow\mathcal{V}$ với
$\text{jn}_{j}\psi((x_{k})_{k=0}^{n-1})=\psi_{j}(x_{W(j)})$.
Vì vậy, chúng tôi có $\psi((x_{k})_{k=0}^{n-1})=(\psi_{j}(x_{W(j)}))_{j=0}^{n- 1}$. Kể từ khi lập bản đồ $\psi$ là một automorphism và kể từ đó $\mathcal{V}$ là hữu hạn, chúng ta biết rằng mỗi ánh xạ $\psi_{j}$ cũng phải là một automorphism và ánh xạ $W$ phải là một bijection.
Q.E.D.
Định lý trên phát biểu rằng bất cứ khi nào $s$ là xiên cứng nhắc, nhóm automorphism của $F$ do đó là một nhóm con của sản phẩm vòng hoa của $\text{Aut}(\mathcal{V})$ với nhóm đối xứng $S_{n}$.
Chúng tôi cũng có thể đảm bảo rằng nhóm automorphism của $F$ được thuần hóa một cách hợp lý theo các giả định khác nhau về các hộp chữ S.
Để cho $H$ là nhóm các hoán vị của $X$ được tạo bởi tất cả các hoán vị của mẫu $F_{j}\circ F_{k}^{-1},F_{j}^{-1}\circ F_{k}$. Bây giờ chúng ta sẽ chỉ ra rằng dưới những giả thuyết hợp lý, sự phân rã của $H$ có tích trực tiếp trong của nhóm trực tiếp bất phân là duy nhất.
Từ một phiên bản suy yếu của định lý Krull-Schmidt, chúng ta biết rằng nếu $G_{1},\dots,G_{\alpha},H_{1},\dots,H_{\beta}$ là các nhóm không thể phân tách trực tiếp hữu hạn và
$G_{1}\times\dots\times G_{\alpha}\simeq H_{1}\times\dots\times H_{\beta}$, sau đó $\alpha=\beta$, và có một phép loại trừ $\zeta:\{1,\dots,\alpha\}\rightarrow\{1,\dots,\beta\}$ ở đâu $G_{i}\simeq H_{\zeta(i)}$ vì $1\leq i\leq\alpha$.
Nếu $j\in U$, sau đó để $s_{j}$ là hoán vị của $V$ được xác định bằng cách cho phép
$s_{j}(v)=I(j)s(v)$ bất cứ khi nào $v\in V$. Để cho $H^{-}$ là nhóm các hoán vị của $V$ được tạo ra bởi các ánh xạ $s_{j}\circ s_{k}^{-1},s_{j}^{-1}\circ s_{k}$.
Bổ đề: Giả sử rằng đối với $1\leq i\leq n$, $\Delta_{i}$ là một nhóm không abelian hữu hạn với $|\Delta_{i}|>1$ và ở đâu nếu $A,B\subseteq\Delta_{i}$ là các nhóm con sao cho $ab=ba$ bất cứ khi nào $a\trong A,b\trong B$ và ở đâu $\Delta_{i}=AB$, thì một trong hai $|A|=1$ hoặc $|B|=1,$ Rồi bất cứ khi nào $\phi:\Delta_{1}\times\dots\times\Delta_{n}\rightarrow\Delta_{1}\times\dots\times\Delta_{n}$ là một phép đồng vị, có một hoán vị $\rho$ của $\{1,\dots,n\}$ và đẳng cấu $\phi_{i}:\Delta_{\rho(i)}\rightarrow\Delta_{i}$ ở đâu
$\phi(x_{1},\dots,x_{n})=(\phi_{1}(x_{\rho(1)}),\dots,\phi_{n}(x_{\rho(n )}))$.
Chứng minh: Quan sát rằng nếu $A_{1},\dots,A_{r}$ là các nhóm con của $\Delta_{i}$ và $ab=ba$ bất cứ khi nào $a\in A_{i},b\in A_{j},i\neq j$ và $\Delta_{i}=A_{1}\dots A_{r}$, thì tồn tại một $i$ ở đâu $\Delta_{i}=A_{i}$ và ở đâu
$|A_{j}|=1$ bất cứ khi nào $j\neq i$. Quan sát này có thể được thiết lập bằng quy nạp trên $r$.
Vì $i,j\in\{1,\dots,n\}$, để cho $\pi_{j}:\Delta_{1}\times\dots\times\Delta_{n}\rightarrow\Delta_{j}$ là ánh xạ chiếu, và đặt $\iota_{i}:\Delta_{i}\rightarrow\Delta_{1}\times\dots\times\Delta_{n}$ là ánh xạ bao gồm. Rồi bất cứ khi nào $i_{1}\neq i_{2}$ và
$a\in\pi_{j}[\phi[\iota_{i_{1}}[\Delta_{i_{1}}]]],b\in\pi_{j}[\phi[\iota_{i_ {2}}[\Delta_{i_{2}}]]]$, chúng ta có $ab=ba$. Từ
$\Delta_{j}$ được tạo ra bởi các nhóm con $\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]$, chúng tôi biết rằng đối với tất cả $j$, tồn tại nhiều nhất một $i$ ở đâu $|\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]|>1$ và cho như vậy $i$, chúng ta có
$\Delta_{j}=\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]$. Nói cách khác, có một chức năng $\rho:\{1,\dots,n\}\rightarrow\{1,\dots,n\}$ ở đâu
$\pi_{j}[\phi[\iota_{\rho(j)}[\Delta_{\rho(j)}]]]=\Delta_{j}$ cho tất cả $j$ nhưng ở đâu $|\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]|=1$ bất cứ khi nào $\rho(j)\neq i$.
Vì vậy, chúng tôi có
$\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)})).$
Từ $\phi$ là một đẳng cấu, ánh xạ $\rho$ là một dự đoán, và
$\pi_{j}\phi\iota_{\rho(j)}$ là một đẳng cấu từ $\Delta_{\rho(j)}$ đến $\Delta_{j}$ cho tất cả $j$.
Q.E.D.
Bổ đề: Giả sử rằng $G$ là một nhóm có thể phân tích thành nhân tử như một sản phẩm trực tiếp bên trong của các nhóm con $\Delta_{1},\dots,\Delta_{m}$. Hơn nữa, giả sử rằng với mọi $i$, nếu $A,B$ là các nhóm con của $\Delta_{i}$ với
$ab=ba$ cho mỗi $a\trong A,b\trong B$ và $\Delta_{i}=AB$. Sau đó nếu $\Delta_{1}^{\sharp},\dots,\Delta_{n}^{\sharp}$ là một yếu tố khác của $G$ như một sản phẩm trực tiếp bên trong của các nhóm con, sau đó $m=n$, và có một số hoán vị $\rho$ của $\{1,\dots,m\}$ ở đâu $\Delta_{i}=\Delta_{\rho(i)}^{\sharp}$ cho tất cả $i$.
Chứng minh: Theo định lý Krull-Schmidt, chúng ta biết rằng $m=n$, và có một hoán vị $\rho$ của $\{1,\dots,m\}$ ở đâu $\Delta_{i}\simeq \Delta_{\rho(i)}^{\sharp}$ cho tất cả $i$. Do đó, có một số tự động hóa $\phi$ của $G$ ở đâu $\phi$ giới hạn đối với ánh xạ đẳng cấu $\Delta_{i}$ trên $\Delta_{\rho(i)}^{\sharp}$ cho tất cả $i$. Tuy nhiên, theo bổ đề trên, chúng ta biết rằng có một số hoán vị $f$ của $\{1,\dots,m\}$ ở đâu $\phi[\Delta_{i}]=\Delta_{f(i)}$ cho tất cả $i$. Vì vậy,
$\Delta_{\rho(i)}^{\sharp}=\Delta_{f(i)}$ cho tất cả $i$. Q.E.D.
Định lý: Giả sử rằng bất cứ khi nào $A,B$ là các nhóm con của $H^{-}$ với
$ab=ba$ vì $a\trong A,b\trong B$, một trong hai $|A|=1$ hoặc $|B|=1$. Sau đó nếu $(\phi,\psi)$ là một phép biến hình của $F$, sau đó có một bijection $W:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ cùng với tự biến hình
$\psi_{0},\dots,\psi_{n-1}$ của $\mathcal{V}$ như vậy mà
$\psi(x_{0},\dots,x_{n-1})=(\psi_{0}(x_{W(0)}),\dots,\psi_{n-1}(x_{W (n-1)}))$ bất cứ khi nào $x_{0},\dots,x_{n-1}\in V.$
Chứng minh: Giả sử rằng $(\phi,\psi)$ là một phép biến hình của $V$. sau đó $\psi$ bảo tồn nhóm $H$ theo nghĩa là $H=\psi H\psi^{-1}$. Vì vậy, nếu $H$ được coi là một sản phẩm trực tiếp bên trong của các nhóm con $H_{0},\dots,H_{n-1}$, sau đó nhóm $H$ được xác định trong $(F,K,X)$, và tập các nhóm con $\{H_{0},\dots,H_{n-1}\}$ cũng được xác định trong $(F,K,X)$.
Vì vậy, có một sự từ chối $\rho:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ như vậy mà $H_{\rho(i)}=\psi H_{i}\psi^{-1}$ cho tất cả $i$. Vì vậy, chúng tôi có $H_{\rho(i)}\psi=\psi H_{i}$.
Giả sử rằng $\pi_{0},\dots,\pi_{n-1}:X\rightarrow V$ là các hàm chiếu. Giả sử rằng $\hat{H}_{i}$ là nhóm được tạo bởi tất cả $H_{j}$là như vậy $i\neq j$.
sau đó $\pi_{i}(x)=\pi_{i}(y)$ nếu và chỉ nếu $h(x)=y$ cho một số $h\in\hat{H}_{i}$ nếu và chỉ nếu $\psi^{-1}h'\psi(x)=y$ cho một số $h'\in\hat{H}_{\rho(i)}$ nếu và chỉ nếu $h'\psi(x)=\psi(y)$ cho một số
$h'\in\psi\hat{H}_{i}\psi^{-1}=\hat{H}_{\rho(i)}$ nếu và chỉ nếu
$\pi_{\rho(i)}\psi(x)=\pi_{\rho(i)}(\psi(y))$.
Vì vậy, $\psi(x_{0},\dots,x_{n-1})=(\psi_{0}(x_{\rho^{-1}(0)}),\dots,\psi_{n- 1}(x_{\rho^{-1}(n-1)})$ cho một số bijections
$\psi_{0},\dots,\psi_{n-1}$. Hơn nữa, các dự đoán $\psi_{0},\dots,\psi_{n-1}$ phải là phép biến hình của $\mathcal{V}$.
Q.E.D.
Định lý trên áp dụng khi $H^{-}$ là nhóm xen kẽ hoặc đối xứng trên một tập hợp nhiều hơn $4$ phần tử. Đặc biệt, định lý trên áp dụng cho mật mã khối AES. Một bằng chứng rằng đối với AES, nhóm $H^{-}$ là nhóm xen kẽ có thể được tìm thấy trong bài báo của Ralph Wernsdorf chứng minh rằng các hoán vị vòng của mật mã khối AES tạo ra nhóm xen kẽ của tất cả các hoán vị của $\{1,\dots,2^{128}\}.$
