轻量级8字节散列函数算法

我需要从一个可变长度的字符串中提取一个8字节的摘要，所以我正在寻找一种我将在c / c ++中实现的算法。 这将是微控制器上数字签名程序的一部分，因此它必须是：

• 只需几行代码即可写入，因为固件必须尽可能少地保存;
• 资源消耗低，特别是ram（最好小于100字节）;
• 足够强大，在字符串的任何一点更改单个字符都会改变整体摘要。

我看了一下现有的算法，比如crc64，但它们对我的平台来说似乎太重了。

Answer 1

正如AndrewTomazos-Fathomling所说，用64位进行安全散列是不可能的，所以如果那是你的意图，那么我的建议是停止 ，拿起一本书并阅读有关加密安全散列的内容。

如果您不打算将此作为安全哈希并且不关心碰撞或攻击，那么他给你的答案就可以了，你可以根据需要调整素数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); } 

Answer 2

没有机会以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; } 

Answer 3

这是我在旧源文件中找到的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

Answer 4

我有完全相同的要求， 在解雇SIP哈希（ 由bloomberg在这里实施 ）之后 ，我选择了FNV-1A 。

我在这里找到了一个FNV实现：

https://github.com/foonathan/string_id/blob/master/hash.hpp

这是：

 constexpr uint64_t fnv_basis = 14695981039346656037ull; constexpr uint64_t fnv_prime = 1099511628211ull; // FNV-1a 64 bit hash of null terminated buffer uint64_t fnv1a_hash(const char* str, uint64_t hash = fnv_basis) { return *str ? fnv1a_hash(str + 1, (hash ^ *str) * fnv_prime) : hash; } 

看起来他正在使用尾递归进行循环。 并且stop条件是null字节。
（boost使用hash_range ，它是hash_combining链中的每个元素我猜。）

许可证是zlib ，版权归JonathanMüller所有。 虽然我不相信如果一个oneliner实施了其他人的研究（ Fowler-Noll-Vo ），它就可以获得合法许可。