SHA-256 和 SHA-512 是否抗碰撞？
這是我在這個論壇的第一篇文章，如果這篇文章是幼稚的，請見諒。我想學習密碼學，我想從這個問題開始。
背景：設計一個 TinyUrl 系統。使用者輸入一個冗長的 URL，系統計算雜湊並將其編碼為 binary64 並將其發送回使用者。
據我目前所知（來自這個論壇和維基百科），SHA-2 算法不是無衝突的。如果這些功能確實不是無碰撞的，如何讓它們無碰撞？網際網路上有一些資源建議添加抖動，例如，在 URL 開頭的唯一字元串，軟體系統設計中的可行解決方案。這不僅使不同的 URL 產生不同的雜湊值，而且還使相同的 URL 在 2 次不同的嘗試中產生 2 個不同的雜湊值（可能是針對 2 個不同的使用者）。在反向查找中，系統可以忽略前綴並使用 HTTP 302 將使用者重定向到原始 URL。但是，這增加了系統自身的複雜性，即跨分佈式系統的不同伺服器生成/使用唯一前綴。
問題 1：當使用 SHA-256 或 SHA-512 時，2 個不同的字元串/URL 產生相同雜湊的可能性有多大？
問題 2：假設系統將 300 億個 URL 的雜湊值保存在數據庫中，如果不是 SHA-2，推薦的雜湊函式是什麼？請注意，系統的要求是它應該是高可用的，這意味著：雜湊計算不應該花費很長時間。
感謝任何幫助。提前致謝！
PS：很高興開始使用密碼學。
設計上的加密雜湊函式不可能是無衝突的，因為它們在任意大小的輸入上執行到固定大小的輸出，例如 SHA-256 的 256 和 SHA-512 的 512。$$ H:{0,1}^* \to {0,1}^b $$在哪裡 $ b $ 是個 $ H $ 的輸出大小。
根據鴿巢原理，碰撞是不可避免的。簡單考慮一下 100 洞和 101 羽鴿子。有了這種條件，當鴿子上洞時，至少要多出一洞鴿子。
這並不意味著人們可以很容易地找到碰撞。對於 SHA-256，您需要 $ 2^{128} $ 輸入以查看至少一個有 50% 機率的碰撞對。對於 SHA-512，即 $ 2^{256} $ . 這是由於具有成本的通用生日攻擊 $ \mathcal{O}(2^{n/2}) $ 50% 用於 $ n $ -bit 輸出雜湊函式。這些數字是巨大的，需要考慮。例如，比特幣礦工的集體力量可以達到 $ ~2^{93} $ 每年的 SHA-1 雜湊值。這意味著他們需要 2^{37} 年才能找到 50% 的人。
我們不會試圖讓它們無碰撞，我們通過了解邊界來適應它。
目前，對於 SHA-256 和 SHA-512，都沒有比通用碰撞攻擊更好的碰撞攻擊。減少輪數有攻擊，但是，這僅表明比通用更好的是難！我們會驚訝地發現兩個輸入發生衝突。這甚至隨機發生在MD4上。MD5 衝突是微不足道的，SHA-1 已被粉碎。即使在 2010 年代初期，也不要混淆那些不是安全的雜湊函式。
使用 SHA-256 或 SHA-512 時，2 個不同的字元串/URL 產生相同雜湊的可能性有多大？
如果我們對 SHA-256 均勻隨機建模，那麼 $ 1/2^{256} $ . 這是一個簡單的機率；第一個元素可以得到任何位置然後第二個元素有 $ 1/2^{256} $ 打第一個的機率。
問題 2：假設系統將 300 億個 URL 的雜湊值保存在數據庫中，如果不是 SHA-2，推薦的雜湊函式是什麼？請注意，系統的要求是它應該是高可用的，這意味著：雜湊計算不應該花費很長時間。
300億網址（ $ \approx 2^{32.48} $ URL ) 有碰撞的機率；
$$ (2^{32.48})^2/2^{256}/2 = 2^{69.6 - 256-1} \approx 1/2^{187.4} $$
如果事件有機率，我們稱它為“不會發生” $ <\frac{1}{2^{100}} $ . 您可以使用任何 512 位加密雜湊函式，如 SHA-512、SHA3-512 和 BLAKE2b，而不必擔心衝突。與替代品及其並行版本 BLAKE3 相比，您可能會非常快地查看 BLAKE2b。
SHA-256 和 SHA-512 是否抗碰撞？
是的，目前截至 2021 年，在不久的將來，是的。