string - 如何散列可变长度字符串

Question

我是加密/散列的初学者。而且我想知道如何将可变长度字符串（可能是 10 或 100 个字母）散列为固定长度代码，例如 128 位二进制，而不管底层编程语言如何，同时实现箱之间相对相等的冲突。

具体来说，如何处理不同输入的输入，并使哈希码均匀分布？

Answer 1

有许多不同的方法可以做到这一点。

对于非加密应用程序，通常通过按顺序迭代字符并应用一些操作将新字符的位与累积的散列位混合来散列字符串。您将如何执行此操作有很多变化。此处显示了一种常见的方法：

unsigned int kSmallPrime = /* some small prime */;
unsigned int kLargePrime = /* some large prime */;

unsigned int result = 0;

for (char ch: string) {
    result = (result * kSmallPrime + ch) % kLargePrime;
}

更复杂的组合步骤可以获得更好的分布。这些方法通常不要求字符串具有任何特定长度并且适用于任何长度的字符串。您返回的位数取决于您用于混合位的内部存储，尽管不一定有强有力的理论理由（除了经验证据）相信您有一个良好的分布。

对于加密应用程序，字符串散列函数通常源自分组密码。像Merkle-Damgard这样的结构让你从一个安全的分组密码开始，然后产生一个安全的散列函数。它们通过使用安全填充方案（确保不同的字符串在填充后最终不同的方案）将字符串填充到块大小的某个倍数来工作，将字符串分成块，并将它们散列在链中。然后最终输出来自底层分组密码，它自然地输出大量比特，并且良好的分布来自底层分组密码的强度，它（原则上）应该与随机无法区分。