Merkles Meta-Verfahren

Merkles Meta-Verfahren (auch Merkle-Damgård-Konstruktion) 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 von Merkles Meta-Verfahren 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.