0

我之前在这里读过 SO（编辑： 增量校验和），有一些校验和算法（我认为其中一个是 adler32）支持以下属性：

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

请注意，结果只是展示我想要归档的示例。我已经在 PHP 中使用 adler 和 fletcher 模块尝试了一些带有哈希扩展的示例，但这些值似乎没有加起来。有人可以给我看一些实现示例吗？

4

5 回答 5

3

如果您正在寻找的是这样的字符串散列函数hash(s1+s2) = hash(s1) + hash(s2)，我很确定所有具有此属性的散列函数都(sum of the hash_char(c) for all the chars c in the string)具有固定函数的形式hash_char。

这并不构成一个非常好的散列函数。您不会记错您对 adler32 的看法吗？

于 2009-09-29T19:59:56.030 回答
2

Adler32 is not a hash function.
There are no good hash functions with this property.

There are, however, encryption functions with a similar property; known as homomorphism.
Basically:

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

Where E is the encryption function, D is the encryption function, and the texts are numbers (or data serialized as a number). Note that schemes using operations other than + & * do exist.

Two examples schemes: ElGamal, and Paillier. Both are slow, which is a common feature of asymmetric encryption schemes. Both of these examples use * & +.

于 2009-09-29T21:21:15.783 回答
1

除非我误解了，否则如果没有不必要的碰撞次数，我看不出这是怎么可能的。

hash('cde') => 345 
hash('aaabcd') => 345
于 2009-09-29T19:50:15.657 回答
1

Adler32 是校验和算法而不是哈希，并且没有您描述的属性。

散列具有可以通过散列结果描述散列状态的属性是很常见的，所以如果

H ( "aaa" ) = G ( H0, "aaa" )

其中 G 是散列和与散列连接的函数，H0 是初始值，通常为零。然后

H ( "aaa" ) = G ( H("aa"), "a" ) = G ( G ( H("a"), "a" ), "a" ) = G ( G ( G ( H0, "a" ), "a" ), "a" )

But a function which is simply adding some function of the characters in the input together ( as is implied by your rule that G ( x .concat. y ) = G(x) + G(y) ) will collide for all permutations of that input.

One such function might create a 128 bit hash from an ASCII input:

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

which would have the property that 

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.
于 2009-09-29T20:26:01.467 回答
0

鉴于 Alder32 算法描述，我看不出您描述的关于字符串连接的属性是如何可能的。

编辑：删除了有缺陷的演示，即哈希的这种属性是不可能的。实际上，这种散列的一个示例是简单地添加（可能以某个大数字为模，但这是可以理解的）输入中字符的 ASCII 值。（感谢Pete Kirkham 指出我的这个错误）。

您可能指的是同态加密算法，而不是 Alder32。您可以在此处找到此类加密方案的列表。IBM 的研究人员 Craig Gentry 也宣布了他成功生产全同态加密，但我不知道此时是否发布了任何技术细节（这将是个大新闻，顺便说一句）。

于 2009-09-29T19:57:53.317 回答