use*_*832 4 algorithm hash cryptography
我想使用单向散列算法(无冲突)将32位整数转换为36位整数.
任何人都可以解释如何做到这一点？
"单向"意味着,很难弄清楚x给出的哈希结果h(x)是什么.由于术语"硬"没有明确定义,因此对于单向函数也没有明确的定义.
"无碰撞"意味着对于x和y的每一对,h(x)不同于h(y),其中x与y不同.这是一个明确的定义,但很难证明h(x)是否是一个单向函数.您必须比较每对两个32位数的哈希结果,并测试它们是否不同.
执行此操作的最佳方法是计算所有可能的h(x)并将它们与x一起存储在数组中.然后用h(x)对数组进行排序,然后遍历此列表并测试两个邻居是否具有相同的h(x).如果找不到相同的邻居,则哈希函数不会发生冲突.
但是:如果你真的能做到这一点,你的功能并不能真正成为一个单向功能,因为你刚才生成证明碰撞freenes列出的是一个非常快速的查找表,可以让你找到X每股H (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 $ -notebook绝对没问题.一旦你拥有它,它很容易证明它是否真的无碰撞,但通过构建这个表你也证明它不是单向函数!
那么什么是最好的解决方案？
在第1步之后,该列表将包含6,25%的冲突(大约2.684亿次冲突).在每次迭代中,您都会将碰撞次数减少到其第16个部分.它将花费大约8次迭代来消除所有的碰撞.
这38 GB表现在是超快速绝对无冲突的哈希函数.并且它是单向的,因为任何32到36位的散列函数都可以.含义:没有其他无冲突的哈希函数,在给定的h(x)中找到x更难.