Lăsa $K,X$ fi seturi și lasă $F:K\ori X\săgeata la dreapta X$ fi o funcție. Pentru fiecare $k\în K$, lăsa $f_{k}:X\săgeată la dreapta X$ fi funcția unde $f_{k}(x)=F(k,x)$ oricând $k\în K,x\în X$. Să presupunem că fiecare $f_{k}$ este o bijectie.
Să presupunem că $F$ este funcția rotundă pentru o funcție criptografică, cum ar fi AES-128 sau o funcție criptografică.
Dacă $F$ este o funcție criptografică, atunci nu mă aștept la $\{f_{k}\mid k\in K\}$ pentru a genera întregul grup simetric $S_{X}$, dar m-as astepta la $\{f_{k}\mid k\in K\}$ pentru a genera grupul alternant $A_{X}$ (anunțați-mă dacă există exemple din lumea reală unde $f_{k}$ este o permutare ciudată). Au existat cazuri în criptografie în care s-a dovedit riguros că? $\{f_{k}\mid k\in K\}$ generează sau nu generează grupul alternativ $A_{X}$? De exemplu, dacă
$F$ este funcția rotundă pentru AES-128 sau DES, apoi face $\{f_{k}|k\în K\}$ generează grupul alternativ $A_{X}$?
Ma intereseaza mai ales cazul in care functiile $f_{k}$ sunt functiile rotunde pentru ca acest caz probabil va fi mai usor de analizat si pentru ca daca functiile $f_{k}$ sunt funcțiile rotunde, atunci este mai probabil ca $\{f_{k}\mid k\in K\}$ generează grupul alternant.
Această problemă poate fi insolubilă în majoritatea cazurilor, dar pot exista cazuri în care se poate demonstra asta
$\{f_{k}\mid k\in K\}$ generează grupul alternant $A_{X}$ precum criptografia învechită sau nesigură sau când criptografia are o formă specială care face mai ușor de analizat (cum ar fi cifrurile Feistel) sau chiar algoritmi criptografici care sunt proiectați pentru testare.
Spunem că un subgrup $G$ a grupului de permutare $S_{X}$ este $n$-tranzitiv dacă oricând $x_{1},\dots,x_{n}$ sunt elemente distincte în $X$ și $y_{1},\dots,y_{n}$ sunt elemente distincte în $X$, apoi mai sunt unele $g\în G$ cu $g(x_{i})=y_{i}$ oricând $1\leq i\leq n$.
Teoremă: Să presupunem că $X$ este finită și $|X|>24$. Dacă $G$ este o
$4$-subgrupul tranzitiv al $S_{X}$, atunci fie $G=S_{X}$ sau
$G=A_{X}$.
Teorema de mai sus poate facilita demonstrarea acestui lucru $G=A_{X}$.
Dacă $\{f_{k}\mid k\in K\}$ nu generează grupul alternativ $A_{X}$, atunci aș respinge orice cifru bloc cu funcție rotundă $F$ ca fiind oribil de nesigur de vreme ce fie $|X|\leq 24$ care este prea mic pentru orice cifru bloc sau grupul generat de $\{f_{k}\mid k\in K\}$ nu este 4-tranzitiv.
Cu toate acestea, dacă este ușor sau ușor să demonstrezi asta $\{f_{k}\mid k\in K\}$ generează grupul alternant $A_{X}$, apoi funcția $F$ poate fi prea bine comportat în scopuri criptografice.
