Um den öffentlichen MSS-Schlüssel zu bestimmen, wird ein binärer Authentifizierungsbaum wie folgt konstruiert: Jeder Verifikationsschlüssel Yi wird als Bit-String geschrieben. Die Blätter des Authentifizierungsbaums sind die Hash-Werte H(Yi) der Verifikationsschlüssel. Jeder innere Knoten des Baums (einschließlich Wurzel) ist der Hash-Wert der Konkatenation seiner beiden Kinder (Abb. 1). Der öffentliche MSS-Schlüssel ist die Wurzel des Authentifizierungsbaums (Erinnerung: Rückrechnen "nach unten" ist nicht möglich).

Beim Signieren werden die OTSS-Schlüssel nacheinander benutzt. Die Signatur eines Dokuments d, die unter Verwendung des i-ten Schlüsselpaars (Xi,Yi) erzeugt wurde, ist ein Tupel (Abb. 2), dessen erste drei Elemente der Index i, der i-te Verifikationsschlüssel Yi und die OTSS-Signatur von d sind, die mit dem i-ten Signaturschlüssel Xi erstellt wird. Weiterhin enthält die MSS-Signatur noch die Folge der Geschwister aller Knoten auf dem Pfad vom i-ten Blatt des Authentifizierungsbaums zur Wurzel, den so genannten Authentifizierungspfad für Yi.

Um diese Signatur zu verifizieren, wird zuerst die Einmalsignatur mit dem Verifikationsschlüssel Yi überprüft. Danach wird dieser Verifikationsschlüssel selbst überprüft, indem mithilfe des Authentifizierungspfads der Pfad vom i-ten Blatt H(Yi) zur Wurzel konstruiert wird (Abb. 3). Ist der letzte Knoten in diesem Pfad gleich dem öffentlichen MSS-Schlüssel, so ist die Signatur gültig.

Modifikation von MSS
In seiner ursprünglichen Form ist das Merkle-Verfahren sehr ineffizient: Der geheime Schlüssel ist zu groß und die Schlüsselerzeugung dauert zu lang. In der Arbeitsgruppe von Prof. Johannes Buchmann an der TU Darmstadt wurde eine MSS-Variante entwickelt, welche die Zeit für die Schlüsselerzeugung und die Größe des geheimen MSS-Schlüssels drastisch reduziert; die Autoren nennen diese Variante CMSS [1]. Das verbesserte Signaturverfahren hat überzeugende Timings und kann mit RSA, DSA und ECDSA durchaus konkurrieren. Tabelle 1 zeigt die Zeiten für Schlüsselerzeugung, Signieren und Verifizieren sowie die Größe der Schlüssel und der Signaturen auf einem Pentium M 1,73 GHz (1 GB RAM, Windows XP).

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