滿足 SAC 的簡單可逆算法
有哪些簡單的算法…
- 對固定大小的塊進行操作（或者可以很容易地這樣做），即輸入塊具有固定大小，例如 256 位，輸出是相同大小的塊
- 是可逆的（不能是雜湊函式）
- 滿足嚴格的雪崩準則 (SAC)
我對任何其他加密屬性不感興趣。它不必是安全密碼。
我在非常籠統的意義上使用*簡單這個詞。*我對大多數工程師稱之為簡單、易於在軟體和/或硬體中實現的任何東西感興趣，儘管可能與計算複雜度等明確定義的度量相關。
我考慮過 AES 或像 SHA-256 這樣的散列函式，我相信它會表現出強烈的雪崩效應（不確定它們是否滿足 SAC），但是散列函式是不可逆的，如果您不需要算法，AES 似乎不必要地複雜成為一個安全的密碼。我想一定有更簡單的東西。當然，我可能會弄錯。
一種簡單的方法是，如果您的輸入/輸出大小是 $ n $ 位，是選擇一個表示 $ GF(2^n) $ , 和一個隨機的非零值 $ v $ ，並讓你的功能是 $ F(u) = u \times v $ （在哪裡 $ \times $ 是乘法 $ GF(2^n) $ )
- 它對固定大小的塊進行操作
- 它是可逆的（乘以值 $ v^{-1} $ )
- 它在這個意義上滿足 SAC：對於輸入位 $ i $ ，以及任何輸出位 $ j $ , 翻轉位 $ i $ 輸入將翻轉位 $ j $ 的輸出幾乎正好是一半，也就是說， $ 2^{n-1}/(2^n-1) \approx 1/2 + 2^{-(n+1)} $
現在，它不滿足固定值的 SAC $ v $ ; 對於固定值，翻轉位 $ i $ 會翻轉位 $ j $ 總是或從不；所以，它可能不是您正在尋找的答案（另一方面，它可能）
布爾函式 $ f:\mathbb{F}_2^n \rightarrow \mathbb{F}_2 $ 其 Hadamard 係數均等於 $ \pm 2^{n/2} $ 被稱為彎曲函式，顯然 $ n $ 必須是均勻的。
這樣的函式滿足最大強度的傳播準則，即
對於任何非零向量 $ a $ 功能 $ f(x \oplus a)+f(x) $ 是平衡的。但功能本身並不平衡。
拿 $ n $ 並行彎曲功能，您擁有的不僅僅是您想要的。如果你想要的只是 SAC，那麼只有上面的向量屬性 $ a $ 漢明權重 1 就足夠了。
已經探索了此類函式的其他屬性，例如線性結構、非線性等。這裡的論文是一個很好的密碼學起點。有數百個對彎曲函式的引用，但大多數不需要與加密相關。