哪些哈希算法支持任意位长度的二进制输入？

Question

背景

理论上，哈希函数可以从任意长度的二进制数据生成具有有界（通常是固定）长度的二进制数。

在实践中，规范和实现将输入长度限制为 8 的倍数。这是合理的，因为在实践中，客户端散列的二进制数据以字节块（而不是位）表示。

假设我们想要在不能假设输入二进制数据被分块为字节的上下文中使用哈希算法。

例如，我们要计算 13 位数据流的哈希值

0101111101111

。

此外，假设长度不可被 8 整除的任何二进制片段所预期的值与任何填充的字节整除表示形式明确不同。

例如，我们的系统要求 13 位

0101111101111

的含义与任何 16 位值根本不同（例如左填充

0000101111101111

或右填充

0101111101111000

）。 因此，它们的哈希值应该是不同的。

问题

• 哪些已建立的哈希算法可以兼容任意bit长度的输入二进制数据？

• 现有哪些工作和实现可以直接解决许多常见算法和库的这一限制？

注意

我认识到，截断的任意长度二进制数据和填充的字节块之间的区别可以通过使用其截断长度的字节可分割表示来标记填充的输入数据来改造为字节可分割的输入。 如果有一种冗余度较低的方法可用，似乎会更可取。

Answer 1

按照@MattTimmermans 的建议进行操作。在末尾添加

1

，然后填充以填充该字节。

如果你觉得这很浪费，你可以简单地截断你得到的哈希值的最后几位。您会稍微增加随机碰撞的几率，但它仍然是一个可用的哈希。

用位来指定实际的计算没有多大意义。 CPU 具有与特定长度的常见数据类型相对应的高度优化的操作。一个好的散列算法将利用这一点。尝试使用特定于位的优化进行滚动需要大量额外的工作，并且无法利用芯片已有的硬编码优化。