Zyklische polynomiale Hash-Kollisionen verstehen

Wie Länge Kollisionen bewirkt

Das ist einfach eine Frage von Permutationen.

  

Wenn ich kleine Hash-Werte (7-8 Bits) verwende, dann gibt es einige Kollisionen

Nun, lasst uns das analysieren. Bei 8 Bits gibt es 2^8 mögliche binäre Sequenzen, die für jede gegebene Eingabe erzeugt werden können. Das sind 256 mögliche Hash-Werte, die generiert werden können, was theoretisch bedeutet, dass alle erzeugten% code_d% -Verschlüsselungswerte eine Kollision garantieren. Dies wird das Geburtstagsproblem genannt.

  

Wenn ich die Bits im Hash-Wert auf 31 erhöhen, gibt es 0 Kollisionen - alle Ngrams werden verschiedenen Hash-Werten zugeordnet.

Nun, lassen Sie uns die gleiche Logik anwenden. Mit 31 Bit Genauigkeit haben wir 256 mögliche Kombinationen. Das ist 2^31 mögliche Kombinationen. Und wir können dies verallgemeinern auf:

Dies ist ein exponentielles Wachstum, weshalb Sie mit 8 Bits viele Kollisionen gefunden haben und mit 31 Bits sehr wenig Kollisionen gefunden haben.

Wie wirkt sich dies auf Kollisionen aus?

Nun, mit einer sehr kleinen Anzahl von Werten und einer gleichen Chance, dass jeder dieser Werte einer Eingabe zugeordnet wird, haben Sie Folgendes:

Wenn 2147483648 gleich X ist, haben Sie eine 256 Chance einer Kollision, beim ersten Mal. Dann haben Sie eine Wahrscheinlichkeit von 1/256 einer Kollision, wenn ein anderer Wert generiert wird. Bis Sie schließlich 255 verschiedene Werte generiert haben und Sie eine 2/256 Chance auf eine Kollision haben. Beim nächsten Mal wird es offensichtlich eine 255/256 Chance oder 256/256 , was eine probabilistische Gewissheit ist. Offensichtlich wird es diesen Punkt normalerweise nicht erreichen. Eine Kollision wird wahrscheinlich viel mehr als alle 1 Zyklen auftreten. In der Tat sagt uns das Birthday-Paradox, dass wir eine Kollision erwarten können, nachdem 256 message digest-Werte generiert wurden. Wir folgen unserem Beispiel, nachdem wir 2^N/2 unique hashes erstellt haben. Wir wissen jedoch, dass es passieren muss, mindestens , alle 16 Zyklen. Was nicht gut ist!

Was dies auf einer mathematischen Ebene bedeutet, ist, dass die Wahrscheinlichkeit einer Kollision umgekehrt proportional zur möglichen Anzahl von Ausgaben ist, weshalb wir die Größe unseres Nachrichten-Digest auf erhöhen müssen eine angemessene Länge.

Eine Anmerkung zu Hashalgorithmen

Kollisionen sind absolut unvermeidbar. Dies liegt daran, dass es eine extrem große Anzahl von möglichen Eingaben gibt (2 ^ Alle möglichen Zeichencodes) und eine endliche Anzahl von möglichen Ausgaben (wie oben gezeigt).

Wenn Sie Hash-Werte von 8 Bit haben, ist die Gesamtzahl der möglichen Werte 256 - das heißt, wenn Sie 257 verschiedene N-Gramme haseln, wird es sicher mindestens eine Kollision geben (... und sehr wahrscheinlich werden Sie bekommen) viel mehr Kollisionen, sogar mit weniger als 257 N-Gramm) - und dies wird unabhängig vom Hashalgorithmus oder von den Daten, die gehashed werden.

Wenn Sie 32 Bit verwenden, beträgt die mögliche Gesamtzahl der Werte etwa 4 Milliarden - und die Wahrscheinlichkeit einer Kollision ist viel geringer.

Wie wählt man die Anzahl der Bits aus? Ich schätze, hängt von der Verwendung des Hashes ab. Wenn es verwendet wird, um die N-Gramme in einer Art von Hash-Datenstruktur (einem Wörterbuch) zu speichern, dann sollte es sich auf die mögliche Anzahl von "Buckets" der Datenstruktur beziehen - z. Wenn das Wörterbuch weniger als 256 Buckets hat, ist ein 8-Bit-Hash OK.

Siehe dies für etwas Hintergrund