Merkle-Damgård-Konstruktion

Die Merkle-Damgård-Konstruktion (auch Merkles Meta-Verfahren) ist eine Methode zur Konstruktion von kryptographischen Hash-Funktionen, die auf Arbeiten von Ralph Merkle und Ivan Damgård zurückgeht.

Gegeben ist eine Kompressionsfunktion ${\displaystyle f\colon \{0,1\}^{a+b}\rightarrow \{0,1\}^{b}}$, die eine ${\displaystyle a+b}$ Bit lange Eingabe auf eine ${\displaystyle b}$ Bit lange Ausgabe abbildet. Sie ist kollisionssicher, das heißt, es ist nicht mit realistischem Aufwand möglich, zwei verschiedene Eingaben zu finden, die auf die gleiche Ausgabe abgebildet werden. Durch die Anwendung der Merkle-Damgård-Konstruktion ergibt sich daraus eine kollisionssichere Hash-Funktion ${\displaystyle h\colon \{0,1\}^{*}\rightarrow \{0,1\}^{b}}$, die beliebig lange Nachrichten auf einen Hashwert von ${\displaystyle b}$ Bit abbildet.