Merkle-Signatur

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Merkle-Signatur ist ein digitales Signaturverfahren, das auf Merkle-Bäumen sowie Einmalsignaturen wie etwa den Lamport-Einmalsignaturen basiert. Es wurde von Ralph Merkle in den späten 1970er Jahren entwickelt und stellt eine Alternative zu traditionellen digitalen Signaturen wie dem Digital Signature Algorithm oder auf RSA basierenden Signaturen dar. Im Gegensatz zu diesen ist es resistent gegen Angriffe durch Quantencomputer, da seine Sicherheit nur von der Existenz sicherer Hashfunktionen abhängt.

Idee[Bearbeiten | Quelltext bearbeiten]

Ein Problem von Einmalsignaturen, wie der Lamport-Signatur, ist die Übertragung des öffentlichen Schlüssels. Da jeder Schlüssel nur genau einmal verwendet werden kann, kommt eine größere Datenmenge zusammen, die zuverlässig an den Empfänger weitergegeben werden muss.

Das Merkle-Signaturverfahren löst dieses Problem, indem das gesamte (öffentliche) Schlüsselmaterial von Einmalsignaturen in einem mehrstufigen Hash-Verfahren zu einem einzigen Hashwert zusammengefasst wird. Als öffentlicher Schlüssel braucht nur veröffentlicht zu werden, anschließend lassen sich mit ihm Nachrichten signieren.

Die Signatur einer Nachricht besteht dann aus zwei Teilen:

  • Einem der öffentlichen Schlüssel, sowie die mit dem entsprechenden privaten Schlüssel signierte Nachricht. Der Empfänger kann verifizieren, dass der Sender tatsächlich in Besitz des privaten Schlüssels war.
  • Einem Nachweis, dass es sich bei dem öffentlichen Schlüssel um einen der Schlüssel handelt, aus denen der Hashwert berechnet wurde.

Schlüsselerzeugung[Bearbeiten | Quelltext bearbeiten]

Merkle-Baum mit 8 Blättern

Das Merkle-Signaturverfahren kann nur verwendet werden, um eine begrenzte Anzahl von Nachrichten mit einem öffentlichen Schlüssel zu signieren. Die Anzahl möglicher Nachrichten entspricht einer Zweierpotenz und wird daher als bezeichnet.

Der erste Schritt bei der Generierung des öffentlichen Schlüssels ist die Generierung des öffentlichen Schlüssels und des privaten Schlüssels von Einmalsignaturen. Für jeden privaten Schlüssel mit wird ein Hash-Wert berechnet. Mit diesen Hash-Werten wird ein Hash-Baum aufgebaut.

Ein Knoten des Baums wird mit identifiziert, wobei die Ebene des Knotens bezeichnet. Die Ebene eines Knotens ist über seinen Abstand zu den Blättern definiert. Somit hat ein Blatt die Ebene und die Wurzel die Ebene . Die Knoten jeder Ebene sind von links nach rechts durchnummeriert, sodass der Knoten ganz links auf Ebene ist.

Im Merkle-Baum sind die Hash-Werte die Blätter des Binärbaums, sodass . Jeder innere Knoten des Baums ist der Hash-Wert der Konkatenation seiner beiden Kinder. Beispielsweise ist und .

Auf diese Weise wird ein Baum mit Blättern und Knoten aufgebaut. Die Wurzel des Baums ist der öffentliche Schlüssel des Merkle-Signaturverfahrens.

Signierung[Bearbeiten | Quelltext bearbeiten]

Merkle-Baum mit Pfad A und Authentifizierungspfad für i=2

Um eine Nachricht mit dem Merkle-Signaturverfahren zu signieren, wird die Nachricht zuerst mit einem Einmalsignaturverfahren signiert, wodurch die Signatur entsteht. Dazu wird eines der Schlüsselpaare aus öffentlichem und privatem Schlüssel verwendet.

Das einem öffentlichen Einmalschlüssel zugehörige Blatt des Hash-Baums ist . Der Pfad im Hash-Baum von zur Wurzel wird mit bezeichnet. Der Pfad besteht aus Knoten, , wobei die Blätter sind und die Wurzel des Baums ist. Um diesen Pfad zu berechnen wird jedes Kind der Knoten benötigt. Es ist bekannt, dass ein Kind von ist. Um den nächsten Knoten des Pfades zu berechnen, müssen beide Kinder von bekannt sein. Daher wird der Bruder von benötigt. Dieser Knoten wird mit bezeichnet, sodass . Deswegen werden Knoten benötigt, um jeden Knoten des Pfades zu berechnen. Diese Knoten werden berechnet und gespeichert. Sie bilden zusammen mit einer Einmalsignatur von die Signatur des Merkle-Signaturverfahrens.

Verifizierung[Bearbeiten | Quelltext bearbeiten]

Der Empfänger kennt den öffentlichen Schlüssel , die Nachricht , und die Signatur . Zuerst verifiziert der Empfänger die Einmalsignatur der Nachricht . Falls eine gültige Signatur von ist, berechnet der Empfänger , indem er den Hash-Wert des privaten Schlüssels der Einmalsignatur berechnet. Für werden die Knoten des Pfades berechnet, mit . Wenn dem öffentlichen Schlüssel des Merkle-Signaturverfahrens entspricht, so ist die Signatur gültig.

Quellen[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

  • Efficient Use of Merkle Trees – Erklärung von RSA Security zum ursprünglichen Zwecks von Merkle-Trees: der Handhabung vieler Lamport-Einmalsignaturen.