10. Übungsblatt

[erik.tews]

Ist online

[bruse]

Servus. Bei der Aufgabe 2 des 10. Blattes war ja eine Kollision der Hashfunktion gefragt. Es ist auch eine angegeben, allerdings ohne Lösungsweg. Wie kommt man denn auf diese Kollision?

[Tristan]

Das würde ich auch gerne mal wissen.

[erik.tews]

Nein, ist ja noch nen Monat.

Vermutlich verschieben wir Krypto um 30 Minuten für die EiSE schreiber, so dass genug Zeit für beide Klausuren bleibt. Für ein ausgiebiges Mittagessen mit anschließender Ganzkörpermassage zur Entspannung zwischen den beiden Klausuren wird aber vermutlich keine Zeit mehr bleiben.

[bruse]

Erstmal danke für die Info. Das war aber sicher die Antwort auf die Frage aus einem anderen Thread, oder?

[Hyst]

hatte da jemand zu viele tabs/fenster offen?

[Tristan]

Wie sieht es mit einer Antwort zu der eigentlichen Frage aus?

[erik.tews]

Hallo

Wir basteln noch an einer Lösung.

[bruse]

Irgendwoher muss die auf dem Lösungsblatt angegebene Kollision ja gekommen sein. Mich interessiert eigentlich nur der Ansatz, wie man darauf kommt. Die Kollision ist ja nicht so, dass man sie sofort erkennt, und Durchprobieren von 10.000 Werten kann ja kaum verlangt worden sein. Da Sie eine solche Kollision auf dem Blatt angegeben haben, müssen Sie ja einen solchen Ansatz (bezogen auf dieses spezifische Problem) kennen. Den hätt' ich gern gewusst, am liebsten noch vor der Klausur.

[taufrisch]

\(\frac{1+\sqrt 5} 2\)ist der goldene Schnitt \(\varphi\), und für die Fibonaccizahlen \(F_n\) gilt \(lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi\), d.h. wenn du \(n\) groß genug wählst gilt \(F_{n+1}\approx\varphi F_n\).

Damit ist \(\varphi F_n\) bis auf einen kleinen, von \(n\) abhängigen Fehler eine ganze Zahl (und ein kleines \(\epsilon\ mod\ 1\) das du nur noch hinter die vierte Stelle nach den Komma drücken mußt). Bei \(F_{20}=6765\) bekommst du die erste Kollision mit \(h(2)=2360=h(2+6765)\).

Die Musterlösung nimmt \(F_{21}=10946\) und \(h(1)=6180=h(1+F_{21})\), alle Fibonaccizahlen über der zwanzigsten funktionieren.

[\Hannes]

Wicked

[bruse]

Cool, danke.

[The One and Only Markus]

Hi,

mal 2 kleine Anmerkungen zur G1:

1. In der Aufgabe wird nach der Anzahl der Kollisionen gefragt, in der Lösung stehen aber die Anzahl verschiedener Ausgaben. Das hat doch aber erstmal garnichts mit der Lösung zu tun. Beispiel für die Permutation (1,3,2): Da ist als Anzahl verschiedener Ausgaben 2 angegeben, die Anzahl an Kollisionen beträgt doch eigentlich 24, da eine Kollision im Buch als Paar von 2 ungleichen Strings definiert ist, für die h(x) gleich ist. Wobei ich diese Definition für etwas merkwürdig halte, da in dem genannten Beispiel ja z.B. (000, 011) und (011, 000) schon als 2 Kollisionen zählen würde. Ist dass denn so sinnvoll?

2. Die Funktion in der Aufgabe ist überhaupt keine Kompressionsfkn. da die Länge von x gleich der Länge von h(x) ist.

[erik.tews]

zu 1.: Wir haben nicht wirklich erklärt wie wir Kollisionen zählen, wenn z. B. die Funktion für 3 Eingabewerte die gleiche Ausgabe liefert. Also sind das dann 2 oder 3 Kollisionen. Um die Lösung klarer formulieren zu können, stehen nur die Anzahl der unterschiedlichen Ausgaben da.

zu 2.: Eigentlich hast du recht.

[AhGuGu]

Hallo,

zu 1.: Wir haben nicht wirklich erklärt wie wir Kollisionen zählen, wenn z. B. die Funktion für 3 Eingabewerte die gleiche Ausgabe liefert. Also sind das dann 2 oder 3 Kollisionen. Um die Lösung klarer formulieren zu können, stehen nur die Anzahl der unterschiedlichen Ausgaben da.

Vor dem Problem stand ich auch. Wie würde sowas inder Klausur ausschauen? Eine Bearbeitung analog zur Musterlösung würde ja wohl kaum zur gewünschten Maximalpunktzahl führen. Mein Vorschlag wäre, in der Aufgabe die Zählweise zu definieren.

zu 2.: Eigentlich hast du recht.

Unsere Tutorin versuchte uns das so zu erklären: Die Permutation gehört als Parameter dazu, sprich die Funktion sollte wohl h(pi, x) lauten. Damit würde es sich doch dann um eine Kompressionsfunktion (wenn auch in etwas anderer Notation) handeln, oder?

gruß Ahgugu