用數學代替 s-box - 好主意還是壞主意？

在過去的一周裡，以下內容一直在我的腦海中縈繞。如果密碼學界普遍知道我的想法，那麼有人會提供一兩個連結。即使我犯了一個經典的新手錯誤。

加密內部函式的操作類似於 $ x=f(x) $ 可以是table lookup s box 和inverse s box 作為一個單獨的表。一個 16 位的 sbox 和它的逆可以用一點數學和沒有表來實現。使用素數 $ m = (2^{16})+1 $ . 然後選擇常量 $ p $ 和 $ q $ 這樣遞歸

Seed = Seed * p % m;

觸及所有值，1.. $ 2^{16} $ . 然後選擇 $ q $ 這樣 $ p * q mod m = 1 $ .

p = 49374; // example values
q = 32065;
y = ((x+1) * p % m)-1; // forward
x = ((y+1) * q % m)-1; // reverse
// x+1 puts the 16-bit x into the range (1..2^16) where the recursion works.
// the -1 at the end makes the result fit in 16 bits.

有超過 32000 個值 $ p $ 遞歸觸及所有 $ 2^{16} $ 價值觀。

“Mod 0x10001”只需減法即可實現。不需要實際的劃分。這是一個好的加密算法的合理部分嗎？也許要替換 2 個 8 位 s 盒表？

---

得意忘形 - - 32 位（不可逆）sbox

因為 $ m=2^{32}+1 $ 不是素數沒有滿（ $ 2^{32} $ term) 形式的序列遞歸

Seed = Seed * const % m

如果我們不希望非常準確，也可以只用減法來形成這個 % m 操作。或者一個測試並減去 1 我們想要準確。因此加密程式碼執行

z ^= ((x+1) * const % m)-1

可以在解密中執行以恢復的先驗值 $ z $ .

這個“32 位 sbox”是一個有用的概念嗎？

很多加密算法（例如，在AES中）中的 S-box已經用數學建構（AES S-box 是 $ GF(256) $ 加上仿射變換）。查找表的存在僅僅是為了簡化實現。事實上，現代 Intel/AMD CPU 已經配備了 AES 輪函式指令，因此根本不需要這些表。

當人們設計新的 S-box 時，首先要回答的問題是為什麼？下一個是它們與現有的相比有哪些屬性？. 在得到合理答案之前，這些建議不會被使用，甚至不會被分析。

這是一個好主意，並且已經有效地使用了。

s 盒用於將非線性變換引入密碼原語。在這個答案中，我只會處理不可逆的 s 框。正如問題所強調的那樣，實時計算的 s 框避免了查找表的需要。8 位 s 盒的大小為 256 字節，16 位為 132KB，32 位為 16GB。所有這些都基於 32 位 Java 機器。雖然今天 16 位盒很容易管理，但 32 位盒並不那麼實用。擴大範圍目前是不現實的。

OP 建議避免使用查找表並使用算法來確定 s 盒的輸出。該算法是： -

p = 49374; 
y = ((x+1) * p % m)-1;

繪製前一百個數字的輸入與輸出給出了一個令人不安的關係：-

而如果它是隨機的，具有大的漢明距離，它應該看起來像這樣：-

解決 s 盒算法問題的一種方法是從 Kolmogorov 複雜度。發布的算法只有 24 字節長，這種簡單性體現在 IO 圖的高度組織性和重複性上。Kolmogorov 的簡單源於簡單。紅色的 IO 圖是用一個隨機填充的 256 字節 s 框繪製的。它的 Kolmogorov 複雜度為 256 字節，因為該表是可壓縮的，並且不能以比實際列出原始內容更少的字節來定義。因此，輸出是高度隨機的，具有非常低的可壓縮性/高 Kolmogorov 複雜性。

目前在 Whirlpool 散列的行混合子輪中使用了這種算法方法。使用以下矩陣跨八個字節執行 ersatz 矩陣散列：-

這相當於一個 64 位寬的 s 盒，否則無法儲存。然而，計算工作量和時間是有代價的。我沒有繪製這種 IO 關係，但我希望它不像第一個 Op 的圖表那樣結構化，但仍然具有可辨識的形式。Kolmogorov 複雜度仍然很低，因為矩陣顯然可壓縮為旋轉列或 x^8 + x^4 + x^3 + x^2 + 1 等方程。

對於最大非線性，可以使用具有等於矩陣大小的 Kolmogorov 複雜度的完全隨機矩陣。此類矩陣用於真隨機數生成器的隨機提取器中。矩陣的大小可能為 1000 - 2000 位，形成約 40 位寬度的等效 s 盒。這可以擴展到更寬的等效 s 框。例如，一個 2048 位寬的 s 盒可以很容易地用 64KB 的隨機排列的 Pearson 雜湊表來建構。

綜上所述，如果需要一個大於 16 位的 s box，算法方法就是目前使用的方法。但是，由於它們比普通的查找表要慢得多，因此需要支付時間損失。

引用自：https://crypto.stackexchange.com/questions/17975