Combinaison de hachages pour un ensemble ordonné

Question

Une méthode acceptée pour combiner deux hachages à partir d'objets différents consiste à utiliser XOR. Cela a du sens, mais comme mentionné dans le deuxième commentaire de Thomas Pornin dans le post ci-dessous, XOR est commutatif, ce qui signifie que si vous hachez chaque élément d'un ensemble et les combinez avec XOR, tout ordre que vous ferez le même hachage:

Why is XOR the default way to combine hashes?

Qu'est-ce qu'un bon moyen de combiner hash que vous voulez dépendre l'ordre? Si elle est spécifique à la taille, quelles sont les techniques connues en 32 bits et en 64 bits?

Answer 1

Pour rendre l'ordre de hachage résultant dépendant, il doit y avoir un aspect séquentiel (c'est-à-dire non statique) dans l'algorithme. La technique la plus courante est probablement celle de Cyclic Redundancy Checks (CRC).

CRC peut être implémenté dans le matériel en tant que registre à décalage avec rétroaction XOR-ed. Un tel registre de décalage agit comme un générateur de nombres aléatoires déterministes. À condition que l'état initial soit le même, il passera toujours par la même séquence d'états. Ces états sont utilisés dans le calcul de signature CRC pour XOR les données d'une manière répétable.

Pour combiner deux valeurs de hachage, vous devez les extraire avec une troisième valeur d'un algorithme CRC. Cela peut être calculé ou tiré d'une consultation table.-

codes CRC Populaire:

09 bits (CRC-8) 
17 bits (CRC-16) 
33 bits (CRC-32) 
65 bits (CRC-64) 

Classless.Hasher fournit plus de détails.

Les implémentations C# peuvent être trouvées dans HashLib.