無衝突的單向函式映射 32 位到 32 位
聽起來很簡單，但我找不到一個無衝突的單向（ish）函式，它需要 32 位輸入並產生 32 位輸出。如果我只是不知道找到該功能的正確關鍵字，我深表歉意。
當然， $ 2^{32} $ 在現代中高端零售 PC 上可以在幾秒鐘內輕鬆暴力破解的範圍內，但目標是不讓攻擊者以比暴力破解更快的方式找到輸入。
此外，該功能應該被證明是無碰撞的，這可以通過暴力破解每個 $ 2^{32} $ 輸入。如果有人沒有時間這樣做（或者只是不想這樣做），我願意承擔這項任務。
編輯：我忘了提及攻擊場景並且已經放棄了想法：
該函式將在白盒環境中執行，因此我寧願不使用依賴於密鑰的函式來保證安全（例如 Pseudo-Random-Permutations）。
我還嘗試過轉換散列函式，如 SHA-2、Keccak 或 ChaCha 的底層散列函式。可悲的是，它們在被截斷為 32 位時都會發生衝突。
該函式將用於通過比較函式的輸出來混淆 if 語句。
需要一個 32 位整數的排列，它在反向方向上比在正向方向上更難計算。顯然，比例不能超過 $ 2^{31} $ ，因為這是通過蠻力反轉功能的成本。對事物進行參數化也很有用；否則，它可能會被製成表格，甚至可以簡化為彩虹表。
我提出了一個使用離散對數問題的構造 $ \Bbb Z_p^* $ 和騎自行車。
讓 $ p $ 成為素數 $ q=(p-1)/2 $ 素數和 $ p\bmod8=7 $ （這意味著 $ 2^q\bmod p=1 $ ， 和 $ 2 $ 是二次餘數模子群的生成器 $ p $ , 素數 $ q $ ）。功能 $ f_p $ 為整數定義 $ x $ 經過
$$ x\mapsto f_p(x)=\min\big((2^x\bmod p),,p-(2^x\bmod p)\big) $$ 是整數的排列 $ [1,q] $ 這很容易在正向計算，但需要求解 DLP $ \Bbb Z_p^* $ 扭轉。插圖 $ p=47 $
x = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 fp(x)= 2 4 8 16 15 17 13 21 5 10 20 7 14 19 9 18 11 22 3 6 12 23 1如果我們添加兩個參數，這個屬性也成立 $ a $ 和 $ b $ 和 $ 1\le a<q $ 和 $ 0\le b<q $ , 給
$$ x\mapsto f_{(p,a,b)}(x)=\min\Big(\big({(2^a)}^{x+b}\bmod p\big),,p-\big({(2^a)}^{x+b}\bmod p\big)\Big) $$ 和 $ p>2^{33} $ ， 功能 $ {\tilde f}{(p,a,b)} $ 通過迭代獲得 $ f{(p,a,b)} $ 結果大於 $ 2^{32} $ 是整數的排列 $ [1,2^{32}] $ .
現在 $ x\mapsto h_{(p,a,b)}(x)={\tilde f}{(p,a,b)}(x+1)-1 $ 定義一個排列 $ h{(p,a,b)} $ 的 32 位整數，根據需要，在正向評估比反轉要容易得多。
例如，對於 $ p=\lceil2^{32}\pi\rceil+3062=13493040767 $ , $ a=1 $ , $ b=42 $ , 很容易計算 $ h_{(p,a,b)}(4)=2511267353 $ （因為 $ f_{(p,a,b)}(5)=5073155518>2^{32} $ , $ f_{(p,a,b)}(5073155518)=5723706427>2^{32} $ , $ f_{(p,a,b)}(5723706427)=2511267354\le2^{32} $ ）。但解決起來要困難得多 $ h_{(p,a,b)}(x)=2919107273 $ 為了 $ x $ . 試試看！
我估計即使使用複雜的算法來解決 DLP（索引演算或NFS ） ，一個輸出的反演也比直接計算困難數百倍；使用更簡單的算法（ BSGS或Pollard’s ρ ）將難度提高數千倍；並且通過蠻力更難數十萬倍。
在白盒上下文中，讓實現包含 $ 2^a\bmod p=g $ 而不是 $ a $ , 並實施 $ {(2^a)}^{x+b}\bmod p $ 作為 $ g^{x+b}\bmod p $ 或者 $ g^{(x+b)\bmod q}\bmod p $ . 另一方面，在黑盒上下文中，前向實現可以實現 $ {(2^a)}^{x+b}\bmod p $ 作為 $ 2^{(a,x+b)\bmod q}\bmod p $ ，這允許稍微更快的評估。
的迭代次數 $ f_{(p,a,b)} $ 是關於 $ p/2^{33} $ 平均而言，並且對於 $ p<2^{34} $ 超過 $ k $ 機率小於約 $ 2^{-k} $ . 為了減緩評估（和逆轉），我們可以連結幾個 $ h_{(p,a,b)} $ 使用不同的 $ p $ ，這比過大更好 $ p $ 有兩個原因：評估時間往往不太依賴於 $ x $ ; 以及進行大量預計算的攻擊，以便稍後有效地解決相同的多個離散對數問題 $ \Bbb Z_p^* $ 受阻。
在超奇異橢圓曲線上使用 DLP 似乎有更好的結構（在使反向成本與正向成本之比更高的意義上）；看到這個和它的評論，也許這個曲線。