輕量級8字節散列函數算法

我需要從一個可變長度的字符串中提取一個8字節的摘要，所以我正在尋找一種我將在c/C++中實現的算法。這將是微控制器數字簽名程序的一部分，所以它必須是：輕量級8字節散列函數算法

可以在幾行代碼中寫入，因爲固件必須儘可能少地保留;
資源消耗低，特別是ram（最好少於100字節）;
強大到足以在字符串的任何點更改單個字符將改變整體摘要。

我看了一下現有的算法，如crc64，但它們似乎對我的平臺來說太重了。

2012-11-10 etuardu

有許多散列函數可用（並且很容易找到）。哪個現有功能看起來「接近」預期的目標，爲什麼？如果他們不能接受，爲什麼？對於一個簡單的「散列函數C」，有許多好的結果/閱讀 - 說實話，只有第三個要求才會顯示任何興趣。另外，由於提到了CRC，目標是[通用] *散列*還是*校驗和*？ – 2012-11-10 19:04:13

也許這可能會有所幫助：http://en.wikipedia.org/wiki/List_of_hash_functions也許檢查出sphlib，但要澄清一些東西8字節將導致衝突，因此您的要求的第3點不能滿足任何哈希算法至少不適用於所有字符串和8個字節是非常低的。 – 2012-11-10 19:08:15

@pst：我考慮了一些現有的散列函數提供了64位輸出，但是例如crc64需要遠遠超過100字節的RAM。正如我在問題中所述，目標是獲取消息摘要，所以密碼函數會更好。不過，我需要它比輕量級更強，所以我也考慮了其他類型的散列函數。 – etuardu

由於AndrewTomazos-Fathomling說，這是不可能做到安全散列在64位，所以如果這是你的意圖，然後我的建議是STOP，拿起一本書並閱讀密碼安全哈希。

如果你不打算使用這個作爲安全散列，並且你不關心衝突或攻擊，那麼他給你的答案工作得很好，你可以根據需要調整素數P1和P2。我會給你另一個選擇，它允許你做標記哈希和混合東西更多。

// Disclaimer: I make no claims about the quality of this particular hash - it's 
// certainly not a cryptographically secure hash, nor should it *ever* be 
// construed as such. 

unsigned long long quickhash64(const char *str, unsigned long long mix = 0) 
{ // set 'mix' to some value other than zero if you want a tagged hash   
    const unsigned long long mulp = 2654435789; 

    mix ^= 104395301; 

    while(*str) 
     mix += (*str++ * mulp)^(mix >> 23); 

    return mix^(mix << 37); 
}

來源

2012-11-10 21:40:24

我更喜歡這個，因爲它保持了對弦的所有字符的敏感性，其他使用了移位的字符串在某些長度後失去了字符串的第一個字符的影響。順便說一下，我發現它可以縮短，例如，'uint64_t mix，mulp = 2654435789; while（* str）混合^ = mulp ** str ++;'。 – etuardu

沒有機會在64位中執行安全散列。即使在160位SHA-1被認爲理論上被破壞。如果你真的關心安全的數字簽名，你應該使用SHA2-256。如果你不關心安全性，只是想避免非對抗性的衝突只是用下面的散列函數，它是好的：

constexpr uint64 P1 = 7; 
constexpr uint64 P2 = 31; 

uint64 hash = P1; 
for (const char* p = s; *p != 0; p++) { 
    hash = hash * P2 + *p; 
}

來源

2012-11-10 19:12:45

+1，雖然'strlen'在C程序中不是一個很好的變量名。 :-P – ruakh

謝謝你的回答，雖然這並不能滿足我的第三點：'mystring1' =>'10000786a32ed'，'mystring2' =>'10000786a32ee'。我需要一些能夠通過散列「傳播」更多單一字符變化的東西。 – etuardu

你想要所謂的「雪崩效應」，但問問自己爲什麼要這樣做。它在安全散列的情況下真正有意義，並且只有64位，它絕對不會抵禦暴力攻擊。你可以通過對P1和P2使用兩個較大的素數來得到更多的翻轉比特，但正如我所說的那樣，沒有意義。 –

下面是一個32位版本的我發現了一個修改版本我舊的源文件

static unsigned long long llhash(const char *str) 
{ 
    unsigned long long hash = 5381; 
    int c; 

    while (c = *str++) 
     hash = ((hash << 5) + hash) + c; 

    return hash; 
}

但散列總是會導致衝突。當然有些算法比其他算法更好。

編輯： 我找到的32位版本的源：http://www.cse.yorku.ca/~oz/hash.html

來源

2012-11-10 19:17:49

輕量級8字節散列函數算法

回答

相關問題