對於任何兩個不同的公鑰作為原像，Keccak_256 的尾隨 160 位發生衝突的可能性是多少？
今天早些時候，我在乙太坊 SE網站上回答了一個問題，該問題分析了曲線 secp256k1 上的多個私鑰（映射到不同的公鑰）來控制相同的乙太坊地址的可能性，該地址是通過對公鑰進行散列得到的Keccak256 作為一個字節數組，兩個不同的雜湊摘要的最右邊的 160 位是否會發生衝突，從而兩個不同的私鑰控制相同的地址。
換句話說，任何兩個 Keccak 派生的雜湊摘要具有相同的最右邊 160 個尾隨位（小端側）的可能性有多大？
secp256k1其次，如果兩個原像都只能是有效的公鑰，那麼這種可能性是否會改變（以及在多大程度上） $ {2^{256}} $ 它們中的一個或更精確地n根據該曲線的參數，其中n等於0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141。同樣，乙太坊地址只是從使用者私鑰（假設小於 n）派生的 secp256k1 公鑰的 64 十六進制（256 位）Keccak 雜湊的最後 40 十六進製字元。
如果摘要空間是 $ 2^{256} $ ，並且甚至存在 2 個共享相同尾隨 160 位的摘要，那麼這 2 個摘要的前映像是有效的 512 位公鑰的可能性有多大？此外，這些私鑰實際上是由使用者已知的私鑰派生的（而不僅僅是一個被暴力破解的隨機 512 位字元串）。
考慮到多層條件（與能夠嘗試任意前映像而不管長度等相比），我認為有可能（也許是偶然）沒有兩個私鑰會派生相同的乙太坊地址，即使存在不止一個 Keccak256 雜湊摘要在最後 160 位方面部分衝突。
儘管如果存在不可忽略的此類 160 尾隨位衝突，那麼一個乙太坊地址是否真的有機會被兩個不同的公鑰控制？（即使找到它們不可行）。
**注意：**我的估計/猜測是至少必須進行蠻力搜尋 $ 2^{160} $ 橢圓曲線上的有效私鑰，包括導出公鑰的步驟和生成的 Keccak256 雜湊摘要，以嘗試找到最後 160 位的此類部分衝突。
這種情況甚至可以計算出來還是沒有辦法知道？
大約有 $ 2^{256} $ 不同的輸入，secp256k1 私鑰，以及關於 $ 2^{160} $ 不同的輸出，乙太坊地址。
根據鴿巢原理，至少有一個地址被多個私鑰共享。原則上可以有 $ 2^{160} - 1 $ 每個地址都只有一個私鑰，另一個地址 $ 2^{256} - (2^{160} - 1) $ 不同的私鑰。但這基本上保證在實踐中不會出現這種情況。
從 secp256k1 私鑰到乙太坊地址的映射可以合理地建模為統一隨機函式。在這個模型中，單個雜湊共享的 secp256k1 私鑰的預期數量約為 $ 2^{96} = 2^{256}!/2^{160} $ .
你能用這個明顯數量驚人的衝突私鑰做什麼？
- 假設世界已經生成 $ n $ 私鑰並公佈了他們的地址。有一對私鑰的機率 $ k \ne k’ $ 共享一個共同的地址 $ H(k) = H(k’) $ 是關於 $ n^2!/2^{160} $ 由生日悖論$$ 1 $$.
如果世界產生了一萬億個密鑰，或者大約 $ 2^{40} $ , 這個機率低於 $ 1/2^{80} $ . 換句話說，你基本上可以保證它沒有發生。
- 假設你想找到一對私鑰 $ k \ne k’ $ 共享一個共同的地址 $ H(k) = H(k’) $ . 已知最便宜的方法是 van Oorschot-Wiener 並行碰撞搜尋機$$ 2 $$，其預期成本為 $ \sqrt{2^{160}} = 2^{80} $ ; 當然，如果並行化 $ p $ 方式，它及時執行 $ 2^{80}!/p $ .
這筆費用由比特幣網路在大約一天內花費。但是你會用這對鑰匙做什麼呢？您可以將其中一把鑰匙交給某人，然後用另一把鑰匙做一些邪惡的事情，但是……如果您已經可以選擇某人的鑰匙，那麼很難想像您可以用一把碰撞的鑰匙做哪些邪惡的事情，而您已經無法做到首先是原版。
- 假設你有一個特定的地址 $ h = H(k) $ 一把鑰匙 $ k $ 你不知道，你想找到一把鑰匙 $ k’ $ 匹配的 $ h $ . 您基本上可以保證 $ k’ \ne k $ ，不過沒關係—— $ k $ 可以花的錢 $ k’ $ 反之亦然。也許你實際上有 $ t $ 不同的地址， $ h_1 = H(k_1) $ , $ h_2 = H(k_2) $ , …, $ h_t = H(k_t) $ ，如果你找到一個匹配的，你會很高興 $ k’_i $ . 已知最便宜的方法是改編 Oechslin 的彩虹表$$ 3 $$到一個 $ p $ -路併機$$ 4 $$, 花費 $ 2^{160}!/t $ 只要 $ t < p^2 $ , 並及時執行 $ 2^{160}!/pt $ .
即使您有千萬億個目標鍵（大約 $ 2^{50} $ )，但你沒有，而且你有一個 $ 2^{100} $ - 方式並行電腦，你不這樣做，它仍然會花費 $ 2^{110} $ 為該電腦供電以找到第一個匹配的私鑰，而您不會。
PS 公鑰可以用 512 位編碼，但只有大約 $ 2^{256} $ 其中——具體來說，不同的公鑰和不同的私鑰一樣多。