3

我必须实现一个简单的散列算法。

输入数据：

  • 值（16 位整数）。
  • 密钥（任意长度）。

输出数据：

  • 6 位哈希（数字 0-63）。

要求：

  • 如果您只有输入值而没有 key ，实际上应该不可能预测哈希值。更具体地说：如果我知道 x < M 的 hash(x)，那么在不知道密钥的情况下应该很难预测 hash(M)。

可能的解决方案：

  1. 保持完整映射作为关键。所以密钥的长度为 2^16*6 位。我的情况太长了。
  2. 线性代码。Key 是一个生成矩阵。它的长度是16*6。但是使用几个已知的哈希值很容易找到生成矩阵。

还有其他可能吗？

4

2 回答 2

5

HMAC似乎是您想要的。因此，您可能会使用基于 SHA 的 HMAC 并仅使用生成的哈希的子字符串。这应该是相对安全的，因为加密哈希的位应该尽可能独立和不可预测。

但是，根据您的环境，这可能会花费过多的处理时间，因此您可能必须选择更简单的散列方案来构建 HMAC。

原始答案评论中的讨论基于：

由于您无论如何都可以忘记加密属性（通过对 5 位哈希的暴力攻击来发现冲突是微不足道的），您不妨使用 CRC 或汉明码之类的东西并免费获得错误检测

于 2012-04-10T12:24:56.670 回答
1

Mensi 建议使用截断的HMAC是一个很好的建议，但是如果您碰巧在一个高度受限的系统上并且想要更快或更简单的东西，您可以采用任何分组密码，加密您的 16 位值（填充到一个完整的块) 并将结果截断为 6 位。

与计算伪随机函数的 HMAC 不同，分组密码是伪随机排列——每个输入映射到不同的输出。但是，当您丢弃分组密码输出中除了 6 位之外的所有内容时，剩下的部分看起来非常像伪随机函数。对重复输出会有一个非常小的偏差，但是（假设分组密码的块大小远大于 6 位，它应该是）它会小到几乎无法检测到。

对于非常低端的系统来说，一个好的分组密码选择可能是TEA或其继任者XTEA和XXTEA。虽然对这些密码有一些已知的攻击，但它们都需要对密码进行更广泛的访问，而不是在您的应用程序中应该有的权限。

于 2013-01-21T20:34:14.190 回答