我想使用一种单向散列算法（无冲突）将 32 位整数转换为 36 位整数。
谁能解释如何做到这一点？
问问题
2178 次
2 回答
8
“单向”意味着“很难”弄清楚 x 给出了哈希结果 h(x)。由于术语“硬”没有明确定义，因此也没有明确定义什么是单向函数。
“无冲突”意味着对于每对 x 和 y，h(x) 与 h(y) 不同，其中 x 与 y 不同。这是一个明确的定义，但很难证明 h(x) 是否真的是单向函数。您必须比较每对两个 32 位数字的哈希结果并测试它们是否不同。
最好的方法是计算所有可能的 h(x) 并将它们与它们的 x 一起存储在一个数组中。然后按 h(x) 对数组进行排序，然后遍历这个列表并测试两个邻居是否具有相同的 h(x)。如果你没有找到相同的邻居，你的散列函数就没有冲突。
但是：如果你真的能做到这一点，你的函数就不能真正成为单向函数，因为你刚刚生成的证明无碰撞的列表是一个非常快速的查找表，它可以让你找到每个 h 的 x (x) 在 log(n) 的搜索时间内。这甚至可能比从 x 计算 h(x) 更快。
所以让我们弄清楚，这真的需要多长时间
32 位整数是 0 到 4294967295 之间的数字。假设从 x 计算 h(x) 需要 0.1 ms。根据散列算法，即使在便宜的笔记本上也是现实的。因此，在 1 秒内，您获得 10,000 个哈希数字，在一天内获得 864,000,000 个数字。您只需 5 天就可以计算出所有可能的数字并将它们存储在磁盘上。
每个条目对于 32 位数字有 4 个字节，对于 36 位散列有 5 个字节。制作 9 个字节。所以完整的表有 38,654,705,664 字节。这是 38 GB。您可以将其存储在每个低预算笔记本上。这张表的排序需要几分钟，这不计入我们计算所需的 5 天。
因此，在 200 美元的二手笔记本上构建这张桌子绝对没有问题。一旦你有了它，很容易证明它是否真的没有碰撞，但是通过构建这个表你也证明了它不是一个单向函数！
那么最好的解决方案是什么？
- 生成一个包含 4,294,967,296 个随机 36 位数字的列表，为每个条目添加一个 32 位数字，即条目行号（从 0 开始）。
- 对列表进行排序。
- 重置 did-change-a-number-flag
- 浏览列表。将实际条目与前一个条目进行比较。如果它们不同，请转到步骤 7。
- 用新的随机 36 位数替换 36 位数
- 设置 did-change-a-number-flag
- 如果您到达列表的末尾：是否设置了标志？如果是，请转到步骤 2。
- 按 32 位数字（前行号）对列表进行排序
在第 1 步之后，列表将包含 6.25% 的碰撞（约 2.684 亿次碰撞）。在每次迭代中，您将碰撞次数减少到第 16 部分。消除所有冲突大约需要 8 次迭代。
这个 38 GB 的表现在是您的超快速绝对无冲突哈希函数。它与任何 32 到 36 位散列函数一样是单向的。含义：对于给定的 h(x)，没有其他无冲突的散列函数更难找到 x。
于 2012-07-24T07:48:30.153 回答
3
如果 38 GB 对您来说听起来并不小，您可以使用带有 36 位块的Luby-Rackoff 结构。
首先，将您的 32 位输入填充为 36 位，但您喜欢。
然后生成一堆独立的随机密钥Ki。使它们尽可能大。比如说，80 位左右。将这些存储Ki在安全的地方，因为您每次“散列”时都会使用它们。
对于轮函数F(Ki,x)，使用SHA1(Ki . x)截断为 18 位。
这四轮应该做得很好。它肯定是一对一的，因为如果你有Ki.
（是的，是的，“永远不要发明你自己的密码学”。但是只有 32 位的输入，谁在乎呢？）
于 2012-07-27T03:01:03.047 回答