一个单向哈希函数（无碰撞），将32位整数转换为36位整数？

Question

4

我希望使用单向哈希算法（无碰撞）将32位整数转换为36位整数，有人能解释一下如何做吗？

- user1548832

2

“单向”和“无冲突”一起实现很困难。如果它已经足够难以被认为是“单向”，那么证明它也是无冲突的可能就太难了。 - Mysticial

2

实际上，使用现代处理器，这不可能是单向的。32位可以很容易地被暴力破解... - Mysticial

1

我假设OP的意思是，“单向”指从h(x)中获取x（不切实际）。 - Mysticial

4

根据所述问题，(long)x << 4 可以解决问题。我会将其翻译为：将 x 转换为 long 类型后左移 4 位，可以解决该问题。 - BlueRaja - Danny Pflughoeft

3

恒等函数也可以使用。 - Rafe

显示剩余3条评论

2个回答

3

如果38GB对你来说不算小的话，你可以使用36位块的Luby-Rackoff construction。

首先，按照你喜欢的方式将32位输入填充到36位。

然后生成一堆独立的随机密钥Ki。可以设置任意大小，比如80位左右。将这些Ki存放在一个安全的地方，因为每次“哈希”时都会用到它们。

对于轮函数F(Ki,x)，使用截断为18位的SHA1(Ki . x)。

做四轮就足够了。如果有Ki，它肯定是一对一的，因为它实际上是可逆的。

（是的，是的，“永远不要发明自己的加密”。但是只有32位的输入，谁在乎呢？）

- Nemo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hubert Schölnast · Accepted Answer

“单向”指的是很难从哈希结果h(x)反推出x。由于“难”这个术语没有明确定义，因此也没有一个明确的单向函数定义。

“无冲突”指的是对于每一对不同的x和y，它们的哈希值h(x)和h(y)都不相同。这是一个明确定义，但很难证明h(x)真的是一个单向函数。你必须比较每一对32位数字的哈希结果并测试它们是否不同。

最好的方法是计算所有可能的h(x)并将它们与它们的x一起存储在数组中。然后按h(x)对数组进行排序，然后遍历此列表并测试两个相邻元素是否具有相同的h(x)。如果您找不到相同的相邻元素，则您的哈希函数就没有冲突。

但是，如果您确实能做到这一点，那么您的函数实际上不能是一个单向函数，因为您刚刚生成的用于证明无碰撞性的列表是一个非常快速的查找表，可让您在对数(n)的搜索时间内找到每个h(x)的x。这甚至可能比从x计算h(x)更快。

所以让我们来看看这需要多长时间。

32位整数是介于0到4294967295之间的数字。假设从x计算h(x)需要0.1毫秒。根据哈希算法，即使在廉价笔记本上，这也是现实的。因此，在1秒钟内，您可以得到10,000个哈希数字，并且在一天内可以获得864,000,000个数字。只需要5天就可以计算出所有可能的数字并将它们存储在磁盘上。

每个条目有4个字节用于32位数字和5个字节用于36位哈希值。共9个字节。因此，完整的表占用38,654,705,664个字节。这是38GB。您可以将其存储在任何低成本笔记本电脑上。对该表进行排序需要几分钟，这不包括我们需要计算的5天时间。

因此，在200美元的二手笔记本上构建此表绝对没有问题。一旦拥有了它，很容易证明它是否真的是无冲突的，但是通过构建此表，您还证明它不是一个单向函数！

那么最好的解决方案是什么呢？

在步骤1之后，列表将包含6.25％的冲突（约268.4百万个冲突）。在每次迭代中，您将将冲突数量减少到其16分之一。需要大约8次迭代才能消除所有冲突。

这个38 GB的表现在是您超快速绝对无冲突的哈希函数。它和任何32位到36位哈希函数一样单向。意思是：没有其他无冲突哈希函数可以更难找到给定h(x)的x。