บล็อกวัตถุประสงค์ cipher รอบมาตรการรักษาความปลอดภัย

จริงๆ แล้วโครงสร้างค่อนข้างน้อยสามารถกำหนดได้ในแง่ของฟังก์ชัน block cipher round และจากโครงสร้างนี้ เราสามารถสร้างค่าคงที่ของฟังก์ชัน block cipher round ที่วัดความปลอดภัยในการเข้ารหัสได้

ส่วนหนึ่งของคำตอบนี้เหมือนกับของฉัน คำตอบก่อนหน้าที่นี่ดังนั้น ในกรณีนี้ เราจะละเว้นการพิสูจน์ผลลัพธ์

ถ้า $G,H$ เป็นกลุ่มแล้วเราเรียกว่าฟังก์ชัน $\phi:G\rightarrow H$ เป็นโฮโมมอร์ฟิซึ่มแบบฮีป ถ้ามีโฮโมมอร์ฟิซึ่มแบบกลุ่ม $\psi:G\ลูกศรขวา H$ พร้อมด้วยก $b\ในสกุลเงิน H$ ที่ไหน $\phi(g)=b\psi(g)$ สำหรับทุกอย่าง $b\ใน B.$ เทียบเท่าแผนที่ $\phi:G\rightarrow H$ เป็นโฮโมมอร์ฟิซึ่มแบบฮีปถ้าหากว่า $\phi(xy^{-1}z)=\phi(x)\phi(y)^{-1}\phi(z)$ เมื่อไหร่ก็ตาม $x,y,z\ใน G$. กล่าวกันว่า bijective heap homomorphism เป็น heap automorphism

สำหรับกระทู้นี้ขอ $U_{0},\dots,U_{n-1},V_{0},\dots,V_{n-1}$ เป็นกลุ่ม สมมติว่า $I_{i}:U_{i}\rightarrow V_{i}$ เป็นมอร์ฟิซึ่มแบบกลุ่มเมื่อไรก็ได้ $0\leq ฉัน<n$. อนุญาต $K=U_{0}\times\dots\times U_{n-1},X=V_{0}\times\dots\times V_{n-1}$. จากนั้นกำหนดมอร์ฟิซึมแบบกลุ่ม $\iota:K\ลูกศรขวา X$ โดยปล่อยให้ $\iota(u_{0},\dots,u_{n-1})=(I_{0}(u_{0}),\dots,I_{n-1}(u_{n-1})) $.

ถ้า $0\leq ฉัน<n$จากนั้นให้ $s_{i}:V_{i}\rightarrow V_{i}$ เป็นการโต้แย้งโดยพลการ กำหนดแผนที่ $S:V_{0}\times\dots\times V_{n-1}\rightarrow V_{0}\times\dots\times V_{n-1}$ โดยปล่อยให้ $S(v_{0},\dots,v_{n-1})=(s_{0}(v_{0}),\dots,s_{n-1}(v_{n-1}))$. อนุญาต $\Gamma:X\ลูกศรขวา X$ เป็น automorphism กอง อนุญาต $P=\Gamma\circ S$และกำหนดการแม็ป $F:K\times X\rightarrow X$ โดยปล่อยให้ $F(k,x)=\iota(k)P(x)$.

โจทย์: การแม็ป $K^{2}\times X\rightarrow X,(j,k,x)\mapsto\iota(jk^{-1})x$ และ $X^{3}\rightarrow X,(x,y,z)\mapsto xy^{-1}z$ สามารถกำหนดลำดับแรกได้ใน $(K,X,F)$.

อนุญาต $\pi_{i}:X\rightarrow V_{i}$ เป็นกลุ่มโฮโมมอร์ฟิซึ่ม อนุญาต $\simeq_{i}$ เป็นความสัมพันธ์สมมูลบน $X$ ที่เราตั้งไว้ $x\simeq_{i}y$ ถ้าและถ้า $\pi_{i}(x)=\pi_{i}(y)$. ฉันอ้างว่าเซตของความสัมพันธ์สมมูล $\{\simeq_{0},\dots,\simeq_{n-1}\}$ ลำดับที่สูงขึ้นสามารถกำหนดได้ใน $(K,X,F)$ ภายใต้สมมติฐานที่สมเหตุสมผลเกี่ยวกับรหัสบล็อก $F$แต่เพื่อพิสูจน์คำกล่าวอ้างนี้ เราจะต้องทบทวนคำหลักสองสามคำ จากการนิยามของ $\{\simeq_{0},\dots,\simeq_{n-1}\}$เราสามารถสร้างค่าคงที่ของฟังก์ชันรอบรหัสตัวเลขหลายบล็อกที่วัดความไม่เป็นเส้นตรงและเอฟเฟกต์หิมะถล่ม

สำหรับ $0\leq ฉัน<n$, และ $j\in U_{i}$, อนุญาต $s_{i}^{j}$ เป็นการเปลี่ยนแปลงของ $V_{i}$ กำหนดโดยปล่อยให้ $s_{i}^{j}(v)=I_{i}(j)s_{i}(v)$.

ถ้า $0\leq ฉัน<n$จากนั้นให้ $H_{i}$ เป็นกลุ่มของการเรียงสับเปลี่ยนทั้งหมดของ $V_{i}$ ที่สร้างขึ้นโดย $s_{i}^{j}\circ(s_{i}^{k})^{-1},(s_{i}^{j})^{-1}\circ s_{i}^{ k}$.

อนุญาต $H$ เป็นกลุ่มของการเรียงสับเปลี่ยนทั้งหมดของ $X$ สร้างขึ้นโดยการเรียงสับเปลี่ยนทั้งหมดของแบบฟอร์ม $F_{j}^{-1}\circ F_{k},F_{j}\circ F_{k}^{-1}$. สังเกตสิ่งนั้น $F_{j}\circ F_{k}^{-1}(x)=\iota(jk^{-1})(x)$ และ $F_{j}^{-1}\circ F_{k}(x)=S^{-1}[\Gamma^{-1}[\iota(j^{-1}k)]S(x )]$. โดยเฉพาะอย่างยิ่ง, $H$ ถูกสร้างขึ้นโดยการเรียงสับเปลี่ยนของแบบฟอร์ม $x\mapsto\iota(m)(x)$ พร้อมกับการเรียงสับเปลี่ยนของแบบฟอร์ม $S^{-1}[\iota(m)S(x)]$. กล่าวต่างกันว่า $H$ ถูกสร้างขึ้นโดยการเรียงสับเปลี่ยนของแบบฟอร์ม $$(x_{0},\dots,x_{n-1})\mapsto(I_{0}(m_{0})(x_{0}),\dots,I_{n-1}(m_{ n-1})(x_{n-1}))$$ และ $$(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} ))]).$$ ดังนั้น, $H$ ประกอบด้วยการเรียงสับเปลี่ยนทั้งหมดของแบบฟอร์ม $h_{0}\times\dots\times h_{n-1}$ ที่ไหน $h_{i}\ใน H_{i}$ เมื่อไหร่ก็ตาม $0\leq ฉัน<n$.

ดังนั้น $H\simeq H_{0}\times\dots\times H_{n-1}$ เป็นผลิตภัณฑ์โดยตรงภายนอก เรายังเขียนได้ $H$ เป็นผลิตภัณฑ์โดยตรงภายใน $H_{0}^{\sharp},\dots,H_{n-1}^{\sharp}$ ที่ไหน $H_{i}^{\sharp}$ ประกอบด้วยการแมปทั้งหมด $h\ ใน H$ ที่ไหนถ้า $h_{0},\dots,h_{n-1}$ เป็นแมปที่ไหน $h(x_{0},\dots,x_{n-1})=(h_{0}(x_{0}),\dots,h_{n-1}(x_{n-1}))$ สำหรับทุกอย่าง $x_{0},\dots,x_{n-1}$, แล้ว $h_{j}$ เป็นฟังก์ชันประจำตัวเมื่อใดก็ได้ $j\neq ฉัน$. แล้ว $H_{i}^{\sharp}\simeq H_{i}$ เมื่อไหร่ก็ตาม $0\leq ฉัน<n.$

เราว่ากลุ่ม $G$ จะสลายตัวไม่ได้ถ้าเมื่อใดก็ตามที่ $ก,ข$ เป็นกลุ่มย่อยของ $G$ กับ $ab=ba$ เมื่อไหร่ก็ตาม $a\ในA,b\ในB$ และ $G=AB$, แล้ว $|A|=1$ หรือ $|B|=1$ (แจ้งให้เราทราบในความคิดเห็นหากคุณนึกถึงคำที่ดีกว่า 'superindecomposible')

ทฤษฎีบท (ครูล-ชมิดต์): สมมติว่า $G$ เป็นกลุ่มที่เป็นไปตามเงื่อนไขของห่วงโซ่จากน้อยไปหามากและจากมากไปน้อยของเงื่อนไขของห่วงโซ่ในกลุ่มย่อยปกติ (กลุ่มจำกัดใด ๆ เป็นไปตามคุณสมบัตินี้) อนึ่ง สมมุติว่า $G$ ถูกเขียนเป็นผลิตภัณฑ์โดยตรงภายในของกลุ่มย่อยที่แยกย่อยไม่ได้โดยตรงที่ไม่สำคัญในสองวิธีที่แตกต่างกัน ได้แก่ $G=G_{0}\times\dots\times G_{n-1}$ และ $G=H_{0}\times\dots H_{n-1}$. จากนั้นมีการเปลี่ยนแปลง $\rho$ ของ $\{0,\จุด,n-1\}$ ดังนั้น $G_{i}\simeq H_{\rho(i)}$ สำหรับ $0\leq ฉัน<n$ และที่ไหน $$G=G_{0}\times\dots\times G_{r}\times H_{\rho(r+1)}\times\dots H_{\rho(n-1)}$$ เมื่อไหร่ก็ตาม $0\leq r\leq n-1$.

บทแทรก: สมมุติว่า $G$ เป็นกลุ่มที่แน่นอน ถ้า $G$ เป็นผลิตภัณฑ์โดยตรงภายในของกลุ่มย่อยที่แยกย่อยไม่ได้ เมื่อใดก็ตามที่เราแยกตัวประกอบ $G$ เป็นผลิตภัณฑ์โดยตรงภายใน $G=G_{0}\times\dots\times G_{m-1}$ และ $G=H_{0}\times\dots\times H_{n-1}$, แล้ว $m=n$และมีการเปลี่ยนแปลงบางอย่าง $\rho:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ ที่ไหน $H_{i}=G_{\rho(i)}$ สำหรับ $0\leq ฉัน<n$.

ทฤษฎีบท: มีสูตรลำดับที่สูงกว่าอยู่ $\phi$ เช่นนั้นหากกลุ่ม $H_{0},\dots,H_{n-1}$ นั้นไม่สามารถย่อยสลายได้ $(K,X,F)\models\phi(z)$ ถ้าและถ้า $z=\{\simeq_{0},\dots,\simeq_{n-1}\}$.

หลักฐาน: สังเกตว่ากลุ่ม $H$ ลำดับที่สูงขึ้นสามารถกำหนดได้ในโครงสร้าง $(K,X,F)$. นอกจากนี้กลุ่ม $H$ มีการแยกตัวประกอบแบบเรียงสับเปลี่ยนที่ไม่เหมือนใคร $H^{\sharp}_{0}\times\dots\times H^{\sharp}_{n-1}$ เป็นปัจจัยที่แยกย่อยไม่ได้ ดังนั้นชุดของปัจจัยที่แยกย่อยไม่ได้ทั้งหมด $\{H^{\sharp}_{0},\dots,H^{\sharp}_{n-1}\}$ สามารถกำหนดได้ใน $(K,X,F)$. ตอนนี้สำหรับแต่ละคน $i$, อนุญาต $\หมวก{\simeq}_{i}$ เป็นความสัมพันธ์สมมูลที่เราตั้งไว้ $x\hat{\simeq}_{i}y$ ถ้าและถ้า $h(x)=y$ สำหรับบางคน $h\in H^{\sharp}_{i}$. อนุญาต $\simeq_{i}$ เป็นความสัมพันธ์สมมูลบน $X$ ที่สร้างขึ้นโดย $\bigcup\{\hat{\simeq}_{j}\กลาง j\neq i\}$. แล้ว $\{\simeq_{0},\dots,\simeq_{n-1}\}$ กำหนดได้จาก $\{H^{\sharp}_{0},\dots,H^{\sharp}_{n-1}\}$. ดังนั้นชุด $\{\simeq_{0},\dots,\simeq_{n-1}\}$ สามารถกำหนดได้ใน $(K,X,F)$. $\สแควร์$

จากการนิยามของ $\{\simeq_{0},\dots,\simeq_{n-1}\}$เราสามารถกำหนดค่าไม่แปรเปลี่ยนของฟังก์ชันรอบรหัสตัวเลขได้ค่อนข้างน้อย

ถ้า $T_{1},T_{2}$ เป็นกลุ่มและ $f_{i}:T_{i}\rightarrow T_{i}$ สำหรับ $i\in\{1,2\}$แล้วเราค่อยว่ากัน $f_{1},f_{2}$ จะเทียบเท่ากันหากมี heap automorphisms อยู่ $L_{1}:T_{1}\rightarrow T_{2},L_{2}:T_{2}\rightarrow T_{1}$ ที่ไหน $f_{2}=L_{1}f_{1}L_{2}$. เราบอกว่าแผนที่ $M$ ไม่แปรเปลี่ยนภายใต้การสมมูลเชิงเปรียบเทียบ ถ้า $M(f)=M(g)$ เมื่อไหร่ก็ตาม $ฉ,ก$ มีความเท่าเทียมกัน

เราว่าคู่กันนะ $(k,\เดลต้า)$ เป็น S-boxification ถ้า $\เดลต้า$ เป็น automorphism กองและเมื่อใดก็ตามที่ $x\simeq_{i}y$, แล้ว $\Delta\circ F_{k}(x)\simeq_{i}\Delta\circ F_{k}(y)$. คอลเลกชันของ S-boxifications ทั้งหมดเป็นลำดับที่สูงขึ้นซึ่งกำหนดได้ใน $(K,X,F)$. สังเกตว่ามี S-boxification อยู่ นั่นคือการทำแผนที่ $(e,\Gamma^{-1})$. เอาเป็นว่าตอนนี้ $(k,\เดลต้า)$ เป็น S-boxification แล้วมันก็ง่ายที่จะแสดงให้เห็นว่าแต่ละ $\simeq_{i}$ เป็นความเห็นพ้องต้องกันกับ $\Delta\Gamma^{-1}$. ดังนั้น $\Delta=E\Gamma^{-1}$ สำหรับ automorphism กอง $E$ แต่ละที่ $\simeq_{i}$ เป็นความเห็นพ้องต้องกันกับ $E$. ดังนั้น, $\Delta\circ F_{k}=E'\circ S$ สำหรับ automorphism กอง $E'$. ดังนั้นพีชคณิตเชาวน์ $(X,\Delta\circ F_{k})/\simeq_{i}$ เทียบเท่ากับ $(V_{i},s_{i})$ สำหรับ $0\leq ฉัน<n$. จากการสังเกตเหล่านี้ เราได้ข้อเท็จจริงดังต่อไปนี้

ข้อเท็จจริง: หากการทำแผนที่ $M$ ไม่แปรผันภายใต้การสมมูลที่ใกล้เคียงกันและกำหนดได้ในตรรกะลำดับที่สูงกว่า จากนั้นจึงทำการแมป $M^{+}$ กำหนดโดยปล่อยให้ $M^{+}(F)=\{M(s_{0}),\dots,M(s_{n-1})\}$ ลำดับที่สูงขึ้นสามารถกำหนดได้ในโครงสร้าง $(K,X,F)$. ดังนั้น, $M^{+}$ เป็นพารามิเตอร์ที่ไม่แปรผันของฟังก์ชันแบบกลม