查找碰撞字符串與給定的哈希函數

我有一個字符串anna，在字符串中的字符的值是a = 1, n = 14 (You can compute the value of other chars like (char - 96)和哈希函數看起來像：查找碰撞字符串與給定的哈希函數

int hashCode(string s) // s = "anna"; 
{ 
    k = 0; 
    for (int i = 0; i < s.length(); i++) 
     k = (7 * k + 3 * s[i]) % 61; 
    return k; 
}

如何找到一個長度爲3的字符串發生碰撞（聰明的事情）？我想到的唯一方法是計算k的anna這是29，然後以某種方式想到另一個長度爲3的字符串，它給出29。

來源

2016-11-30 kvway

你不得不暴露它恐怕是的。 –

我看到_61_是總理，你正在調整它。歡迎來到[離散對數問題]的世界（https://en.wikipedia.org/wiki/Discrete_logarithm）。 – SpencerD

@ Jean-FrançoisFabre：我不太確定，寫一個好的單向加密散列函數是很困難的。也就是說，我不是加密或數學專家，所以我不能說你會如何正確地扭轉這種情況，但是當你談論長度爲三串小寫字母時，你不需要放聰明點;搜索空間只有26 ** 3 == 17,576個字符串，所以耗盡它們都是微不足道的。 – ShadowRanger

爲什麼不簡單地生成長度爲3的所有字符串並計算它們的散列（實際上，當所有61個可能的散列函數值都可以達到時，您可以停止）？選項的數量不是太大。一個可能的優化：如果你需要回答多個查詢（如給定一個字符串，找到一個長度爲3的字符串，其值爲散列函數的相同值），則可以生成長度爲3的所有字符串，並計算它們的散列值建立地圖hash -> a string of length 3 with this hash。一旦你有了這張地圖，找到一個長度爲3的字符串，與給定的哈希相同，只是一次地圖查找。

來源

2016-11-30 18:39:09 kraskevich

可能要存儲'hash - >這個散列長度爲3的兩個字符串。你知道，如果存儲的第一個字符串是你試圖找到碰撞的字符串。 :-) – ShadowRanger

@ShadowRanger是的，很好的接收。 – kraskevich

查找碰撞字符串與給定的哈希函數

回答

相關問題