Bei einer Menge von 100 verschiedenen Strings gleicher Länge, wie können Sie die Wahrscheinlichkeit quantifizieren, dass eine SHA1 Digest Kollision für die Strings unwahrscheinlich ist ...?Wahrscheinlichkeit von SHA1 Kollisionen
Sind der 160-Bit-Hash-Wert von SHA-1 erzeugt, die groß genug Fingerabdrucks jeden Block, um sicherzustellen, einzigartig sind? zufällige Hashwerte mit einer gleichmäßigen Verteilung Angenommen, eine Sammlung von n verschiedenen Datenblöcken und ein Hash Funktion, die b Bits erzeugt, die Wahrscheinlichkeit P, dass es wird ein oder mehrere Kollisionen durch die Anzahl der Paare begrenzt ist von Blöcken multipliziert mit der Wahrscheinlichkeit, dass ein gegebenes Paar kollidieren wird.
(Quelle: http://bitcache.org/faq/hash-collision-probabilities)
Zusammenfassend ist die Wahrscheinlichkeit einer Kollision in der Größenordnung von 10^-45. Das ist sehr, sehr unwahrscheinlich. –
Aber SHA-1 ist keine gleichmäßige Verteilung, es könnte größer als diese obere Grenze sein. Ich bezweifle, dass diese Gleichung nicht korrekt ist. Zumindest das EQUAL. – Kamel
Diese Antwort berücksichtigt nicht die chinesische Entdeckung im Jahr 2005, wo sie in 2^69 Iterationen Kollisionen erzeugen können, statt der von Brute Force projizierten 2^80 https://www.schneier.com/blog/archives /2005/02/sha1_broken.html – Djarid
Das ist Birthday Problem - der Artikel bietet nette Näherungen, die es recht einfach machen, die Wahrscheinlichkeit zu schätzen. Die tatsächliche Wahrscheinlichkeit wird sehr, sehr sehr niedrig sein - siehe this question für ein Beispiel.
Nun, die Wahrscheinlichkeit einer Kollision wäre 1 - ((2^160 - 1)/2^160) * ((2^160 - 2)/2^160) * ... * ((2^160 - 99)/2^160).
Denken Sie an die Wahrscheinlichkeit einer Kollision von 2 Elementen in einem Raum von 10. Der erste Artikel ist einzigartig mit Wahrscheinlichkeit 100%. Die zweite ist einzigartig mit Wahrscheinlichkeit 9/10. Daher ist die Wahrscheinlichkeit, dass beide eindeutig sind, 100% * 90% und die Wahrscheinlichkeit einer Kollision ist 1 - (100% * 90%) oder 1 - ((10 - 0)/10) * ((10 - 1))/10) oder 1 - ((10 - 1)/10).
Es ist ziemlich unwahrscheinlich. Sie müssen viel mehr Zeichenfolgen haben, damit es eine entfernte Möglichkeit ist.
Werfen Sie einen Blick auf die Tabelle auf this page on Wikipedia; interpoliere einfach zwischen den Zeilen für 128 Bits und 256 Bits.
klären, wie kann man 'anders, aber gleich lang' Strings haben? – KevinDTimm
@kevindtimm "a", "b", "c" sind gleich lang, aber verschiedene Strings –
Ich nehme an, die Strings sind mindestens 20 Bytes lang. Sonst wären die Chancen einer Kollision natürlich höher. :) –