SHA1子問題

我想提出一個引擎收錄類型的網站，我試圖讓ID是一個隨機字符串像paste.com/4RT65LSHA1子問題

我收到ID的SHA1之前，我把它添加到數據庫中，但我得到了sha1的前8個字符的子字符串。他們是否有可能成爲同一sha1的雙份副本？我不希望他們意外成爲第二個貼有已經使用過的ID的貼？

來源

2010-10-08 Robert Cardona

那麼在8個字符中碰撞的機率要比與兩個Sha1鍵發生碰撞要高得多，但這並不意味着它很可能會發生。

我會建議你對它做一些測試。生成隨機輸入並查看碰撞前需要多長時間。如果你喜歡這個結果，那就去吧。否則，你需要一個更長的字符串。

編輯：你也可以通過查看Birthday Paradox來計算碰撞的機率。基本上，如果你從SHA-1中取出前8個十六進制數字，那麼你有16 ** 8（4,294,967,296）不同的可用組合。

使用在線Birthay悖論計算器，在大約9200次散列之後，您將有1％的碰撞機率。在你有10％的機會之前它將需要約30,000次散列，而在你有50％的機會之前需要77,000次散列。

重要的是要指出，只要你的散列函數做僞隨機的體面工作，你使用哪一個（無論是SHA1，MD5還是任何形式的校驗和）都沒關係 - - 這些數字完全是隨機輸入，因此只能通過使用越來越好的散列函數來處理這些值。

所以最終，這取決於您期望的流量。如果這是一個小型網站，你可能會逃避。如果這是一個很大的交通量，那麼你的碰撞機率非常高。

來源

2010-10-08 03:07:07 riwalk

我想過這樣做，但我不知道如何去編寫一個匹配兩個確切字符串的程序。有任何想法嗎？ – 2010-10-08 03:08:39

生成完全隨機的字符串並計算它們的哈希值。散列函數是（或者至少它們試圖是）僞隨機的，所以輸入是否有意義也沒有區別。 – riwalk 2010-10-08 03:10:08

那麼，爲什麼不告訴我們「顯着更高」真的是什麼？ – stillstanding 2010-10-08 03:23:04

在分配id之前，你總是可以檢查它沒有被採用......或者甚至更好，把一個唯一的id放在數據庫字段上......問題解決了。 :)

等等，你說的ID的SHA1。你不是指你的autoinc ID嗎？我的第一個猜測是：

356a192b 
da4b9237 
77de68de

如果您使用的是隨機ID，爲什麼要在其上運行sha1？

來源

2010-10-08 03:41:36 DGM

autoinc id在數據庫上，我想實際的id人們看到是隨機的，以便他們不會看到其他人的帖子。就像現在它是id = 45，他們可以將其更改爲0-45並查看所有這些帖子。總體而言，這僅僅是爲了知識，我不希望獲得超過200個帖子，但是希望它能像tinyurl那樣寫作 – 2010-10-08 03:55:25

如果你想讓url是隨機的，那麼你不需要散列。要看你的id = 45，我只需輸入fb644351。生成* real *隨機字符串並將其存儲在具有唯一索引的記錄中，然後在收到URL時搜索該字符串。 – DGM 2010-10-08 19:09:57

我想通了，我的代碼是：

strtoupper(substr(sha1($token_start . $id . $token_end), 0, 8))

其中$ ID是是找到了什麼ID的總量是在數據庫+ 1，是因爲下一個ID獲得的ID它是自動增量。

然後當它插入它插入加密的條目。

$ token_start和$ token_end都是隨機字符串，您可以選擇使其具有唯一性。

我做了一個循環，將它們插入數據庫32000次，只是id，autoincrement以及新的id，我做了一個獨特的搜索，並沒有得到任何dublicates。這對我來說已經足夠了。任何評論都會有幫助。我不知道它會花多長時間，它會給我一個碰撞。如果有人知道什麼時候第一個會是那麼棒。

來源

2010-10-08 05:47:43

正如我所提到的那樣，在30k的時候，碰撞機率有10％左右。你不能保證什麼時候發生碰撞，因爲它是基於偶然的。在77k時，你將有50-50的機會。 – riwalk 2010-10-08 13:57:45

回答

相關問題