Hashes cumulatifs

Question

Je l'ai lu avant ici sur le SO ( EDIT: checksums incrémentielles ) qu'il y sont des algorithmes de contrôle (je pense que l'un d'entre eux est adler32) qui prennent en charge la propriété suivante:

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

S'il vous plaît noter que les résultats ne sont que des exemples pour démontrer ce que je veux archieve. J'ai essayé quelques exemples avec l'extension de hachage en PHP avec les modules et adler fletcher mais les valeurs ne semblent pas additionner. Quelqu'un peut-il me montrer des exemples de mise en œuvre?

Answer 1

Si ce que vous recherchez est une fonction de hachage sur des chaînes telles que hash(s1+s2) = hash(s1) + hash(s2), je suis sûr que toutes les fonctions de hachage avec cette propriété sont de la forme (sum of the hash_char(c) for all the chars c in the string), pour une hash_char fonction fixe.

Cela ne fait pas une très bonne fonction de hachage. N'êtes-vous pas misremember ce que vous avez vu à propos adler32?

Answer 2

Adler32 n'est pas une fonction de hachage.
Il n'y a pas de bonnes fonctions de hachage avec cette propriété.

Il y a, cependant, des fonctions de chiffrement avec une propriété similaire; connu sous le nom homomorphisme .
En gros:

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

où E est la fonction de chiffrement, D est la fonction de chiffrement, et les textes sont des nombres (ou les données sérialisés en un nombre). Notez que les systèmes utilisant des opérations autres que + et * existent.

Deux exemples schémas: ElGamal et Paillier . Les deux sont lent , qui est une caractéristique commune des systèmes de cryptage asymétriques. Ces deux exemples utilisent * et +.

Answer 3

A moins que je comprends mal, je ne vois pas comment cela est possible sans un nombre inutile de collisions.

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

Answer 4

Adler32 est un algorithme de contrôle plutôt qu'un hachage, et ne possède pas la propriété que vous décrivez.

Il est assez courant pour les hachages d'avoir la propriété que l'état du hachage peut être décrite par le résultat du hachage, donc si

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

où G est la fonction de hachage et la concaténation de la valeur de hachage, et H0 est une valeur initiale, souvent nul. Ensuite,

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

Mais une fonction qui est tout simplement en ajoutant une fonction des caractères de l'entrée ensemble (comme le laisse entendre par votre règle G (x .concat. Y) = G (x) + G (y)) va entrer en collision pour tous les permutations de cette entrée.

Une telle fonction peut créer un hachage 128 bits à partir d'une entrée ASCII:

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

qui aurait la propriété que

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

En vue de Alder32 Description de l'algorithme, je ne vois pas comment la propriété que vous décrivez en ce qui concerne la concaténation de chaîne est possible.

Modifier supprimé démo défectueuse que cette propriété pour un hachage est impossible. En effet, un exemple d'un tel hachage est celui qui ajoute simplement (bien modulo peut-être un grand nombre, mais qui est compréhensible) la valeur ASCII des caractères dans l'entrée. (Merci Pete Kirkham de signaler cette erreur de la mine).

Au lieu de Alder32 vous faites allusion chiffrement homomorphique algorithmes . Vous pouvez trouver une liste de ces systèmes de cryptage . Craig Gentry, une recherche chez IBM, a également annoncé son succès à la production cryptage entièrement homomorphic , mais je ne sais pas si tous les détails techniques ont été publiés à ce moment (ce serait de grandes nouvelles, BTW).