Предположим, что $F:K\раз X\стрелка вправо X$ функция такая, что для каждого $к\в К$, отображение $F_{k}:X\стрелка вправо X$ определяется, позволяя $F_{к}(х)=F(к,х)$ является биекцией. Предположим, что $F$ это функция раунда для некоторой криптографической функции, такой как блочный шифр или криптографическая хеш-функция. Позволять $V_{X}$ — комплексное векторное пространство, состоящее из всех кортежей $(\alpha_{x})_{x\in X}$ такой, что $\sum_{x\in X}\alpha_{x}=0$. Задайте неприводимое линейное представление $\фи$ группа перестановок $S_{X}$ на $V_{X}$ позволив $\phi(f)(\alpha_{x})_{x\in X})=(\alpha_{f(x)})_{x\in X}$.
Задайте линейное преобразование $L_{F}=\sum_{k\in K}\phi(F_{k})$.
Если перестановки $F_{к}$ случайны и выбираются независимо друг от друга, то круговой закон кажется верным для линейного преобразования $L_{F}$, поэтому собственные значения $L_{F}$ должны быть примерно равномерно распределены по диску $\{z\in\mathbb{C}:|z|^{2}\leq |K|\}$, а спектральный радиус $L_{F}$ должен быть рядом $\sqrt{|К|}$. Конечно, на практике круглые функции $F_{к}$ являются неслучайными для функций раунда блочного шифра $F$. Кажется, было бы неплохо попытаться сделать спектральный радиус $L_{F}$ достаточно низким, чтобы случайные величины $Z_{n}$ как униформа на $Х^{2}$ насколько это возможно, где значение $Z_{n}$ это случайная пара $(х,у)$ куда $х$ выбирается из $Х$ равномерно случайным образом и $y=F_{k_{1}}\dots F_{k_{n}}(x)$ для случайно и независимо выбранных $k_{1},\dots,k_{n}\in K$.
Теперь есть случаи, когда $L_{F}$ является нильпотентным по весьма тривиальным причинам. Например, если $F(k,x)=k\oplus g(x)$ для некоторой перестановки $г$ (как в случае с AES), то $L_{F}$ является нильпотентным. Можно также убедиться, что $L_{F}$ является нильпотентным для некоторых функций блока шифра Фейстеля $F$.
Есть ли какое-либо вычисление или оценка спектрального радиуса или распределения собственных значений $L_{F}$ для функций раунда для SHA-256 или любого другого современного блочного шифра или криптографической хеш-функции $F$ куда $L_{F}$ не является нильпотентным?
Математическая терминология
$S_{X}$ это группа всех перестановок из $Х$ к $Х$.
Если $В,В$ являются векторными пространствами, то пусть $\text{Hom}(V,W)$ — множество всех линейных преобразований $L:V\стрелка вправо W$. Если $G$ это группа, и $В$ является векторным пространством, то линейное представление
из $G$ в векторном пространстве $В$ это функция $\phi:G\стрелка вправо\текст{Hom}(V,V)$ такой, что $\фи(г)\цирк\фи(ч)=\фи(гх)$ в любое время $г,ч\в G$. Мы говорим, что $\фи$ неприводимо, не существует собственного нетривиального подпространства $W$ из $В$ такой, что $\фи(г)(ш)\в W$ в любое время $w\in W$.
Если $А$ является квадратной матрицей, то собственное значение $А$ является скаляром $\лямбда$ такой, что $А\mathbf{х}=\лямбда\mathbf{х}$ для некоторого ненулевого вектора $\mathbf{х}$.
Если $А$ представляет собой квадратную матрицу с действительными или комплексными элементами, затем определите спектральный радиус $\сигма(А)$ из $А$ быть $$\max\{|\lambda|:\text{$\lambda$ является собственным значением $A$}\}.$$
Предположим, что $К$ поле действительных или комплексных чисел и $В$ векторное пространство над полем $К$. Норма в векторном пространстве $В$ это функция $\|\cdot\|:V\стрелка вправо[0,\infty)$ такой, что если $\alpha\in K,\mathbf{x},\mathbf{y}\in V$, тогда
$\|\alpha\cdot\mathbf{x}\|=|\alpha|\cdot\|\mathbf{x}\|,$
$\mathbf{x}\neq 0$ если и только если $\|\mathbf{x}\|>0$, и
$\|\mathbf{x}+\mathbf{y}\|\leq\|\mathbf{x}\|+\|\mathbf{y}\|$.
Оказывается, спектральный радиус всегда
$$\sigma(A)=\lim_{n\стрелка вправо\infty}\sqrt[n]{\|A^{n}\|}$$
независимо от выбранной нормы.
Мы говорим, что $n\n$ матрица $А$ нильпотентна, если она удовлетворяет одному из следующих свойств:
$А^{п}=0$.
$А^{к}=0$ для некоторых $к$.
Все собственные значения $А$ находятся $0$.
Спектральный радиус $А$ является $0$.
