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

Question

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

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

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

Answer 1

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

正如 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);
}