On Sunday 02 November 2003 00:03, Ulf Lorenz wrote:
Genau, wenn wir gleiche Chancen fuer alle md5-Summen annehmen, passiert das aller etwa 2^128 Dateien einmal... MD5 war doch 128 Bits, oder?
Richtig: MD5 hat 128 Bit.
Falsch: "alle 2^128 Dateien" -> die Kollissionswahrscheinlichkeit ist 2^64. Sprich unter 2^64+1 Dateien sind statistisch zwei mit identischem MD5. Die Kollissionswahrscheinlichkeit ist immer die Quadratwurzel der Anzahl der moeglichen Werte.
Im Gegensatz zu: eine in 2^128 verschiedenen Dateien wird den selben MD5 haben wie diese eMail.
Gemeinerweise ist die Kollissionswahrscheinlichkeit die kritische Groesse bei der Beurteilung von Hashes...
Kleines Beispiel zum Ausprobieren: nimm 16 (2^4) Skatkarten. Mische sie.
Uebung 1: versuche eine spezielle Karte zu ziehen (sagen wir Pik Bube), Du wirst durchschnittlich 16 Versuche brauchen, um diese Karte zu ziehen (Achtung: nach dem Ziehen die Karte zurueckmischen).
Uebung 2: ziehe nacheinander Karten (mit zuruecklegen!!) und schreibe die Werte auf. Stoppe sobald Du eine gezogen hast, die Du in dieser Serie schonmal hattest. Du solltest darauf kommen, dass Du durchschnittlich 4 Karten ziehst, bevor Du ein Duplikat hast.
Sprich: Wahrscheinlichkeit jedes einzelnen Wertes = 2^4, Kollisionswahrscheinlichkeit = 2^2.
Konrad