小域鍵控排列本質上是不安全的嗎？
在Computer Science Stack Exchange 中接受的一個問題的答案中，提到了計數器模式下的分組密碼生成了一個具有大位空間的隨機數生成器，它在循環之前恰好訪問域的每個元素一次。
當然，使用通常的塊密碼塊大小（128 位或更多），你永遠不會達到那個循環點。在另一個答案的評論中，出現了一個問題，我們是否可以用更小的域大小來做同樣的事情。
是否有一種加密方式來建構具有“小”域大小的鍵控排列，這樣即使給定所有輸入-輸出對，在計算上也無法導出密鑰？
還是小域排列總是允許對密鑰進行暴力破解？
（這樣一個函式的目的是建構一個 PRNG，它循環遍歷所有值一次，然後以不同的順序再次循環：使用這個帶有固定鍵和計數器輸入的鍵控排列，當計數器溢出時，遞增鍵.)
不，小域鍵控排列本質上不是不安全的，因為某些不安全的定義適應了小域的固有限制。我們可以建構具有小域的鍵控置換，該置換在計算上與隨機的此類置換無法區分。這是Format Preserving Encryption的標準。幾種結構是已知的。
在下面，我將假設一個域 $ v $ 值（的 $ w $ 位與 $ w=\log_2v $ ）， 和 $ k $ 鍵（ $ \ell $ 位與 $ \ell=\log_2k $ ）。
小域排列總是允許對密鑰進行暴力破解嗎？
不，但對於足夠小的域（包括 $ v\lesssim 24 $ ， 那是 $ w\lesssim4.6 $ ) 可以將所有輸入/輸出對製成表格並找到一個工作密鑰（不一定是密鑰），無論它有多大 $ k $ 是。請注意，當 $ v!<k $ .
這樣一個函式的目的是建構一個 PRNG，它循環遍歷所有值一次，然後以不同的順序再次循環：使用這個帶有固定鍵和計數器輸入的鍵控排列，當計數器溢出時，遞增鍵。
很好，如果這個 PRNG 是可以區分的，並且具有相當大的優勢，那麼 $ \sqrt v=2^{w/2} $ 輸出，因為它不經常重複。
為了 $ w=32 $ 正如此評論中所問的那樣，並且在固有地整個消息空間最終將耗盡的案例中，我們不能使用純 Feistel 密碼，在每一輪 $ (L_{i+1},,R_{i+1}):=(R_i,,L_i\oplus F_i(K,R_i)) $ . 那是因為這實現了一個偶數排列，它允許預測 $ (2^{32}-1)^{\text{th}} $ 和 $ (2^{32})^{\text{th}} $ 確定地產生的值，從以前的 $ 2^{32}-2 $ . 我們可以通過添加一個密鑰模的組件來解決奇偶校驗問題 $ 2^{32} $ ; 結果排列將是奇數還是偶數，具體取決於該關鍵組件是奇數還是偶數。
這是一個達到（低）*“我不知道如何在編寫後立即攻擊它”*安全級別的範例：
// a 32-bit PRP with 192-bit key uint32_t prp32(const uint64_t k[3], uint32_t b) { uint64_t u = k[0], v = k[1], w = k[2]; uint32_t r = 48; do { b ^= b<<1 | b<<5; // Xor with non-linear function u += v ^ r; b += b<<4; // Add v ^= w; b = b<<13 | b>>19; // Rotate w += u<<27 | u>>37; b = (b>>3 ^ b) + (uint32_t)u; // Xor and enter round key } while(--r!=0); return b; }理由：
- 這是一個迭代的塊密碼轉換整個塊 $ b $ 在每一輪，同時導出輪密鑰（作為低 32 位輸入 $ u $ ）。
- 的 4 個子變換中的每一個 $ b $ 是一個排列（對於常數 $ u $ )，因此整個結構是一個排列。
- 4個子變換 $ b $ 是ARX，有一個額外的非線性第一個。相對於字寬 (32) 的小移位常數 (1, 5, 4, 3) 使得 Add 和 Xor 步驟幾乎在整個寬度上執行。
- $ (u,v,w) $ 根據密鑰進行初始化並根據可逆的 ARX 轉換進行演化（在該輪的三個非註釋行中；這些可以在輪開始時移動而不改變結果：它們只是為了流水線而交錯）。
- 在大多數現代 CPU 上，每個操作都有一個簡單的硬體實現。編譯器生成的程式碼可以接近最優，數據相關或密鑰相關時序變化的機會最小。
- 將圓鍵與 $ u $ 通過加法模 $ 2^{32} $ 導致排列的非恆定奇偶性（進一步，這已通過實驗驗證）。
- 在轉換中輸入整數 $ u $ 防止全零鍵是特殊的（例如有 $ b=0 $ 作為固定點）。
- 如果 48 輪足以補償塊中的緩慢擴散，這是完全值得商榷的 $ b $ （這需要量化）。我希望它比Simon更保守。這是基於每輪至少值得 1.5 輪 Simon32 的猜測，因為 3 次操作轉換（忽略旋轉）至少要寬得多，而且稍微複雜一些。
上述方法（或更保守的Feistel 密碼）適用於整數 $ w $ 從 8 位到 64 位。為了 $ v $ 不是 2 的冪，我們可以為下一個 2 的冪做一個密碼，然後通過循環行走減少域，更糟糕的是（當 $ v $ 略高於 2 的冪）大約是平均功的兩倍。當心會有一個依賴於數據的時序變化，在某些情況下它可能是有害的（但我不認為它可能是在問題的 PRNG 的上下文中）。