密码安全加法哈希函数

Question

我正在研究基于Fountain Code的文件传输系统.在此系统中,下载数据块,并与xor函数结合使用.我想在块到达时验证它们.

我需要的是加密安全散列函数,它具有以下属性:

哈希(A)^哈希(B)==哈希(A ^ B)

这样的事情存在吗？

注意:数据块必须与xor函数组合,散列可以与您喜欢的任何函数组合,只要它的计算成本相当便宜.

Answer 1

如果您要求的身份完全正确

Hash(A) ^ Hash(B) == Hash(A ^ B)

那么不,没有这种加密安全散列函数是可能的.这是因为您的函数将是一个线性映射(在具有两个元素的字段上),从可能块的空间到可能的散列空间.

这简单来说意味着什么？

好吧,假设您的地图采用长度为6的块并返回长度为3的哈希值,并且这些是一些哈希值:

Hash(000001) = 010
Hash(000010) = 111
Hash(000100) = 001
Hash(001000) = 101
Hash(010000) = 110
Hash(100000) = 001

然后,您可以通过上述线性组合计算任何给定块的哈希值.例如,

Hash(101000) = Hash(100000) ^ Hash(001000) = 001 ^ 101 = 100.

这意味着您的哈希函数可以用6乘3矩阵表示.

这意味着什么？

维基百科将理想的加密哈希函数定义为具有四个主要或重要属性:

• 很容易计算任何给定消息的哈希值,
• 找到具有给定哈希的消息是不可行的,
• 在不改变其散列的情况下修改消息是不可行的,
• 找到具有相同散列的两个不同消息是不可行的.

当然,第一个属性可能是真的,但其余属性不是.反转哈希函数就像求解线性方程组一样简单,这很容易.我假设你已经为实数上的线性映射做了这个,但是完全相同的方法在这里工作.

如果您发现的元素内核的散列函数,也就是说,一个消息K,从而Hash(K)为全零,则最后一个属性也会失败.接受任何信息M; 那么M与M^K将具有相同的哈希值,因为Hash(M^K) = Hash(M)^Hash(K) = Hash(M)^0 = Hash(M).找到内核的元素也很容易.

第三个属性有点困难,但也可以打破.(例如,假设您正在散列一个合法的合同.找到一些可以修改某些流浪逗号的地方.考虑这些变化对散列函数的影响,然后求解线性方程组.)

Answer 2

你想要的是一个同态哈希.我不了解最新的发展,但我看到的那个非常 - 几乎不可行 - 计算速度慢.原来的纸在这里,并与一些改进它采用的是随访是在这里.

对于组合块,哈希通常要求您在素数域中使用加法.如果您正在使用喷泉代码,则不必使用xor,但任何可逆功能都可以,并且包括添加.上面描述的散列用于素数域中的加法和乘法,并且可证明是安全的.