Prof. Dr. Johannes Buchmann ist Professor für Informatik und Mathematik sowie Vizepräsident der TU Darmstadt. Prof. Dr. Alexander May ist Juniorprofessor, Dr. Ulrich Vollmer und Dipl.-Math. Erik Dahmen sind Mitarbeiter am Fachbereich Informatik – Kryptographie und Computeralgebra der TU Darmstadt.



Das Merkle-Signaturverfahren (MSS)
Die einfachste Variante des Merkle-Signaturverfahrens benötigt lediglich einen Zufasllszahlengenerator und eine kryptographische Hash-Funktion H:{0,1}* → {0,1}s, die aus beliebig langen Dokumenten Strings einer festen Länge s macht. Das Merkle-Verfahren verwendet hierbei ein Einmal-Signatursystem (One-Time Signature Scheme, OTSS), das im Folgenden zunächst kurz erläutert werden soll.

Für eine OTSS-Signatur werden 2s (Erinnerung: s ist die Länge der Hash-Werte) Zufallszahlen x1(0),x1(1),x2(0),x2(1),…,xs(0),xs(1) erzeugt. Die Folge dieser Zahlen ist der geheime Signaturschlüssel X des OTSS. Daraus werden die Hash-Werte yi( j )=H(xi(j)), mit i = 1,…,s und j = 0,1 berechnet. Die Folge dieser Werte ist der Verifikationsschlüssel Y.

Da es sich um eine kryptographische Hash-Funktion handelt, kann niemand aus den Zahlen im Verifikationsschlüssel die Zahlen im Signaturschlüssel errechnen. Aber umgekehrt ist das für jeden möglich: Die Signatur des Hash-Werts (h1,…,hs) eines Dokuments ist die Folge (b1,…,bs) = (x1(h1),…,xs(hs)). Diese Signatur wird verifiziert, indem man den Hash-Wert des Dokuments berechnet und die Signatur akzeptiert, wenn die Folge (H(b1),…,H(bs)) mit (y1(h1),…,ys(hs)) übereinstimmt. Der Signaturschlüssel kann kein zweites Mal verwendet werden, weil er in der Signatur ja schon zur Hälfte preisgegeben wurde.

Bei der Schlüsselerzeugung für MSS wählt man eine positive Zahl h (z. B. h = 3) und entscheidet damit, dass 2h Signaturen mit dem erzeugten öffentlichen Schlüssel verifizierbar sein sollen. Dann werden 2h OTSS-Schlüsselpaare (Xi,Yi), i = 1,…,2h erzeugt (Erinnerung: Xi sind Signaturschlüssel, Yi Verifikationsschlüssel). Der geheime MSS-Schlüssel ist nun die Folge aller dieser OTSS-Signaturschlüssel.

[Vorherige]  1 2 3 4 5 6 7 8  [Nächste]