Nein, 3 Würfe reichen nicht aus. Der Berechnungsweg von
@heiko01 und mir entsprechen dem Vorgehen in KE2, S. 83 (Geburtstagsparadoxon), und EA2, Aufgabe 5a. Allerdings haben wir einen Fehler gemacht.
Es geht um schwache Kollisionsresistenz: Nachricht 1 ist gegeben, eine weitere Nachricht 2 wird gesucht, damit gilt: H(1) = H(2). Die Berechnung dafür ist:
((mögliche Ereignisse, dass Ereignis nicht positiv ist - positive Ereignisse)*/mögliche Ereignisse)^n <= gesuchte Wahrscheinlichkeit.
* 3 von 4 Ereignissen treffen nicht zu. Mit jeder Wiederholung sinkt die Wahrscheinlichkeit (p), dass die Ereignisse NICHT zutreffen.
1. Wurf: p = 3/4 (75%), dass h(M) != 2. | (1-p = 25% -> h(M) = 2)
2. Wurf: p = (3/4)^2 (56%), dass h(M) != 2. | (1-p = 44% -> h(M) = 2)
3. Wurf: p = (3/4)^3 (42%), dass h(M) != 2. | (1-p = 58% -> h(M) = 2)
4. Wurf: p = (3/4)^4 (32%), dass h(M) != 2. | (1-p = 68% -> h(M) = 2)
Die Wahrscheinlichkeit soll nun mind. 60 Prozent betragen, dass eine der 3 Nachrichten h(M) = 2 hat. D.h. die Wahrscheinlichkeit, dass h(M) keine 2 ist soll mind. 40% betragen (1-p).
Daher darf in der Gleichung:
(3/4)^n =< gesuchte p
nicht 38/64 (60%) als gesuchte p genommen werden, sondern 26/64 (40%).
(3/4)^n =< 26/64 -> log(26/64) / log(3/4) = 3,13 Würfe.
Ohne Taschenrechner könnte man das einfach prüfen - ganz ohne Log:
(3/4)^3 = 27/64 > 26/64.