Hash
如何構造一個不是單向函式的抗碰撞雜湊函式？
如何構造一個不是 OWF（單向函式）的 CRHF（抗碰撞雜湊函式）？不確定，但我認為它可能需要另一個 CRHF？
如果沒有單向性，將很難實現抗碰撞性。確實，單向性的否定意味著對於給定的輸出，您可以找到相應的輸入。因此，通過簡單地選擇一個隨機輸入m，將其散列到輸出x，然後為獲得的輸出x找到原像**m’ ，很容易獲得碰撞。這種方法不起作用的唯一方法是使輸出空間至少與輸入空間一樣大，以便輸入m’很有可能與m相同。但是，由於散列函式的輸入空間比輸出空間大得多（例如，SHA-256 輸出空間的大小為 2 256，但其輸入空間的大小為 218446744073709551616 -1，這要大得多），您從利用非單向性中獲得的m’可能與您開始使用的**m不同，這會產生衝突。
Thomas Pornin 已經解釋了為什麼這樣的事情通常是不可能的，但我想引用 Rogaway 和 Shrimpton 的*“加密雜湊函式基礎：原像抗性、第二原像抗性和碰撞抗性的定義、含義和分離”中的圖形"* ( pdf ):
從Coll ision resistance 到Pre image resistance的虛線箭頭表示含義取決於消息和散列大小。您將在論文的定理 7 中找到確切的概念。
