Hash
為什麼通過蠻力完成對 SHA-256 的原像攻擊總是需要 2^256 次？
我在閱讀 SHA-256 (SHA-2) 的維基百科頁面時遇到了以下聲明：
對於其中的雜湊函式 $ L $ 是消息摘要中的位數，找到對應於給定消息摘要的消息總是可以使用暴力搜尋來完成 $ 2^L $ 評價。
為什麼這是真的？它是 SHA-256 的某些屬性還是我遺漏了什麼？我知道裡面一定有碰撞 $ 2^{256} + 1 $ 獨特的輸入，但我不明白為什麼這意味著必須從一些長度獨特的輸入列表中指定一個摘要 $ 2^{256} + 1 $ .
這是作者懶惰的表現。你是對的，如果 SHA256 是一個構造良好的雜湊函式（我們相信它是）那麼嘗試 $ 2^L $ 輸入很可能會產生原像，但不一定會產生原像。準確地說，如果我們有 $ 2^L $ 不同的輸入，我們期望找到原像的機率是 $$ 1-\left(1-\frac 1{2^L}\right)^{2^L}\approx 1-\frac1e. $$ 更一般的機率分佈 $ n $ , 成功所需的猜測次數由下式給出 $$ \mathbb P({\rm guesses}\le n)=1-\left(1-\frac 1{2^L}\right)^{n} $$ 這樣期望的猜測次數是 $ 2^L $ .
對於“粗略”計算，用均值近似分佈通常很有用，這種習慣導致作者做出技術上不正確的陳述。