Hash
查找多個較小的碰撞與查找更大的碰撞一樣有效嗎？
問題一：
我收到兩個雜湊摘要 $ H(x), H(y) $ 和相應的原像 $ (x, y) $ .
$ H $ 是一個128 位加密散列函式： $ H: {0,1}^{*} \longrightarrow {0, 1}^{128} $
我需要找到兩個第二個原像 $ (x’, y’) $ 這樣 $ H(x) = H(x’) $ 和 $ H(y) = H(y’) $ ， 在哪裡 $ x \neq x’ $ 和 $ y \neq y’ $ .
問題 B：
我收到一份雜湊摘要 $ H’(x) $ 和對應的原像 $ x $ .
$ H’ $ 是一個256 位加密散列函式： $ H’: {0,1}^{*} \longrightarrow {0, 1}^{256} $
我需要找到一秒鐘的原像 $ x’ $ 這樣 $ H(x) = H(x’) $ ， 在哪裡 $ x \neq x’ $ .
問題 A 和 B 是等價的嗎？換句話說，兩者都採取 $ 2^{256} $ 工作？
問題 A 和 B 是等價的嗎？換句話說，兩者都採取 $ 2^{256} $ 工作？
不; 在第一種情況下，您可以找到第一次碰撞 $ 2^{128} $ 努力，然後找到第二次碰撞 $ 2^{128} $ 努力，產生總的努力 $ 2^{128}+2^{128} = 2^{129} $
實際上，您可能會開始散列任意值，並在第二個原像後停止 $ x $ 和第二個原像 $ y $ 出現了；這種預期的努力略低於 $ 2^{129} $ …