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