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 Siebzigern 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]

Ein Problem von Einmalsignaturen, wie der Lamport-Signatur, ist die Übertragung des öffentlichen Schlüssels. Da jeder Schlüssel nur genau ein mal 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 2^n Einmalsignaturen in einem mehrstufigen Hash-Verfahren zu einem einzigen Hashwert pub zusammengefasst wird. Als öffentlicher Schlüssel muss nur pub veröffentlicht werden, anschließend lassen sich mit ihm 2^n Nachrichten signieren.

Die Signatur einer Nachricht besteht dann aus zwei Teilen:

  • Einem der 2^n ö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 2^n Schlüssel handelt, aus denen der Hashwert pub berechnet wurde.

Schlüsselerzeugung[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 pub zu signieren. Die Anzahl möglicher Nachrichten entspricht einer Zweierpotenz und wird daher als N=2^n bezeichnet.

Der erste Schritt bei der Generierung des öffentlichen Schlüssels pub ist die Generierung des öffentlichen Schlüssels X_i und des privaten Schlüssels Y_i von 2^n Einmalsignaturen. Für jeden privaten Schlüssel Y_i mit 1 \leq i \leq 2^n wird ein Hash-Wert h_i=H(Y_i) berechnet. Mit diesen Hash-Werten h_i wird ein Hash-Baum aufgebaut.

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

Im Merkle-Baum sind die Hash-Werte h_i die Blätter des Binärbaums, sodass h_i=a_{0,i}. Jeder innere Knoten des Baums ist der Hash-Wert der Konkatenation seiner beiden Kinder. Beispielsweise ist a_{1,0}=H(a_{0,0}||a_{0,1}) und a_{2,0}=H(a_{1,0}||a_{1,1}).

Auf diese Weise wird ein Baum mit 2^n Blättern und 2^{n+1}-1 Knoten aufgebaut. Die Wurzel des Baums a_{n,0} ist der öffentliche Schlüssel pub des Merkle-Signaturverfahrens.

Signierung[Bearbeiten]

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

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

Das einem öffentlichen Einmalschlüssel X_i zugehörige Blatt des Hash-Baums ist a_{0,i}=H(Y_i). Der Pfad im Hash-Baum von a_{0,i} zur Wurzel wird mit A bezeichnet. Der Pfad A besteht aus n+1 Knoten, A_0, \ldots, A_n, wobei A_0=a_{0,i} die Blätter sind und A_n=a_{n,0}=pub die Wurzel des Baums ist. Um diesen Pfad A zu berechnen wird jedes Kind der Knoten A_{1}, \ldots, A_{n} benötigt. Es ist bekannt, dass A_i ein Kind von A_{i+1} ist. Um den nächsten Knoten A_{i+1} des Pfades A zu berechnen, müssen beide Kinder von A_{i+1} bekannt sein. Daher wird der Bruder von A_i benötigt. Dieser Knoten wird mit auth_i bezeichnet, sodass A_{i+1}=H(A_i||auth_i). Deswegen werden n Knoten auth_0,\ldots,auth_{n-1} benötigt, um jeden Knoten des Pfades A zu berechnen. Diese Knoten auth_{0},\ldots, auth_{n-1} werden berechnet und gespeichert. Sie bilden zusammen mit einer Einmalsignatur sig' von M die Signatur sig=(sig', auth_0, auth_1,\ldots, auth_{n-1}) des Merkle-Signaturverfahrens.

Verifizierung[Bearbeiten]

Der Empfänger kennt den öffentlichen Schlüssel pub, die Nachricht M, und die Signatur sig=(sig', auth_0, auth_1, \ldots, auth_{n-1}). Zuerst verifiziert der Empfänger die Einmalsignatur sig' der Nachricht M. Falls sig' eine gültige Signatur von M ist, berechnet der Empfänger A_0=H(Y_i), indem er den Hash-Wert des privaten Schlüssels der Einmalsignatur berechnet. Für j=1,..,n-1 werden die Knoten A_j des Pfades A berechnet, mit A_j=H(a_{j-1}||b_{j-1}). Wenn A_n dem öffentlichen Schlüssel pub des Merkle-Signaturverfahrens entspricht, so ist die Signatur gültig.

Quellen[Bearbeiten]

Weblinks[Bearbeiten]

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