你如何找到雜湊的原像？
什麼是原像，如何找到散列的原像？
在數學和密碼學中，給定一個函式 $ H $ 從集合 $ A $ 設置 $ B $ , 和一個元素 $ b $ 在 $ B $ , 的原像 $ b $ 經過 $ H $ 是任何 $ a $ 在 $ A $ 這樣 $ H(a)=b $ .
在密碼學中，一個公共函式 $ H $ 從集合 $ A $ 到有限集 $ B $ 是：
- 對於給定的隨機數，第一原像抗性 $ b $ 在 $ B $ , 很難展示一個原像 $ b $ ， 那是， $ a $ 在 $ A $ 和 $ H(a)=b $ .
- 給定隨機時的第二原像抗性 $ a_0 $ 在 $ A $ , 很難展示另一個原像 $ b=H(a_0) $ ， 那是， $ a $ 在 $ A $ 和 $ a\ne a_0 $ 和 $ H(a)=H(a_0) $ .
原則上可以通過嘗試不同的值來找到原像 $ a $ 在 $ A $ （除此之外 $ a_0 $ 對於第二原像）和計算 $ H(a) $ 直到匹配 $ b $ （給定的 $ b $ 對於第一原像，或 $ b=H(a_0) $ 從給定的計算 $ a_0 $ 對於第二個原像）。根據定義 $ H $ ，可以有更好的方法。
實用的密碼散列函式的一個共同設計目標是尋找原像（任何一種）的預期工作量不小於 $ |B|/2 $ 倍於計算的努力 $ H(a) $ 一次，符號在哪裡 $ |B| $ 指定集合中元素的數量 $ B $ . 什麼時候 $ B $ 是正好的集合 $ n $ 位位串 $ {0,1}^n $ （對於加密雜湊來說很常見）數量 $ |B|/2 $ 變成 $ 2^{n-1} $ .
自從 $ f $ （雜湊函式）很難反轉，你所能做的就是嘗試隨機輸入，直到你成功。
如果散列函式輸出是 $ n $ 位長，並且散列很強（通過隨機函式很好地近似）你的成功機率只有大約
$$ \frac{q}{2^n} $$後 $ q $ 給定輸出的試驗 $ y_0 $ 並檢查是否 $ f(X_t)=y_0 $ 對於隨機輸入$$ X_1,\ldots, X_t,\ldots,X_q. $$ 在最壞的情況下，您可能需要 $ q>2^n $ 以一種假設的機率成功 $ y_0 $ 是雜湊函式的實際輸出，因為沿途的其他輸出通常會發生衝突。最有可能的 $ q\approx n 2^n $ 將需要這是球和垃圾箱過程（優惠券收集器）的預期覆蓋時間。