Позволять $К,Х$ быть наборы и пусть $F:K\раз X\стрелка вправо X$ быть функцией. Для каждого $к\в К$, позволять $f_{k}:X\стрелка вправо X$ быть функцией, где $f_{k}(x)=F(k,x)$ в любое время $k\in K,x\in X$. Предположим, что каждый $f_{k}$ является биекцией.
Предположим, что $F$ это функция раунда для некоторой криптографической функции, такой как AES-128 или какой-либо криптографической функции.
Если $F$ является криптографической функцией, то я не ожидаю $\{f_{k}\mid k\in K\}$ для создания полной симметричной группы $S_{X}$, но я ожидал бы для $\{f_{k}\mid k\in K\}$ для генерации чередующейся группы $А_{Х}$ (дайте мне знать, если есть реальные примеры, когда $f_{k}$ нечетная перестановка). Были ли в криптографии случаи, когда было строго доказано, что $\{f_{k}\mid k\in K\}$ генерирует или не генерирует чередующуюся группу $А_{Х}$? Например, если
$F$ функция раунда для AES-128 или DES, тогда $\{f_{k}|k\in K\}$ генерировать чередующуюся группу $А_{Х}$?
Меня в основном интересует случай, когда функции $f_{k}$ являются круглыми функциями, потому что этот случай, вероятно, будет легче анализировать, и потому что, если функции $f_{k}$ — круглые функции, то более вероятно, что $\{f_{k}\mid k\in K\}$ генерирует чередующуюся группу.
Эта проблема может быть неразрешимой в большинстве случаев, но могут быть случаи, когда можно показать, что
$\{f_{k}\mid k\in K\}$ генерирует чередующуюся группу $А_{Х}$ например, устаревшая или небезопасная криптография, или когда криптография имеет особую форму, облегчающую анализ (например, шифры Фейстеля), или даже криптографические алгоритмы, предназначенные для тестирования.
Мы говорим, что подгруппа $G$ группы перестановок $S_{X}$ является $n$-транзитивный, если всякий раз $x_{1},\dots,x_{n}$ являются отдельными элементами в $Х$ и $y_{1},\dots,y_{n}$ являются отдельными элементами в $Х$, то есть некоторая $г\в G$ с $г(х_{я})=у_{я}$ в любое время $1\leq i\leq n$.
Теорема: Предположим, что $Х$ конечен и $|Х|>24$. Если $G$ это
$4$-транзитивная подгруппа $S_{X}$, то либо $G=S_{X}$ или же
$G=A_{X}$.
Приведенная выше теорема может упростить доказательство того, что $G=A_{X}$.
Если $\{f_{k}\mid k\in K\}$ не генерирует чередующуюся группу $А_{Х}$, то я бы отказался от любого блочного шифра с циклической функцией $F$ как ужасно небезопасный, поскольку либо $|X|\leq 24$ что слишком мало для любого блочного шифра или группы, сгенерированной $\{f_{k}\mid k\in K\}$ не является 4-транзитивным.
Однако, если легко или легко доказать, что $\{f_{k}\mid k\in K\}$ генерирует чередующуюся группу $А_{Х}$, то функция $F$ может вести себя слишком хорошо для криптографических целей.
