用於小輸出範圍的非重疊種子數生成器
看過這個，但它有點沒用，因為它允許通過將輸出空間的大小增加到一個點任何散列函式都可以實現非衝突來實現簡單的解決方案。
這個問題試圖成為那個沒用的版本。即關於輸出範圍小的情況。說我的輸出空間是 $ \mathcal{S} = {0, 1, \ldots, 10^{6}} $ . 在這裡，使用散列函式很容易發生衝突。
**改寫問題：**是否有任何功能 $ f : \text{seed}, \text{range}, \text{state} \mapsto n $ ，這樣：
- *要求1：*輸出範圍可以小。例如從 $ 0 $ 至 $ 10^6 $ .
- *要求 2：*不同種子沒有衝突。即對於任何種子和範圍， $ f(\text{seed}, \text{range}, \text{state}_1) = f(\text{seed}, \text{range}, \text{state}_2) $ 當且僅當 $ \text{state}_1 = \text{state}_2 $ .
- *要求 3：*除非呼叫函式，否則無法預測下一個數字是什麼 $ f $ . 例如，如果 $ f(\text{seed}, \text{range}, \text{state}_1) = 3 $ ，然後不知道輸出是什麼 $ \text{state}_2 $ 無需將其插入功能 $ f $ . 這消除了可能使用定義的瑣碎解決方案 $ f’ : \text{seed}, \text{range}, \text{state} \mapsto \text{seed} \times \text{state} \mod \text{range} $ ，其中種子、範圍和狀態都是正數。
有什麼功能嗎 $ f : \text{seed}, \text{range}, \text{state} \mapsto n $ ,
是的; 它們被稱為格式保留加密功能。這些是任意大小的分組密碼函式：
- *要求1：*輸出範圍可以小。例如從 $ 0 $ 至 $ 10^6 $ .
是的，他們可以採取相當小的範圍。根據我的經驗，FPE 往往不喜歡真正小的範圍（例如，小於 100 個值的範圍）；對於我所知道的人來說，一百萬的範圍就足夠了
- *要求 2：*不同種子沒有衝突
如果我們使用種子作為 FPE 密鑰，狀態作為 FPE 明文，這是有保證的 - FPE 操作是可逆的（也就是說，通過將 FPE 操作置於解密模式並提供相同的密鑰，它會轉換密文回到明文），因此兩個明文不能轉換成相同的密文
*要求 3：*除非呼叫函式，否則無法預測下一個數字是什麼 $ f $
也是真的；FPE 被設計為安全的（除非您知道密鑰），因此預測明文如何轉換的唯一方法是使用密鑰。
FPE 函式還需要“調整”（一個不需要私有的附加輸入，它會更改加密定義的映射） - 我建議使用範圍作為調整的一部分（除了修改 FPE 函式內部的工作方式） - 這樣，您不必擔心具有一個範圍的函式會洩漏有關具有不同範圍的函式的資訊。
現在，如果您需要關於使用哪個 FPE 函式的建議，我發現最好的一個是此處定義的 FF1函式；從我播種的情況來看，它似乎相當穩固。