理想的雜湊函式和實際的雜湊函式有什麼區別？
該論壇的一位使用者講述了理想和實用的散列函式。
它們之間有什麼區別？
有人可以提供理想和實用的雜湊函式的例子嗎？
至少在連結的上下文中，來自集合的理想（加密）散列函式 $ \mathcal M $ （消息集 $ M $ ，通常是有限位串的無限集 $ {0,1}^* $ ) 到有限集 $ \mathcal H $ （散列集，通常是 $ b $ -位比特環 $ {0,1}^b $ ) 是一個數學抽象。它是一組函式的隨機成員 $ \mathcal M $ 至 $ \mathcal S $ . 它也可以建模為隨機預言機（兩者顯然無法區分）。對於有限輸入集 $ \mathcal M $ ，我們可以通過獨立且均勻地隨機選擇一個輸出元素來製作一個理想的散列 $ \mathcal H $ 對於每個輸入元素 $ \mathcal M $ . 問題是所需的儲存隨著消息的位大小呈指數增長 $ M $ ，這是不切實際的。
一個實用的（加密的）散列函式是，對於一個固定的輸出集 $ \mathcal H $ , 可以通過大小基本上獨立於消息位大小的算法來實現 $ M $ ，以該位大小和恆定（或適度）臨時儲存在時間上線性（或接近）執行；卻盡可能地表現得像一個理想的散列函式/隨機預言機。理想情況下：對於不知道實際雜湊的某個參數的人來說，在計算上不可能將實際雜湊與理想雜湊/隨機預言區分開來。
長期以來，構造實用雜湊函式的最標準方法是Merkle-Damgård構造。如果主要完成這項工作（特別是具有抗碰撞性和抗原像性），但具有不需要的長度擴展屬性：對於任何 $ M_0 $ （在一些巨大的最大尺寸限制內）只知道它的尺寸和散列，可以找到一個短的 $ M_1 $ 這樣對於任何 $ M_2 $ （在一些巨大的最大尺寸限制內）可以計算 $ H(M_0\mathbin|M_1\mathbin|M_2) $ . 理想的雜湊不具有該屬性，並且有一些（很少）實際情況很重要。我們現在有了更好的實際雜湊結構，例如海綿結構，在計算上無法與理想的雜湊/隨機預言區分開來。