Dre*_*dan 1 lookup hash perfect-hash
我被要求寻找一个完美的散列/单向函数,以便能够散列10 ^ 11个数字.然而,由于我们将使用嵌入式设备,它将没有内存来存储相关的存储桶,所以我想知道是否有可能没有它们的体面(最小)完美哈希？
计划是使用设备来散列数字,我们使用彩虹表或使用散列作为偏移量的文件.
干杯
编辑:
我会尝试提供更多信息:)
1)10 ^ 11实际上现在是10 ^ 10,这样可以更容易.这个数字是可能的组合.所以我们可以得到介于0000000001和10000000000(10 ^ 10)之间的数字.
2)计划对我们来说是单向函数的一部分,使数字安全,所以我们可以通过不安全的方式发送它.然后我们将使用彩虹表在另一端查找原始数字.问题是设备的源通常有512k-4Meg的内存使用.
3)它必须是完美的 - 我们100%不会发生碰撞.
EDIT2:
4)我们不能使用加密,因为我们已经被告知它在设备上并不是真的可能,如果我们可以的话,关键人物将是一场噩梦.
EDIT3:
由于这是不明智的,现在纯粹的学术问题(我保证)
好的,既然你已经澄清了你想要做的事情,我改写了我的答案.
总结一下:使用真正的加密算法.
首先,让我回顾一下为什么你的哈希系统是一个坏主意.
据我了解,您建议的系统是这样的:
您的嵌入式系统(我将称之为C)正在发送某种数据空间为10 ^ 11的数据.这些数据需要在传输到某种服务器(我称之为S)时保密.
您的建议是将值发送hash(salt + data)给S.然后,S将使用彩虹表来反转此哈希值并恢复数据.salt是C和S都知道的共享值.
加密算法,当你把它煮沸时,是任何给你机密的算法.由于您的目标是机密性,任何满足您目标的算法都是加密算法,包括此算法.
首先,存在不可避免的碰撞机会.而且,碰撞值的集合每天都不同.
其次,即使对于合法服务器S,解密也是CPU和内存密集型的.更改盐更加昂贵.
第三,虽然你声明的目标是避免密钥管理,但你的盐是关键!你根本没有解决密钥管理问题; 任何有盐的人都能够尽可能地破解信息.
第四,它只能从C到S使用.您的嵌入式系统C将没有足够的计算资源来反转哈希值,并且只能发送数据.
最安全的散列算法与合理的分组密码一样计算成本也很高,如果不是更糟的话.例如,SHA-1要求对每个512位块执行以下操作:
每512比特的消息有一个块,最后加上一个可能的额外块.这是每个块的1136个二进制操作(不计算内存操作),或每个字节大约16个操作.
为了进行比较,RC4加密算法每个字节需要四个操作(三个添加,加上消息上的xor),加上两个数组读取和两个数组写入.它还只需要258个字节的工作内存,而SHA-1的峰值为368个字节.
对于任何机密性系统,您必须拥有某种秘密.如果您没有秘密,那么其他任何人都可以实现相同的解码算法,并且您的数据将暴露给全世界.
所以,你有两个选择来保密.一种选择是使加密/解密算法保密.但是,如果算法的代码(或二进制文件)泄漏,则会丢失 - 更换此类算法非常困难.
因此,秘密通常易于更换 - 这就是我们所说的关键.
您建议的哈希算法的使用需要一个盐 - 这是系统中唯一的秘密,因此是一个关键.无论您是否喜欢,您都必须仔细管理此密钥.如果泄漏比其他密钥更换更难 - 你每次更改时都需要花费很多CPU时间来生成新的彩虹表!
使用真正的加密算法,并花一些时间实际考虑密钥管理.这些问题之前已经解决了.
首先,使用真正的加密算法.AES专为满足高性能和低RAM要求而设计.您也可以像我之前提到的那样使用像RC4这样的流密码 - 用RC4注意的事情是,你必须丢弃密码输出的前4千字节左右,否则你将容易受到密码的攻击困扰WEP的攻击.
其次,考虑密钥管理.一种选择是简单地将密钥刻录到每个客户端,如果客户端受到损害,则物理地外出并替换它.如果您可以轻松地访问所有客户端,这是合理的.
否则,如果您不关心中间人攻击,您可以简单地使用Diffie-Hellman密钥交换来协商S和C之间的共享密钥.如果您关注MitM,那么您需要开始查看ECDSA或其他东西来验证从DH交换机获得的密钥 - 请注意,当你开始走这条路时,很容易出错.我建议在那时实施TLS.它不仅仅是嵌入式系统的功能 - 实际上,已经有许多 嵌入式 商业(和开源) 库 可用.如果您没有实现TLS,那么在实现之前至少要让专业的密码学家查看您的算法.