imported>Birkho am 11. November 2024 um 12:43 Uhr

2024-11-11T12:43:06Z

Neue Seite

Die '''Merkle-Signatur''' ist ein [[Digitale Signatur|digitales Signaturverfahren]], das auf [[Hash-Baum|Merkle-Bäumen]] sowie Einmalsignaturen wie etwa den [[Lamport-Einmal-Signaturverfahren|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-Kryptosystem|RSA]] basierenden Signaturen dar. Im Gegensatz zu diesen ist es resistent gegen Angriffe durch [[Quantencomputer]], da seine Sicherheit nur von der Existenz sicherer [[Hashfunktion]]en abhängt.

== Idee ==
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 <math>2^n</math> Einmalsignaturen in einem mehrstufigen Hash-Verfahren zu einem einzigen Hashwert <math>pub</math> zusammengefasst wird. Als öffentlicher Schlüssel braucht nur <math>pub</math> veröffentlicht zu werden, anschließend lassen sich mit ihm <math>2^n</math> Nachrichten signieren.

Die Signatur einer Nachricht besteht dann aus zwei Teilen:

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

== Schlüsselerzeugung ==
[[Datei:MerkleTree1.svg|mini|Merkle-Baum mit 8 Blättern]]

Das Merkle-Signaturverfahren kann nur verwendet werden, um eine begrenzte Anzahl von Nachrichten mit einem öffentlichen Schlüssel <math>pub</math> zu signieren. Die Anzahl möglicher Nachrichten entspricht einer Zweierpotenz und wird daher als <math>N=2^n</math> bezeichnet.

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

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

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

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

== Signierung ==
[[Datei:MerkleTree2.svg|mini|Merkle-Baum mit Pfad A und Authentifizierungspfad für i=2]]

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

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

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

== Weiterentwicklungen ==
Im Zuge der Suche nach [[Post-Quanten-Kryptographie|quantencomputerresistenten]] Signaturverfahren ist das Verfahren in der letzten Zeit wieder stärker in den Fokus gerückt. Inzwischen wurden verbesserte Varianten des Merkle-Signaturverfahrens veröffentlicht, u. a.
* '''XMSS''' (eXtended Merkle Signature [[Scheme]]), das 2018 als <nowiki>RFC 8391</nowiki><ref>{{RFC-Internet |RFC=8391 |Titel=XMSS: eXtended Merkle Signature Scheme |Datum=2018-09}}</ref> standardisiert wurde<ref>{{Literatur |Autor=Johannes Buchmann, Erik Dahmen, Andreas Hülsing |Titel=XMSS – A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions |Sammelwerk=Post-Quantum Cryptography. PQCrypto 2011 |Reihe=Lecture Notes in Computer Science |BandReihe=7071 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=2011 |Seiten=117–129 |DOI=10.1007/978-3-642-25405-5_8}}</ref>
* '''LMS''' (Leighton-Micali Hash-Based Signatures), das 2019 als <nowiki>RFC 8554</nowiki> standardisiert wurde<ref name="RFC8554" />
* '''SPHINCS''' mit größeren Signaturen als XMSS, dafür aber zustandslos<ref>{{Literatur |Autor=Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, Zooko Wilcox-O’Hearn |Hrsg=Elisabeth Oswald, Marc Fischlin |Titel=SPHINCS: practical stateless hash-based signatures |Sammelwerk=Advances in Cryptology – EUROCRYPT 2015 |Reihe=Lecture Notes in Computer Science |BandReihe=9056 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=2015 |ISBN=978-3-662-46799-2 |Seiten=368-397 |DOI=10.1007/978-3-662-46800-5_15}}</ref><ref>{{Internetquelle |url=https://sphincs.cr.yp.to/ |titel=SPHINCS: Introduction |werk=sphincs.cr.yp.to |sprache=en |abruf=2019-01-25}}</ref>

== Literatur ==
* G. Becker: ''Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis''. Seminar 'Post Quantum Cryptology' an der [[Ruhr-Universität Bochum]].
* E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, L. C. Coronado Garca: [http://www.cdc.informatik.tu-darmstadt.de/reports/reports/BCDDK06.pdf ''CMSS – an improved merkle signature scheme''.] (PDF; 264 kB). Progress in Cryptology – Indocrypt 2006, 2006.
* E. Klintsevich, K. Okeya, C. Vuillaume, J. Buchmann, E. Dahmen: [http://www.cdc.informatik.tu-darmstadt.de/reports/reports/BDKOV07.pdf ''Merkle signatures with virtually unlimited signature capacity''] (PDF; 179 kB). 5th International Conference on Applied Cryptography and Network Security – ACNS07, 2007.
* Ralph Merkle: ''Secrecy, authentication and public key systems / A certified digital signature''. Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979; [http://www.merkle.com/papers/Thesis1979.pdf merkle.com] (PDF; 1,9 MB)
* [[Silvio Micali]], M. Jakobsson, T. Leighton, M. Szydlo: ''Fractal merkle tree representation and traversal''. RSA-CT 03, 2003.

== Einzelnachweise ==
<references>
<ref name="RFC8554">
{{RFC-Internet |RFC=8554 |Titel=Leighton-Micali Hash-Based Signatures |Datum=2019-04 |Autor=D. McGrew, M. Curcio, S. Fluhrer}}
</ref>
</references>

[[Kategorie:Signaturverfahren]]

Merkle-Signatur - Versionsgeschichte

imported>Birkho am 11. November 2024 um 12:43 Uhr