Birthday Paradox Calculator
Wie viele zufällige Werte braucht man, bis zwei davon wahrscheinlich übereinstimmen? Intuitiv schätzen die meisten diese Zahl deutlich zu hoch ein.
Mit diesem Rechner wählst du die Größe eines Wertebereichs und die Anzahl der Versuche und siehst sofort, wie wahrscheinlich mindestens eine Collision ist.
Birthday Collision Simulator
Wähle die Größe des Hashraums und die Anzahl erzeugter Hashwerte – die Wahrscheinlichkeit einer Hash Collision wird sofort exakt berechnet.
- Ausgabelänge
- 8 Bit
- Mögliche Hashwerte
- 28 = 256
- Erzeugte Hashwerte
- 20
- Mögliche Paare k(k−1)/2
- 190
- Exakte Wahrscheinlichkeit
- 53,3 %
- Näherung 1 − e^(−k(k−1)/(2N))
- ≈ 52,4 %
- Birthday Bound (Größenordnung)
- 24 ≈ 16
- 50-%-Schwelle √(2·N·ln 2)
- ≈ 18,8 (exakt ab 20)
Die exakte Wahrscheinlichkeit folgt aus P(keine Collision) = N/N × (N−1)/N × … × (N−k+1)/N. Die Näherung ist nur eine Abschätzung. 2n/2 beschreibt die Größenordnung, ab der Collisions wahrscheinlich werden – keine exakte 50-%-Grenze.
Merke: Entscheidend ist nicht die Zahl der Hashwerte, sondern die Zahl der Paare. Sie wächst quadratisch – deshalb reichen schon etwa √N Versuche für eine realistische Chance auf eine Hash Collision.
Was zeigt das Experiment?
Die Kollisionswahrscheinlichkeit wächst überraschend schnell. Entscheidend ist nicht die Zahl der Werte, sondern die Zahl der möglichen Paare – und die wächst ungefähr quadratisch mit der Anzahl der Versuche.
Beim bekannten Geburtstagsbeispiel mit 23 Personen und 365 gleich wahrscheinlichen Geburtstagen liegt die Wahrscheinlichkeit, dass mindestens zwei Personen am selben Tag Geburtstag haben, bereits bei ungefähr 50,7 Prozent.
Wechselst du zu einem Hashraum mit n Bit, zeigt sich derselbe Effekt: Schon nach ungefähr 2^(n/2) Hashwerten wird eine Collision realistisch – weit vor 2^n.
Mehr über das Birthday Paradox
Die Herleitung und den Zusammenhang mit Hashfunktionen erkläre ich im Artikel Das Birthday Paradox. Warum dieser Effekt die Kollisionssicherheit eines Hashes begrenzt, beschreibt Was ist Collision Resistance?.
Wie eine Collision in einem verkleinerten Hashraum tatsächlich gefunden wird, kannst du mit dem Birthday Attack Simulator ausprobieren.