md5-Algorithmus < Algorithmen < Schule < Informatik < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich werde am Mittwoch ein Referat über Hash-Funktionen halten. Ein Teil der Presentation werde ich md5 widmen und da darf natürlich auch ein Umriss des Algorithmus nicht fehlen. Natürlich habe ich schon Wikipedia studiert und auch Google hat nach stundenlanger Suche nichts richtiges ergeben.
Mir ist klar, dass der Eingabestring erst verlängert werden muss. Aber da hörts dann schon auf. Ich weiß nicht, was es mit A, B, C, D und F, G, H, I auf sich hat. Kann mir das jemand näher bringen?
mfG, Sven
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:17 Mo 03.12.2007 | | Autor: | Bastiane |
Hallo schwerminator!
> ich werde am Mittwoch ein Referat über Hash-Funktionen
> halten. Ein Teil der Presentation werde ich md5 widmen und
> da darf natürlich auch ein Umriss des Algorithmus nicht
> fehlen. Natürlich habe ich schon Wikipedia studiert und
> auch Google hat nach stundenlanger Suche nichts richtiges
> ergeben.
> Mir ist klar, dass der Eingabestring erst verlängert
> werden muss. Aber da hörts dann schon auf. Ich weiß nicht,
> was es mit A, B, C, D und F, G, H, I auf sich hat. Kann mir
> das jemand näher bringen?
Habe noch nie davon gehört und nur mal kurz bei Wikipedia reingeschaut, aber ich glaube das Problem mit den Buchstaben kann ich dir erklären. Und zwar sieht es auf der Zeichnung so aus, als kämen B,C und D als Input für die Funktion F, die dort die Variablen X,Y,Z hat (also für X steht dann jetzt B usw.). Was genau das rote Kästchen und [mm] M_i [/mm] und [mm] K_i [/mm] machen, weiß ich nicht, aber wahrscheinlich wird da irgendwie das A noch mit hinzugenommen und noch was verändert. Und dann wird unten die Reihenfolge der A,B,C,D verändert - jetzt kommt nämlich das D nach vorne und alle anderen rutschen eins weiter nach hinten. Und dann geht das Ganze wahrscheinlich wieder von vorne los.
Aber findet man da beim Googeln wirklich nichts anderes Hilfreiches? Hab' leider keine Zeit, sonst würde ich auch mal nachschaun. 
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:06 Di 04.12.2007 | | Autor: | rainerS |
Hallo Sven!
> ich werde am Mittwoch ein Referat über Hash-Funktionen
> halten. Ein Teil der Presentation werde ich md5 widmen und
> da darf natürlich auch ein Umriss des Algorithmus nicht
> fehlen. Natürlich habe ich schon Wikipedia studiert und
> auch Google hat nach stundenlanger Suche nichts richtiges
> ergeben.
> Mir ist klar, dass der Eingabestring erst verlängert
> werden muss. Aber da hörts dann schon auf. Ich weiß nicht,
> was es mit A, B, C, D und F, G, H, I auf sich hat. Kann mir
> das jemand näher bringen?
Die A,B,C,D sind ganz einfach zu verstehen: das sind Speicher für Zwischenergebnisse (jeder davon 32Bit groß). Am Anfang werden dieser vier Speicherzellen mit festen Bitmustern vorbelegt. Am Schluss werden ABCD zu einem 128Bit langen Ergebnis zusammengesetzt.
MD5 ist eine sogenannte iterative Hashfunktion: da wird der Eingabestring in lauter gleich lange Blöcke von je 512 Bit Länge zerhackt, und dieser Blöcke einzeln verarbeitet, indem das Zwischenergebnis der bisherigen Verarbeitung mit dem aktuellen Block verknüpft wird. Es wird dazu jeweils ein Block (512 Bit) hergenommen, mit dem Werten A,B,C,D im Zwischenspeicher verknüpft, und das Ergebnis wieder in A,B,C,D abgelegt.
Jeder dieser Verarbeitungsschritte besteht aus 4 Teilen (den sogenannten Runden). In jeder der 4 Runden wird eine bestimmte logische Operation verwendet. Die in der 1. Runde wird mit F, die in der 2. Runde mit G, in der 3. mit H und in der 4. mit I bezeichnet.
Zusätzlich wird nach jeder Runde die Reihenfolge der ABCD um eins verschoben, also ABCD -> BCDA -> CDAB -> DABC.
Jede Runde besteht wiederum aus 16 gleichen Einzelschritten. Das ![[]](/images/popup.gif) Bild aus der Wikipedia stellt einen solchen Einzelschritt dar.
Der Block von 512 Bit wird nämlich in 16 Teile von je 32 Bit zerlegt. [mm]M_i[/mm] bezeichnet in dem Bild den aktuell verarbeiteten, 32 Bit langen Teilblock. [mm]K_i[/mm] bedeutet bestimmte, im Algorithmus vorgegebene konstante Bitmuster. Der grüne Kasten mit dem F bezeichnet die eben genannte Operation, die in jeder der 4 Runden eine andere ist.
Viele Grüße
Rainer
|
|
|
| |
|
Hallo,
vielen Dank für deine Antwort, das hat schon einiges geklärt. Was ich noch nicht so ganz vesrtanden habe, ist folgendes:
Wie habe ich das mit den Runden zu verstehen, läuft das alles in der gleichen Konstellation viermal durch? Dann geht md5 zum nächsten 512-Bit-Segment und das gleiche nochmal?
Der zur Zeit verarbeitete Block ist ja 512 Bit groß, dieser wird in 16 Teile geteilt, damit md5 mit seinen 32-Bit-Arbeitsspeichern damit umgehen kann. Das ist klar. Aber wenn ich 16 Blöcke habe, aber nur 4 Runden, habe ich eine Differenz. Wie verhält sich das genau?
Sind diese roten Quadrate mit dem Kreuz binäre Additionen?
Weißt du zufällig, wie Ki aussieht?
mfG, Sven
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:55 Di 04.12.2007 | | Autor: | rainerS |
Hallo Sven!
> Hallo,
> vielen Dank für deine Antwort, das hat schon einiges
> geklärt. Was ich noch nicht so ganz vesrtanden habe, ist
> folgendes:
>
> Wie habe ich das mit den Runden zu verstehen, läuft das
> alles in der gleichen Konstellation viermal durch? Dann
> geht md5 zum nächsten 512-Bit-Segment und das gleiche
> nochmal?
Nein. Für jeden 512 Bit langen Block gibt es 4 Runden. Die Runden unterscheiden sich nur durch die nichtlineare Funktion.
> Der zur Zeit verarbeitete Block ist ja 512 Bit groß, dieser
> wird in 16 Teile geteilt, damit md5 mit seinen
> 32-Bit-Arbeitsspeichern damit umgehen kann. Das ist klar.
> Aber wenn ich 16 Blöcke habe, aber nur 4 Runden, habe ich
> eine Differenz. Wie verhält sich das genau?
Jede der 4 Runden besteht aus 16 Durchläufen. In jedem Durchlauf wird einer der 16 32Bit langen Teilblöcke verarbeitet. Die Reihenfolge der 16 Blöcke ist in jeder Runde eine andere.
> Sind diese roten Quadrate mit dem Kreuz binäre Additionen?
Ja.
> Weißt du zufällig, wie Ki aussieht?
In jedem Durchlauf jeder Runde verschieden, das heisst, es sind insgesamt 64 verschiedene 32 Bit Werte, die mit der Sinusfunktion berechnet werden, über die Formel
[mm] 2^{32} * |\sin(i)| [/mm], [mm]i=1,\dots,64[/mm]
und Abschneiden der Nachkommastellen. Diese Zahlen stehen auch in der Spezifikation, man muss sie nicht selbst ausrechnen.
Die Referenz ist der RFC 1321; hier findest du Links auf MD5 in zahlreichen Programmiersprachen.
Viele Grüße
Rainer
|
|
|
| |
|
Danke, Danke, Danke! Alle Fragen geklärt!
mfG, Sven
|
|
|
|
![[]](http://upload.wikimedia.org/wikipedia/commons/a/ab/MD5.png){kind=small}
Bild aus der Wikipedia