Merkle-Signatur
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
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
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 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
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 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 RFC 8391<ref>Vorlage:RFC-Internet</ref> standardisiert wurde<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
- LMS (Leighton-Micali Hash-Based Signatures), das 2019 als RFC 8554 standardisiert wurde<ref name="RFC8554" />
- SPHINCS mit größeren Signaturen als XMSS, dafür aber zustandslos<ref>{{#invoke:Vorlage:Literatur|f}}</ref><ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:|{{#if:SPHINCS: Introduction|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=SPHINCS: Introduction}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://sphincs.cr.yp.to/%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=SPHINCS: Introduction}}}}|[{{#invoke:URLutil|getNormalized|1=https://sphincs.cr.yp.to/}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=SPHINCS: Introduction}}}}]}}{{#if:| ({{{format}}}{{#if:sphincs.cr.yp.to{{#if: 2019-01-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| )
| {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ;
| )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://sphincs.cr.yp.to/%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://sphincs.cr.yp.to/}}%7C%7C}}}}{{#if:SPHINCS: Introduction|{{#if:{{#invoke:WLink|isValidLinktext|1=SPHINCS: Introduction|lines=0}}||}}}}{{#if: sphincs.cr.yp.to| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=sphincs.cr.yp.to}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2019-01-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
|{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
|{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2019-01-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2019-01-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:2232105||(?)}}}}}}{{#if: 2019-01-25|;}}}}{{#if: 2019-01-25| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2019-01-25 |ISO|noerror=1}} }}
|4=im Jahr
|7=im
|10=am
|#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2019-01-25|class=Zitationswartung}} }} {{#invoke:DateTime|format|2019-01-25|T._Monat JJJJ}}
| {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:sphincs.cr.yp.to{{#if: 2019-01-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| (
| {{#if: | | (}}
}}{{#ifeq:{{#if:en|en|de}}|de||
{{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2019-01-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
#if:
| „{{
#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| Vorlage:Str trim
| {{#invoke:Vorlage:lang|flat}}
}}“
| {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| „Vorlage:Str trim“
| {{#invoke:Text|quote
|1={{#if:
| {{#invoke:Vorlage:lang|flat}}
| {{#invoke:Vorlage:lang|flat}} }}
|2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
|3=1}} }}
}}{{#if:
| (<templatestyles src="Person/styles.css" />{{#if: | : }}{{#if: | , deutsch: „“ }})
| {{#if:
| ({{#if: | , deutsch: „“ }})
| {{#if: | (deutsch: „“) }}
}}
}}{{#if: {{{zitat}}}
| {{#if:
| {{#if: {{{zitat}}}
| Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
| Vorlage:": Text= fehlt }}{{#if: | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
| Vorlage:": Ungültiger Wert: ref=
| {{{ref}}} }}
}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:
|0|=Vorlage:Toter Link/Core{{#if: https://sphincs.cr.yp.to/ | {{#if: | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://sphincs.cr.yp.to/ | {{#if:{{#invoke:URLutil|isWebURL|https://sphincs.cr.yp.to/}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://sphincs.cr.yp.to/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://sphincs.cr.yp.to/ | {{#if:{{#invoke:URLutil|isWebURL|https://sphincs.cr.yp.to/}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}[https://sphincs.cr.yp.to/ }}|{{#switch: |0|=Vorlage:Toter Link/Core{{#if: https://sphincs.cr.yp.to/ | {{#if: | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://sphincs.cr.yp.to/ | {{#if:{{#invoke:URLutil|isWebURL|https://sphincs.cr.yp.to/}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://sphincs.cr.yp.to/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://sphincs.cr.yp.to/ | {{#if:{{#invoke:URLutil|isWebURL|https://sphincs.cr.yp.to/}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}[https://sphincs.cr.yp.to/ }} }}}}}}}}}}{{#if:| {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}
}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</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: 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: 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; 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"> Vorlage:RFC-Internet </ref> </references>
- Wikipedia:Vorlagenfehler/Parameter:URL
- Wikipedia:Vorlagenfehler/Parameter:Linktext
- Wikipedia:Vorlagenfehler/Parameter:Datum
- Wikipedia:Vorlagenfehler/Vorlage:"
- Wikipedia:Weblink offline fix-attempted
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link/URL fehlt
- Signaturverfahren