Hash
基於 SHA-256 的隨機預言機
我遇到了以下問題。
將 SHA-256 視為實際應用中的隨機預言機。構造一個（幾乎）隨機的預言機 $ {0,1}^*→{0,1}^{3000} $ 基於 SHA-256。
這是否意味著輸入是任意長度的零和一，並且應該散列到一個 3000 位零和一的值？如果是，我可以只應用 SHA-256 12 次，將輸入分成 12 部分並刪除 72 位，那麼我將得到 3000 位嗎？還是我誤會了？
這是否意味著輸入是任意長度的零和一，並且應該散列到一個 3000 位零和一的值？
是的，就是這個意思 $ {0,1}^→{0,1}^{3000} $ . 使用“0 和 1 的數字”的常用快捷方式重新制定會更好：bits。還， $ {0,1}^ $ 是所有位串的集合。
我可以只應用 SHA-256 12 次，將輸入分成 12 部分並刪除 72 位，然後我將得到 3000 位嗎？
$ 256\times12-72=3000 $ ，因此您擁有正確的域。但這與隨機預言機沒有區別嗎？不。找出你將如何區分。然後改進該結構。理想情況下，證明如果一種方法可以區分精煉結構和隨機預言¹，那麼它可以變成一種方法來區分 SHA-256。
一個隨機預言機 $ k $ -bit 輸出是一個假設的設備，它接受位串作為輸入，並且
- 如果該位串先前未送出，則在 $ {0,1}^k $
- 否則輸出與之前送出的輸入位串相同的位串。
¹ 無法計算 SHA-256，可能忽略 SHA-256 的長度擴展屬性及其輸入長度限制；其中一些或全部可能是問題與*"(almost)"*的含義。