累积哈希

Question

我读之前在这里所以(编辑： 增校验)，有一些校验码算法(我认为那是adler32)支持下列财产：

adler32('abc'); // 123
adler32('def'); // 456
adler32('abcdef'); // 579 (123 + 456)

请注意，结果只是举例证明什么我想要达到的目标。我已经尝试了一些例子，与哈希扩展在PHP与阿德勒和弗莱彻的模块，但该数值似乎没有增加。有人可以告诉我一些执行情况的例子吗？

Answer 1

如果你正在寻找的是对字符串的哈希函数，使得hash(s1+s2) = hash(s1) + hash(s2)，我敢肯定，所有功能与这个属性散列的形式为(sum of the hash_char(c) for all the chars c in the string)的，对于一个固定功能hash_char。

这不会使一个很好的哈希函数。你不misremember你看到了有关的Adler32什么？

Answer 2

Adler32 不是散列函数。
有没有良好的散列函数与这种属性。

然而，有加密功能与一个类似的财产；被称为 homomorphism.
基本上:

E(text1)*E(text2)=cipher  
D(cipher) = text1 + text2  

E是加密功能的加密功能、和文字编号为(或数据序列化为数字)。注意，方案的使用操作的其他比+&*确实存在。

两个例子计划： ElGamal, ， Paillier.两者都是 慢, ，这是一个共同特征的非对称加密方案。这两个例子使用的*&+.

Answer 3

除非我误解我看不出，这是可能的，而不碰撞的不必要的次数。

hash('cde') => 345 
hash('aaabcd') => 345

Answer 4

的Adler32是校验和算法，而不是乱码，没有你描述的属性。

这是相当常见的散列具有所述散列的状态可以由散列的结果来描述的属性，因此，如果

H（ “AAA”）= G（H0， “AAA”）

其中G是散列的函数以及级联到哈希，和H0是初始值，通常为零。然后

H（ “AAA”）= G（H（ “AA”）， “a”）的                = G（G（H（ “一个”）， “一个”）， “a”）的                = G（G（G（H0， “一个”）， “一个”）， “a”）的

但是，其被简单地增加在输入一起字符的某些功能（如由您的规则暗示G（X .concat。Y）= G（x）+ G（Y））将碰撞的所有的函数该输入的置换。

一个这样的函数可以从一个ASCII输入创建128位散列：

H(x) = sum ( b => 1 << b foreach byte b in x ) 

这将具有这样的特性：

H("abcdef") == H("abc") + H("def") 
            == H("a") + H("b") + H("c") + H("d") + H("e") + H("f") 
            == H("abcdfe")
            == H("abcfde")
            == H("abcfed")
 etc.

Answer 5

在考虑Alder32算法描述，我没有看到你关于字符串的串联说明财产是如何可能的。

修改除去有缺陷的演示，对于一个散列这样的属性是不可能的。事实上，这样的散列的一个例子是，只是增加了一个（也许还有一些模大数目，但这是可以理解的），在输入字符的ASCII值。 （谢谢皮特Kirkham的指向我的这个错误）。

而不是Alder32你可能是指为同态加密算法。您可能会发现这样的加密方案这里的列表。克雷格·金特里，IBM的研究，同时宣布他的成功与生产的全同态加密，但我不知道是否有任何技术细节在这个时候发布（这将是个大新闻，BTW）。