Kombinieren von Hashes für eine geordnete Menge

Question

Eine akzeptierte Möglichkeit, zwei Hashes von verschiedenen Objekten zu kombinieren, ist die Verwendung von XOR. Dies ist sinnvoll, aber wie im zweiten Kommentar von Thomas Pornin im folgenden Post erwähnt, XOR ist kommutativ, was bedeutet, dass, wenn Sie jedes Element in einer Menge Hash-und kombinieren sie mit XOR, jede Reihenfolge, die Sie tun, wird immer dazu führen die gleiche Hash:

Why is XOR the default way to combine hashes?

Was ist ein guter Weg Hashes zu kombinieren, die Sie Auftrag abhängig sein wollen? Wenn es für die Größe spezifisch ist, was sind einige bekannte Techniken für 32 Bit und für 64 Bit?

Answer 1

Um die resultierende Hash-Reihenfolge abhängig zu machen, muss im Algorithmus ein sequentieller (d. H. Nicht-statischer) Aspekt vorhanden sein. Die gebräuchlichste Technik ist wahrscheinlich die von Cyclic Redundancy Checks (CRC).

CRC kann in Hardware als ein Schieberegister mit XOR-Ed-Feedback implementiert werden. Ein solches Schieberegister wirkt als deterministischer Zufallszahlengenerator. Wenn der Anfangszustand derselbe ist, wird er immer dieselbe Sequenz von Zuständen durchlaufen. Diese Zustände werden bei der CRC-Signaturberechnung verwendet, um die Daten in einer wiederholbaren Weise zu XOR zu machen.

Um zwei Hash-Werte zu kombinieren, würden Sie sie zusammen mit einem dritten Wert aus einem CRC-Algorithmus XOR. Dies könnte berechnet oder aus einer Look-up table.-

Beliebte CRC-Codes genommen werden:

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

Classless.Hasher mehr enthält Details.

C# - Implementierungen finden Sie in HashLib.