มีการคำนวณกลุ่ม automorphism ของ block cipher เช่น AES หรือ DES รุ่นอื่นหรือไม่?

สมมติว่า $F:K\times X\rightarrow X$ เป็นฟังก์ชัน ถ้า $k\ ใน K$จากนั้นให้ $F_{k}:X\ลูกศรขวา X$ เป็นแผนที่กำหนดโดยให้ $F_{k}(x)=F(k,x)$ แต่ละ $x\ ใน X$. แล้วเราจะโทรหา $F$ บล็อกตัวเลขรอบฟังก์ชันถ้า $F_{k}$ เป็น Bijection สำหรับแต่ละ $k\ ใน K$.

กลุ่ม $\text{Aut}(F)$ เป็นการรวบรวมทุกคู่ $(\phi,\psi)$ ดังนั้น $\phi\in\text{Sym}(K)$, $\psi\in\text{Sym}(X)$, และ $\psi(F(k,x))=F(\phi(k),\psi(x))$ เมื่อไหร่ก็ตาม $k\in K,x\in X$. กล่าวต่างหากว่า $(\phi,\psi)$ เป็น automorphism เมื่อ $\psi\circ F_{k}=F_{\phi(k)}\circ\psi$ แต่ละ $k\ ใน K$.

มีการคำนวณกลุ่ม automorphism ของฟังก์ชันรอบสำหรับรุ่นต่างๆ ของ AES หรือ DES หรือรหัสบล็อกที่รู้จักกันดีอื่น ๆ หรือไม่ กลุ่ม automorphism ของ block ciphers ที่รู้จักกันดีเหล่านี้เป็นเรื่องเล็กน้อยหรือไม่?

การคำนวณกลุ่ม automorphism ของฟังก์ชันการปัดเศษของบล็อกให้ข้อมูลที่มีค่าเกี่ยวกับการเข้ารหัสของบล็อกในหลายวิธี

ถ้า $(1_{K},\psi)\in\text{Aut}(F)$ และ $\psi$ ไม่ใช่ฟังก์ชั่นประจำตัวแล้ว $\{F_{k}\กลาง k\in K\}$ เป็นส่วนย่อยของ Centralizer $C_{\text{Sym}(X)}(\psi)$. ดังนั้นการเปลี่ยนแปลงการเข้ารหัสใดๆ $E_{k}:X\ลูกศรขวา X$ ได้จากฟังก์ชันกลม $F$ จะต้องมีอยู่ใน $C_{\text{Sym}(X)}(\psi)$, ดังนั้น $E_{k}\phi=\phi E_{k}$ (นี่คือตัวอย่างของการเข้ารหัสแบบโฮโมมอร์ฟิคบางส่วน)

ถ้า $(\phi,1_{X})\in\text{Aut}(F)$, และ $\phi$ ไม่ใช่ฟังก์ชั่นประจำตัวแล้ว $F_{k}=F_{\phi(k)}$ แต่ละ $k\ ใน K$. ดังนั้นตั้งแต่ $\phi$ ไม่ใช่ฟังก์ชั่นประจำตัวมีบางอย่าง $k$ ที่ไหน $k\neq\phi(k)$ แต่ที่ไหน $F_{k}=F_{\phi(k)}$, ดังนั้น $|\{F_{k}|k\in K\}|<|K|$ดังนั้นในกรณีนี้ มีค่าน้อยกว่าอย่างมีประสิทธิภาพ $|K|$ แป้นกลมจำนวนมาก

ตอนนี้ในกรณีทั่วไปที่ $(\phi,\psi)\in\text{Aut}(F)$ แต่ที่ไหนไม่ได้ $\phi$ ก็ไม่เช่นกัน $\psi$ คือฟังก์ชันประจำตัวที่เรามี $$\psi\circ F_{k_{1}}\circ\cdots\circ F_{k_{r}}=F_{\phi(k_{1})}\circ\cdots\circ F_{\phi(k_ {r})}\circ\psi$$ สำหรับแต่ละลำดับของแป้นกลม $k_{1},\dots,k_{r}$. ในกรณีนี้ ควรเลือกอัลกอริธึมการตั้งเวลาคีย์ที่ดีเพื่อป้องกันการโจมตีคีย์ที่เกี่ยวข้อง

ในกรณีที่ $\text{Aut}(F)$ เป็นเรื่องเล็กน้อย ฟังก์ชันหรือความสัมพันธ์ใดๆ $(K,X)$ สามารถนิยามได้อย่างแท้จริงในแง่ของทฤษฎีแบบจำลอง

ยันต์สมัยใหม่พยายามที่จะหลีกเลี่ยง ใดๆ โครงสร้าง (ยกเว้นกรณีพิเศษบางอย่าง เช่น PRINCE cipher) แม้แต่ที่ ความน่าจะเป็น ระดับ. การมีความน่าจะเป็นเช่นนี้ 1 automorphism ที่ไม่สำคัญน่าจะเป็นสัญญาณสำคัญของความอ่อนแอ

เพียงแค่ดูที่ปุ่มใดปุ่มหนึ่ง $k_0$ และภาพลักษณ์ของมัน $k_1=\phi(k_0) \ne k_0$จำเป็นต้องมีการเรียงสับเปลี่ยน $F_{k_0}$ และ $F_{k_1}$ มีโครงสร้างวงจรเหมือนกัน สิ่งนี้เป็นสิ่งที่คาดไม่ถึงสำหรับนักเข้ารหัสที่แท้จริงส่วนใหญ่ รวมถึง AES อย่างไรก็ตาม การพิสูจน์สิ่งนี้อย่างเป็นรูปธรรมนั้นอาจเป็นเรื่องยากมาก

สำหรับ DES มีคีย์ที่อ่อนแอและคุณสมบัติเสริม แต่ฉันไม่รู้ว่าสามารถใช้เพื่อสร้างออโตมอร์ฟิซึ่มเต็มรูปแบบได้หรือไม่

Crypto'92, Campbell และ Wiener

DES ไม่ใช่กลุ่ม

https://link.springer.com/chapter/10.1007/3-540-48071-4_36

เราพิสูจน์ว่าชุดของการเรียงสับเปลี่ยน DES (การเข้ารหัสและถอดรหัสสำหรับแต่ละคีย์ DES) ไม่ได้ถูกปิดภายใต้องค์ประกอบการทำงาน ซึ่งหมายความว่า โดยทั่วไป การเข้ารหัส DES หลายรายการไม่เทียบเท่ากับการเข้ารหัส DES เดียว และ DES นั้นไม่ไวต่อการโจมตีข้อความธรรมดาที่รู้จักโดยเฉพาะ ซึ่งโดยเฉลี่ยแล้ว $2^{28}$ ขั้นตอน เรายังแสดงให้เห็นว่าขนาดของกลุ่มย่อยที่สร้างโดยชุดการเรียงสับเปลี่ยน DES นั้นมากกว่า $10^{2499}$ซึ่งใหญ่เกินไปสำหรับการโจมตีที่อาจเกิดขึ้นกับ DES ซึ่งจะใช้ประโยชน์จากกลุ่มย่อยขนาดเล็ก

ฉันอ้างว่าสำหรับฟังก์ชันการปัดรหัสของบล็อกคลาสขนาดใหญ่ซึ่งรวมถึงฟังก์ชันการปัดเศษของ AES โครงสร้างการดึงดูดบนพื้นที่แป้นกลมและบนพื้นที่บล็อกนั้นสามารถกำหนดได้จากฟังก์ชันการปัดเศษของบล็อก ดังนั้น automorphisms เดียวที่เป็นไปได้สำหรับ AES และ block ciphers ที่เกี่ยวข้องคือการแปลงเลียนแบบ

กรณีเมื่อ $K$ เป็นกลุ่มที่ดำเนินการเกี่ยวกับ $X$

สมมติว่า $K$ เป็นกลุ่มที่แสดงในกองถ่าย $X$ ที่ไหนสำหรับแต่ละ $k\in K\setminus\{e\}$มีบางอย่าง $x\ ใน X$ กับ $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 }(k^{-1}\cdot x)) =j\cdot k^{-1}\cdot x.$$

โดยเฉพาะการทำแผนที่จาก $K^{4}\คูณ X$ ถึง $X$ ที่กำหนดโดย $(i,j,k,l,x)\mapsto i\cdot j^{-1}\cdot k\cdot l^{-1}\cdot x$ สามารถกำหนดได้ ทีนี้ลองสังเกตดูว่า $ij^{-1}kl^{-1}=e$ ถ้าและถ้า $x=i\cdot j^{-1}\cdot k\cdot l^{-1}\cdot x$ สำหรับทุกอย่าง $x\ ใน X.$ ดังนั้นชุดของทั้งหมด $(w,x,y,z)\in K^{4}$ ที่ไหน $wx^{-1}yz^{-1}=e$ สามารถกำหนดได้ในแง่ของฟังก์ชัน $F$. ดังนั้นฟังก์ชัน $K^{3}\rightarrow K,(x,y,z)\mapsto xy^{-1}z$ สามารถกำหนดได้ในแง่ของฟังก์ชัน $F$. การดำเนินการ $K^{3}\rightarrow K,(x,y,z)\mapsto xy^{-1}z$ เรียกว่าการดำเนินการฮีป และการดำเนินการฮีปอาจถือเป็นการดำเนินการที่คุณสามารถกู้คืนข้อมูลส่วนใหญ่จากกลุ่มได้ แต่คุณกำหนดว่าองค์ประกอบใดของกลุ่มที่เป็นข้อมูลประจำตัวจากการดำเนินการฮีป ในทางกลับกัน คุณสามารถกู้คืนการดำเนินการกลุ่มจากการดำเนินการฮีปพร้อมกับข้อมูลประจำตัวของกลุ่มได้อย่างง่ายดาย การดำเนินการฮีปควรได้รับการพิจารณาว่าเป็นแนวคิดทั่วไปเกี่ยวกับพื้นที่ใกล้เคียงที่ไม่ใช่แบบอะเบลเลียน

ข้อเสนอ: $(\phi,\psi)$ เป็นออโตมอร์ฟิซึ่มของฟังก์ชันทรงกลม $F$. จากนั้นปล่อยให้ $a=\phi(e)$, และปล่อยให้ $L:K\ลูกศรขวา K$ เป็นแผนที่กำหนดโดย $L(k)=a^{-1}\phi(k)$. แล้ว $L$ เป็นกลุ่มออโตมอร์ฟิซึ่ม

ข้อพิสูจน์: สังเกตสิ่งนั้น $\phi(k)=aL(k)$ แต่ละ $k\ ใน K$. ดังนั้น,

$$L(h^{-1}k)=a^{-1}\phi(h^{-1}k)=a^{-1}\phi(เอ๊ะ^{-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).$$

ดังนั้นการทำแผนที่ $L$ เป็นโฮโมมอร์ฟิซึมแบบกลุ่ม เนื่องจาก $\phi$ เป็นแบบสองนัย $L$ เป็น bijective เช่นกัน คิวอีดี

ตอนนี้กำหนด $M(k)=\phi(k)a^{-1}$. แล้ว $M$ เป็น automorphism ที่ $\phi(k)=M(k)a$ สำหรับ $k\ ใน K$. ดังนั้น, $$\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)$ แต่ละ $k\ ใน K$.

กรณีเมื่อ $K$ และ $X$ เป็นกลุ่ม isomorphic และการดำเนินการของกลุ่มคือการคูณซ้าย

เอาเป็นว่าตอนนี้ $K,X$ เป็นกลุ่มและ $\iota:K\ลูกศรขวา X$ เป็นไอโซมอร์ฟิซึม แล้วสมมุติว่าการกระทำของ $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)$ สำหรับทุกอย่าง $k,x$. โดยเฉพาะอย่างยิ่งถ้า $b=\psi(จ)$, แล้ว $$\psi(\iota(k))=\psi(\iota(k)e)=\iota(M(k))\psi(e)=\iota(M(k))b.$$ พูดแตกต่างกันถ้า $x=\iota(k)$, แล้ว $\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\rightarrow X(j,k,x)\mapsto\iota(jk^{-1})x$.

การผันคำกริยาโดย P

ในกรณีที่ $K$ เป็นเพียงการกระทำ $X$ แต่ที่ไหน $X$ ไม่จำเป็นต้องเป็นกลุ่มเราก็มี $$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}$ ทั้งสองต้องเป็น automorphisms กอง

เครือข่าย SP

สมมติว่า $K=U^{n},X=V^{n}$ ที่ไหน $U,V$ เป็นกลุ่มและ $I:U\ลูกศรขวา V$ เป็นไอโซมอร์ฟิซึม สมมติว่า $\iota:K\ลูกศรขวา X$ คือ isomorphism ที่กำหนดโดยปล่อยให้ $\iota((r_{k})_{k})=(I(r_{k}))_{k}$.

อนุญาต $s:V\ลูกศรขวา V$ เป็นผู้คัดค้าน กำหนดแผนที่ $S:V\ลูกศรขวา V$ โดยปล่อยให้ $S((v_{k})_{k})=(s(v_{k}))_{k}$. อนุญาต $\Gamma:X\ลูกศรขวา X$ เป็น automorphism กอง

สมมติว่า $P=\Gamma\circ 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}$ ทั้งสองต้องเป็น automorphisms กอง

อนุญาต $\mathcal{V}=(V,\Omega,\mho)$ เป็นโครงสร้างพีชคณิตที่ $\โอเมก้า\mho$ เป็นการดำเนินการแบบไตรภาคที่กำหนดโดยการให้ $\Omega(x,y,z)=xy^{-1}z,\mho(x,y,z)=s^{-1}[s(x)s(y)^{-1}s (z)]$. แล้ว $\psi$ ต้องเป็นออโตมอร์ฟิซึมของ $\mathcal{V}^{n}$. ตอนนี้เราจะจำกัดความเป็นไปได้สำหรับ automorphisms $\psi$ เมื่อฟังก์ชั่น $s$ ตอบสนองคุณสมบัติที่ดี

เราว่านะ $s$ มีความเบ้แข็งหากเมื่อใดก็ตามที่ $E:\mathcal{V}\times\mathcal{V}\rightarrow\mathcal{V}$ เป็นเอนโดมอร์ฟิซึ่ม การทำแผนที่ $x\mapsto E(e,x)$ เป็นการทำแผนที่คงที่หรือการทำแผนที่ $x\mapsto E(x,e)$ เป็นแผนที่คงที่

ทฤษฎีบท: ถ้าการทำแผนที่ $s$ มีความเบ้-แข็ง แล้วมี bijection $W:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ พร้อมกับ automorphisms $\psi_{0},\dots,\psi_{n-1}$ ของ $\คณิตศาสตร์แคล{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\rightarrow V^{n}$ โดยปล่อยให้ $\text{in}_{j}(r)=(r_{k})_{k=0}^{n-1}$ โดยปล่อยให้ $r=r_{j}$ และ $r_{k}=e$ เมื่อไหร่ก็ตาม $k\neq เจ$. กำหนดแผนที่ $\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}$ เป็น endomorphism สำหรับทุกคน $i,j$ดังนั้นปล่อยให้ $\psi_{i,j}=\text{jn}_{j}\circ\psi\circ\text{in}_{i}$. เนื่องจาก $\mathcal{V}^{n}$ ถูกสร้างขึ้นโดย subalgebras ของแบบฟอร์ม $\text{in}_{i}[\mathcal{V}]$เราสังเกตว่า automorphism $(\theta,\psi)$ ถูกกำหนดโดยเมทริกซ์ของเอนโดมอร์ฟิซึมอย่างสมบูรณ์ $(\psi_{i,j})_{i,j}$ ของ $\คณิตศาสตร์แคล{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}=e$ เมื่อไหร่ก็ตาม $k\not\in\{i,j\}$.

สมมติ $i\neq j$ และ $E=\text{jn}_{k}\circ\psi\circ\text{in}_{i,j}$. แล้ว $E$ เป็นโฮโมมอร์ฟิซึ่มจาก $\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$ระยะ -ary $t$ ในภาษาของ $\คณิตศาสตร์แคล{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_{ n}.$$

เรามี $$(x_{k})_{k=0}^{n-1}=t(\text{in}_{0}(x_{0}),\dots,\text{in}_{n -1}(x_{k}),e),$$ ดังนั้น $$\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)).$$ ดังนั้นจึงมีบางอย่าง $i$ ที่ไหน การทำแผนที่ $\text{jn}_{j}\psi\text{in}_{i'}$ เป็นฟังก์ชันคงที่ทุกเมื่อ $i'\neq ผม.$ ดังนั้นจึงมีฟังก์ชั่น $W:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ ที่สำหรับทั้งหมด $เจ$มี endomorphism บางอย่าง $\psi_{j}:\mathcal{V}\rightarrow\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$ เป็น automorphism และตั้งแต่นั้นมา $\คณิตศาสตร์แคล{V}$ มีขอบเขตจำกัด เรารู้ว่าแต่ละแผนที่ $\psi_{j}$ ต้องเป็นออโตมอร์ฟิซึ่มและแมปด้วย $W$ จะต้องเป็นไบ

คิวอีดี

ทฤษฎีบทข้างต้นระบุว่าเมื่อใดก็ตามที่ $s$ จะเบ้แข็ง, กลุ่ม automorphism ของ $F$ จึงเป็นกลุ่มย่อยของผลิตภัณฑ์พวงหรีดของ $\text{Aut}(\mathcal{V})$ กับกลุ่มสมมาตร $S_{n}$.

เราสามารถรับประกันได้ว่ากลุ่ม automorphism ของ $F$ เชื่องพอสมควรภายใต้สมมติฐานที่แตกต่างกันเกี่ยวกับ S-boxes

อนุญาต $H$ เป็นกลุ่มของการเรียงสับเปลี่ยนของ $X$ สร้างขึ้นโดยการเรียงสับเปลี่ยนทั้งหมดของแบบฟอร์ม $F_{j}\circ F_{k}^{-1},F_{j}^{-1}\circ F_{k}$. ตอนนี้เราจะแสดงให้เห็นว่าภายใต้สมมติฐานที่สมเหตุสมผล การสลายตัวของ $H$ มีผลิตภัณฑ์โดยตรงภายในของกลุ่มที่ย่อยสลายได้โดยตรงไม่ซ้ำกัน

จากทฤษฎีบท Krull-Schmidt เวอร์ชันอ่อน เรารู้ว่าถ้า $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}$, แล้ว $\alpha=\beta$และมีการคัดค้าน $\zeta:\{1,\dots,\alpha\}\rightarrow\{1,\dots,\beta\}$ ที่ไหน $G_{i}\simeq H_{\zeta(i)}$ สำหรับ $1\leq ฉัน\leq\alpha$.

ถ้า $j\ในหน่วย U$จากนั้นให้ $s_{ญ}$ เป็นการเปลี่ยนแปลงของ $วี$ กำหนดโดยปล่อยให้ $s_{j}(v)=I(j)s(v)$ เมื่อไหร่ก็ตาม $v\ใน V$. อนุญาต $H^{-}$ เป็นกลุ่มของการเรียงสับเปลี่ยนของ $วี$ สร้างขึ้นโดยการแมป $s_{j}\circ s_{k}^{-1},s_{j}^{-1}\circ s_{k}$.

บทแทรก: สมมติว่าสำหรับ $1\leq ฉัน\leq n$, $\Delta_{i}$ เป็นกลุ่มที่ไม่ใช่อาเบลเลียนที่มีขอบเขตจำกัด $|\Delta_{i}|>1$ และถ้า $A,B\subseteq\Delta_{i}$ เป็นกลุ่มย่อยเช่นนั้น $ab=ba$ เมื่อไหร่ก็ตาม $a\ในA,b\ในB$ และที่ไหน $\Delta_{i}=AB$แล้วอย่างใดอย่างหนึ่ง $|A|=1$ หรือ $|B|=1.$ แล้วเมื่อไรก็ตาม $\phi:\Delta_{1}\times\dots\times\Delta_{n}\rightarrow\Delta_{1}\times\dots\times\Delta_{n}$ เป็น automorphism มีการเรียงสับเปลี่ยน $\rho$ ของ $\{1,\จุด,n\}$ และมอร์ฟิซึม $\phi_{i}:\Delta_{\rho(i)}\rightarrow\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}$ และ $ab=ba$ เมื่อไหร่ก็ตาม $a\in A_{i},b\in A_{j},i\neq j$ และ $\Delta_{i}=A_{1}\จุด A_{r}$แล้วมีอยู่ $i$ ที่ไหน $\Delta_{i}=A_{i}$ และที่ไหน $|A_{j}|=1$ เมื่อไหร่ก็ตาม $j\neq ฉัน$. ข้อสังเกตนี้เกิดขึ้นได้จากการเหนี่ยวนำ $r$.

สำหรับ $i,j\in\{1,\dots,n\}$, อนุญาต $\pi_{j}:\Delta_{1}\times\dots\times\Delta_{n}\rightarrow\Delta_{j}$ เป็นแผนที่ฉายและให้ $\iota_{i}:\Delta_{i}\rightarrow\Delta_{1}\times\dots\times\Delta_{n}$ เป็นแผนที่รวม แล้วเมื่อไรก็ตาม $i_{1}\neq ผม_{2}$ และ $a\in\pi_{j}[\phi[\iota_{i_{1}}[\Delta_{i_{1}}]]],b\in\pi_{j}[\phi[\iota_{i_ {2}}[\Delta_{i_{2}}]]]$, เรามี $ab=ba$. เนื่องจาก $\Delta_{j}$ ถูกสร้างขึ้นโดยกลุ่มย่อย $\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]$เรารู้ว่าสำหรับทุกคน $เจ$มีอยู่อย่างมากที่สุดหนึ่งรายการ $i$ ที่ไหน $|\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]|>1$ และสำหรับสิ่งนี้ $i$, เรามี $\Delta_{j}=\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]$. กล่าวอีกนัยหนึ่งมีฟังก์ชั่น $\rho:\{1,\dots,n\}\rightarrow\{1,\dots,n\}$ ที่ไหน $\pi_{j}[\phi[\iota_{\rho(j)}[\Delta_{\rho(j)}]]]=\Delta_{j}$ สำหรับทุกอย่าง $เจ$ แต่ที่ไหน $|\pi_{j}[\phi[\iota_{i}[\Delta_{i}]]]|=1$ เมื่อไหร่ก็ตาม $\rho(j)\neq ผม$.

ดังนั้นเราจึงมี $\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)})).$

เนื่องจาก $\phi$ เป็น isomorphism การทำแผนที่ $\rho$ เป็น bijection และ $\pi_{j}\phi\iota_{\rho(j)}$ เป็นไอโซมอร์ฟิซึมจาก $\Delta_{\rho(j)}$ ถึง $\Delta_{j}$ สำหรับทุกอย่าง $เจ$.

คิวอีดี

บทแทรก: สมมุติว่า $G$ เป็นกลุ่มที่แยกตัวประกอบได้เป็นผลิตภัณฑ์โดยตรงภายในของกลุ่มย่อย $\Delta_{1},\dots,\Delta_{m}$. นอกจากนี้ สมมติว่าสำหรับทุกคน $i$, ถ้า $ก,ข$ เป็นกลุ่มย่อยของ $\Delta_{i}$ กับ $ab=ba$ แต่ละ $a\ในA,b\ในB$ และ $\Delta_{i}=AB$. แล้วถ้า $\Delta_{1}^{\sharp},\dots,\Delta_{n}^{\sharp}$ เป็นตัวประกอบอื่นของ $G$ เป็นผลิตภัณฑ์โดยตรงภายในของกลุ่มย่อยแล้ว $m=n$และมีการเปลี่ยนแปลงบางอย่าง $\rho$ ของ $\{1,\จุด,m\}$ ที่ไหน $\Delta_{i}=\Delta_{\rho(i)}^{\sharp}$ สำหรับทุกอย่าง $i$.

บทพิสูจน์: จากทฤษฎีบท Krull-Schmidt เรารู้เรื่องนั้น $m=n$และมีการสับเปลี่ยน $\rho$ ของ $\{1,\จุด,m\}$ ที่ไหน $\Delta_{i}\simeq \Delta_{\rho(i)}^{\sharp}$ สำหรับทุกอย่าง $i$. ดังนั้นจึงมี automorphism บางอย่าง $\phi$ ของ $G$ ที่ไหน $\phi$ จำกัด การทำแผนที่ isomorphism $\Delta_{i}$ ไปยัง $\Delta_{\rho(i)}^{\sharp}$ สำหรับทุกอย่าง $i$. อย่างไรก็ตาม จากบทแทรกข้างต้น เรารู้ว่ามีการเปลี่ยนแปลงบางอย่าง $f$ ของ $\{1,\จุด,m\}$ ที่ไหน $\phi[\Delta_{i}]=\Delta_{f(i)}$ สำหรับทุกอย่าง $i$. ดังนั้น, $\Delta_{\rho(i)}^{\sharp}=\Delta_{f(i)}$ สำหรับทุกอย่าง $i$. คิวอีดี

ทฤษฎีบท: สมมติว่าเมื่อใดก็ตามที่ $ก,ข$ เป็นกลุ่มย่อยของ $H^{-}$ กับ $ab=ba$ สำหรับ $a\ในA,b\ในB$, ทั้ง $|A|=1$ หรือ $|B|=1$. แล้วถ้า $(\phi,\psi)$ เป็น automorphism ของ $F$แล้วมี Bijection $W:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ พร้อมกับ automorphisms $\psi_{0},\dots,\psi_{n-1}$ ของ $\คณิตศาสตร์แคล{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.$

หลักฐาน: สมมติว่า $(\phi,\psi)$ เป็น automorphism ของ $วี$. แล้ว $\psi$ รักษากลุ่ม $H$ ในแง่ที่ว่า $H=\psi H\psi^{-1}$. ดังนั้นหาก $H$ เป็นปัจจัยที่เป็นผลิตภัณฑ์โดยตรงภายในของกลุ่มย่อย $H_{0},\dots,H_{n-1}$จากนั้นกลุ่ม $H$ สามารถกำหนดได้ใน $(F,K,X)$และชุดของกลุ่มย่อย $\{H_{0},\dots,H_{n-1}\}$ ยังสามารถกำหนดได้ใน $(F,K,X)$.

ดังนั้นจึงมีการคัดค้าน $\rho:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ ดังนั้น $H_{\rho(i)}=\psi H_{i}\psi^{-1}$ สำหรับทุกอย่าง $i$. ดังนั้นเราจึงมี $H_{\rho(i)}\psi=\psi H_{i}$.

สมมติว่า $\pi_{0},\dots,\pi_{n-1}:X\ลูกศรขวา V$ เป็นฟังก์ชั่นการฉายภาพ สมมติว่า $\หมวก{H}_{i}$ เป็นกลุ่มที่สร้างขึ้นโดยทั้งหมด $H_{ญ}$เป็นเช่นนั้น $i\neq j$.

แล้ว $\pi_{i}(x)=\pi_{i}(y)$ ถ้าและถ้า $h(x)=y$ สำหรับบางคน $h\in\หมวก{H}_{i}$ ถ้าและถ้า $\psi^{-1}h'\psi(x)=y$ สำหรับบางคน $h'\in\hat{H}_{\rho(i)}$ ถ้าและถ้า $h'\psi(x)=\psi(y)$ สำหรับบางคน $h'\in\psi\hat{H}_{i}\psi^{-1}=\hat{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}$ ต้องเป็นออโตมอร์ฟิซึมของ $\คณิตศาสตร์แคล{V}$.

คิวอีดี

ทฤษฎีบทข้างต้นใช้เมื่อ $H^{-}$ เป็นกลุ่มสลับหรือกลุ่มสมมาตรในชุดมากกว่า $4$ องค์ประกอบ โดยเฉพาะอย่างยิ่ง ทฤษฎีบทข้างต้นใช้กับรหัสบล็อก AES บทพิสูจน์ว่าสำหรับ AES กลุ่ม $H^{-}$ เป็นกลุ่มสลับที่สามารถพบได้ในเอกสารของ Ralph Wernsdorf ที่พิสูจน์ว่าการเรียงสับเปลี่ยนแบบกลมของรหัสบล็อก AES ทำให้เกิดกลุ่มสลับของการเรียงสับเปลี่ยนทั้งหมดของ $\{1,\dots,2^{128}\}.$