關於使用模運算減少雜湊值的安全問題
如標題所述，我正在尋找的是有關我想在某些算法中使用的“技術”的資訊。
有時我需要將散列函式的結果映射到一個沒有散列函式的餘域那麼大的數字範圍；為此，我使用模運算符。我將散列函式的輸出視為整數；然後對這個整數應用模運算
$$ h(x)\bmod n\text, $$ 在哪裡 $ n $ 是允許的數值範圍的排除上限 $ {0,\dots,n-1} $ . 現在我想了解的是，這是否會導致一些安全風險，而不是獲得的“雜湊”大小更小（因此暴力攻擊更容易），例如模數運算符可能會破壞隨機性雜湊函式以某種方式。
提前感謝您的澄清。
讓我們假設 $ h(x) $ 返回一個介於 0 和 $ k $ （獨家的）。如果 $ h $ 是一個很好的雜湊，這個分佈將是均勻的。
計算 $ h(x) \mod n $ 如果會引入偏差 $ k $ 不是的倍數 $ n $ . 這種偏差是顯著的，如果 $ k $ 僅略小於 $ n $ 並減少為 $ k/n $ 成長。多大 $ k/n $ 需要取決於您可以接受的偏見程度。
DSA 算法需要生成一個無偏的數字。NIST 建議（附錄 B.2.1 中的 FIPS 186-4）您應該使用至少 64 個額外位，即 $ k/n > 2^{64} $ . 這是合理的，因為這意味著只有在攻擊者看到周圍時才會檢測到偏差 $ 2^{64} $ 樣品。我懷疑你會生成那麼多數據。
因此，如果您採用至少 128 位的加密雜湊，請將其解釋為一個大整數，並將其取模一個小於 $ 2^{64} $ 由此產生的偏差可以忽略不計。
如果您的應用程序對偏差不太敏感，則減少 64 位數字模數可能是可以接受的 $ n $ . 這避免了對大整數庫的需要，並且是我為隨機字元串生成器所採用的方法。
避免偏見的另一種方法是拒絕介於 $ \geq k - k \mod n $ . 但這意味著您需要消耗可能無限量的隨機值，因此它可能不是最適合您的應用程序的。