素數模上的離散對數：小輸入，大指數，大素數
我正在考慮使用模冪作為單向雜湊函式。更具體地說，這是場景。
1）輸入（ $ m $ )：輸入消息很小（16 位）
指數 ( $ e $ )：指數是一個 160 位整數，只選擇一次，並且是隨機的；指數不是公開的
素數 ( $ p $ )：一個 2048 位安全素數，只選擇一次並且是公開的
然後將消息的雜湊計算為： $ h=m^e $ 反對 $ p $ .
我的問題是是否存在計算指數的有效算法 $ e $ 給定一定的 $ h $ , 特別是因為只有 $ 2^{16} $ 的可能性 $ m $ ?
由於攻擊者不知道 $ m $ ，他不能直接應用離散對數方法。另一方面，小的消息空間允許在每個可能的情況下執行離散對數算法 $ m $ .
dlog 有次指數算法，但我不確定它們是否在這裡直接適用。但是一般的BSGS算法會發現 $ e $ 在 $ sqrt(e) $ 操作，所以對於每個 $ m $ 我們需要的候選人 $ ~2^{80} $ 尋找一些可能的操作 $ e $ （全部的 $ ~2^96 $ 複雜）。值得注意的是，大多數錯誤的候選人 $ m $ 不會產生任何 $ e $ 所以這也可以用來“取消雜湊”你的“雜湊”。儘管複雜度很高，但很有可能可以應用更有效的離散對數。
另一個注意事項：假設您使用奇數 $ e $ ，這個“雜湊”洩露了一些關於消息的資訊：勒讓德符號（例如，如果消息是二次剩餘模 p 或不是）。
PS：目前還不完全清楚你將如何使用它以及為什麼你的攻擊模型假設只知道 $ h $ ， 不是 $ m $ （從那時起發現 $ e $ 很難）。但這令人困惑，因為您似乎還想隱藏有關 $ m $ ，這在這裡真的是個壞主意。
這絕對不是一個好的散列函式，但正如您已經意識到的那樣，它實際上不是一個散列函式。您的構造可以被視為PRF或HMAC，對於兩者來說它也不安全。一個普遍的問題是，您允許攻擊者的方式太少。只給他 $ h $ ，這類似於僅密文攻擊，這在當今對安全性的理解中是不夠的。
基本上，在 PRF 和 HMAC 兩種情況下，您都將允許攻擊者訪問預言機，並挑戰他將其與真正的隨機函式區分開來。這很簡單： $ h(1)=1 $ （和 $ h(0)=0 $ ) 在您的構造中，這很容易區分。
最後： $ 2^{16} $ 因為輸入空間對於完整搜尋來說太容易了。我猜任何現代電腦都可以在幾秒鐘內做到這一點。特別是您只需要詢問輸入範圍內所有素數的雜湊值，因為您的方案是乘法的： $ h(x_1x_2) = h(x_1)h(x_2) $