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

Question

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

• 可写的几行代码，因为固件必须保持尽可能少；
• 资源消耗低，特别是ram (最好小于100个字节)；
• 足够强，在字符串的任何一点上更改单个字符都会改变整个摘要。

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

Answer 1

正如AndrewTomazos所说，不可能用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);
}

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