กลุ่มที่สร้างโดยฟังก์ชันรอบสร้างกลุ่มสลับหรือไม่

อนุญาต $K,X$ เป็นชุดและปล่อยให้ $F:K\times X\rightarrow X$ ให้เป็นหน้าที่ แต่ละ $k\ ใน K$, อนุญาต $f_{k}:X\ลูกศรขวา X$ เป็นฟังก์ชั่นที่ $f_{k}(x)=F(k,x)$ เมื่อไหร่ก็ตาม $k\in K,x\in X$. ถือว่าแต่ละ $f_{k}$ คือการประนีประนอม

สมมติว่า $F$ เป็นฟังก์ชันรอบสำหรับฟังก์ชันการเข้ารหัสบางอย่าง เช่น AES-128 หรือฟังก์ชันการเข้ารหัสบางอย่าง

ถ้า $F$ เป็นฟังก์ชั่นการเข้ารหัสแล้วฉันไม่คาดหวัง $\{f_{k}\กลาง k\in K\}$ เพื่อสร้างกลุ่มสมมาตรแบบเต็ม $S_{X}$แต่ฉันคาดหวังสำหรับ $\{f_{k}\กลาง k\in K\}$ เพื่อสร้างกลุ่มสำรอง $A_{X}$ (โปรดแจ้งให้เราทราบหากมีตัวอย่างในโลกแห่งความเป็นจริงที่ใด $f_{k}$ เป็นการเรียงสับเปลี่ยนคี่) มีกรณีใดบ้างในการเข้ารหัสที่ได้รับการพิสูจน์อย่างเข้มงวดว่า $\{f_{k}\กลาง k\in K\}$ สร้างหรือไม่สร้างกลุ่มสลับ $A_{X}$? ตัวอย่างเช่น ถ้า $F$ เป็นฟังก์ชันปัดเศษสำหรับ AES-128 หรือ DES แล้วทำ $\{f_{k}|k\in K\}$ สร้างกลุ่มสลับ $A_{X}$?

ฉันสนใจในกรณีที่ฟังก์ชั่นเป็นหลัก $f_{k}$ เป็นฟังก์ชันรอบเพราะกรณีนี้น่าจะวิเคราะห์ได้ง่ายกว่าและเพราะถ้าเป็นฟังก์ชัน $f_{k}$ เป็นฟังก์ชันกลมๆ แล้ว ก็มีแนวโน้มว่า $\{f_{k}\กลาง k\in K\}$ สร้างกลุ่มสลับ

ปัญหานี้อาจแก้ไขได้ยากในกรณีส่วนใหญ่ แต่อาจมีบางกรณีที่สามารถแสดงให้เห็นได้ $\{f_{k}\กลาง k\in K\}$ สร้างกลุ่มสลับ $A_{X}$ เช่น การเข้ารหัสที่ล้าสมัยหรือไม่ปลอดภัย หรือเมื่อการเข้ารหัสมีรูปแบบพิเศษที่ช่วยให้วิเคราะห์ได้ง่ายขึ้น (เช่น Feistel ciphers) หรือแม้แต่อัลกอริธึมการเข้ารหัสที่ออกแบบมาเพื่อการทดสอบ

เราว่ากลุ่มย่อย $G$ ของกลุ่มการเปลี่ยนแปลง $S_{X}$ เป็น $n$- สกรรมกริยาถ้าเมื่อใดก็ตามที่ $x_{1},\dots,x_{n}$ เป็นองค์ประกอบที่แตกต่างกันใน $X$ และ $y_{1},\จุด,y_{n}$ เป็นองค์ประกอบที่แตกต่างกันใน $X$แล้วมีบางอย่าง $g\ใน G$ กับ $g(x_{i})=y_{i}$ เมื่อไหร่ก็ตาม $1\leq ฉัน\leq n$.

ทฤษฎีบท: สมมติว่า $X$ มีขอบเขตและ $|X|>24$. ถ้า $G$ คือ $4$- กลุ่มย่อยสกรรมกริยาของ $S_{X}$แล้วอย่างใดอย่างหนึ่ง $G=S_{X}$ หรือ $G=A_{X}$.

ทฤษฎีบทข้างต้นอาจทำให้พิสูจน์ได้ง่ายขึ้น $G=A_{X}$.

ถ้า $\{f_{k}\กลาง k\in K\}$ ไม่สร้างกลุ่มสลับ $A_{X}$จากนั้นฉันจะปฏิเสธรหัสบล็อกใด ๆ ที่มีฟังก์ชันปัดเศษ $F$ เนื่องจากไม่ปลอดภัยอย่างน่ากลัวเช่นกัน $|X|\leq 24$ ซึ่งเล็กเกินไปสำหรับรหัสบล็อกหรือกลุ่มที่สร้างโดย $\{f_{k}\กลาง k\in K\}$ ไม่ใช่ 4 สกรรมกริยา

แต่ถ้าพิสูจน์ได้ง่ายหรือยาก $\{f_{k}\กลาง k\in K\}$ สร้างกลุ่มสลับ $A_{X}$แล้วฟังก์ชัน $F$ อาจมีพฤติกรรมที่ดีเกินไปสำหรับวัตถุประสงค์ในการเข้ารหัส