spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hey, ich stehe gerade vor einem kleinen Problem. Ich bereite mich gerade auf die Klausur in Kryptographie vor und komme bei
folgender Aufgabe nicht so recht weiter:


Betrachten Sie eine Hashfunktion h mit einer Ausgabelänge von 16 Bit sowie eine bestimmte Nachricht
M mit Hashwert h(M). Ein Angreifer versucht nun, eine Nachricht M' mit dem selben Hashwert
h(M') = h(M) zu finden, indem er wiederholt den Hashwert einer zufälligen Nachricht berechnet.
Wieviele Runden muss er ausführen, um auf eine Erfolgswahrscheinlichkeit von mindestens 50% zu kommen?

Mein Ansatz war nun:
§ \frac {1}{2^{16}} + \frac {1 - \frac {1}{2^{16}}}{2^{16} - 1} + \frac {(1 - \frac {1}{2^{16}}) * (1 - \frac {1}{2^{16} - 1})}{2^{16} - 2} \dots = 0.5 §

Idee dahinter: Wenn der Hash kollisionsfrei ist, muss man §2^{16}§ Nachrichten ausprobieren. Die Wahrscheinlichkeit, dass
die erste Nachricht direkt den Hash generiert ist
§\frac {1}{2^{16}}§
für die zweite Nachricht ist die Wahrscheinlichkeit also §\frac {1 - \frac {1}{2^{16}}}{2^{16} - 1}§ usw. die
Gesamtwahrscheinlichkeit muss dann 0,5 betragen.


Meine Frage wäre: Wie kann man das kombinatorisch in eine Sinnvolle Formel bringen und nach n umformen und
ist meine Überlegung soweit überhaupt korrekt?

PS: Sorry, dass das Erstellen so lange gedauert hat, musste mir noch Latex angucken xD

Zitat

Die Annahme, dass die Hashfunktion kollisionsfrei ist, ist
unsinnig, denn sowas gibt es erstens gar nicht, und zweitens geht es
in der Aufgabe ja gerade darum, eine Kollision zu finden.

Das ist wahr, das "Kollisionsfrei" hab ich aus der letzten Teilaufgabe übernommen. Aber, wenn es nicht kollisionsfrei wäre, würde das ja theoretisch bedeuten, dass man einfach nicht
wissen kann, wie viele Nachrichten man erzeugen muss um auf den gleichen Hashwert zu kommen.

Zitat

Einfach mal Aufgabe lesen: "Hashwert einer zufälligen Nachricht". Es
reicht also nicht aus 2^16 Nachrichten auszuprobieren, es koennte auch
zufaellig 2^16 mal die gleiche Nachricht sein.

Das würde ich so nicht sagen, ich denke das man schon davon ausgehen kann, dass der Angreifer nicht so dumm ist ständig die gleiche Nachricht auszuprobieren, auch wenn da "zufällig" steht.

Deswegen habe ich "Ziehen ohne Zurücklegen" angenommen.