10

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

  • 可以用几行代码写，因为固件必须尽可能少；
  • 资源消耗低，特别是内存（最好小于 100 字节）；
  • 足够强大，以至于在字符串的任何位置更改单个字符都会改变整体摘要。

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

4

4 回答 4

10

没有机会在 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-10T19:12:45.030 回答
4

正如 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-10T21:40:24.010 回答
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

于 2012-11-10T19:17:49.917 回答
2

我有完全相同的要求，在取消 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;
}

看来他正在使用尾递归进行循环。停止条件是null字节。
（我猜，提升使用hash_range的是hash_combining链中的每个元素。）

许可证是zlib，版权是 Jonathan Müller。虽然我不相信如果执行其他人的研究（Fowler-Noll-Vo），oneliner 可以获得合法许可。

于 2018-04-19T09:13:53.077 回答