累积哈希值

Question

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

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

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

Answer 1

如果您正在寻找的是字符串上的哈希函数，例如 hash(s1+s2) = hash(s1) + hash(s2)，我非常确定具有此属性的所有函数哈希都是对于固定函数 hash_char，形式为 （字符串中所有字符 c 的 hash_char(c) 之和）。

这并不能构成一个非常好的哈希函数。您没有记错您在 adler32 中看到的内容吗？

Answer 2

Adler32 不是哈希函数。
没有具有此属性的良好哈希函数。

然而，有一些加密函数具有类似的特性；称为同态。
基本上：

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

其中E是加密函数，D是加密函数，文本是数字（或序列化为数字的数据）。请注意，使用 + & 以外的操作的方案* 确实存在。

两个示例方案：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"), "a" ), "a" )
= G ( G ( H0, "a" ), "a" ), "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 值。 （谢谢 Pete Kirkham 指出我的这个错误）。

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