www.wikidata.de-de.nina.az

Schnorr Signatur Die ist eine kryptographische Methode zur Berechnung und Prüfung digitaler Signaturen Sie wurde in den

Schnorr-Signatur

Die Schnorr-Signatur ist eine kryptographische Methode zur Berechnung und Prüfung digitaler Signaturen. Sie wurde in den Jahren 1989 bis 1991 von dem deutschen Mathematiker Claus Peter Schnorr ausgehend von der Schnorr-Identifikation entwickelt und publiziert. Das Signaturverfahren ist aus dem verwandten Identifikationsverfahren, auch Zero-Knowledge-Beweisverfahren genannt, entstanden. Im Gegensatz zur Fiat-Shamir-Identifikation ist keine mehrstufige Interaktion notwendig. Anders als bei der Schnorr-Identifikation wird beim Signaturverfahren eine Hashfunktion benötigt. Es wird nicht zwingend eine kollisionsresistente Hashfunktion benötigt, anders als beim Digital Signature Algorithm. Die Sicherheit beruht praktisch allein auf der Schwierigkeit den sogenannten diskreten Logarithmus in endlichen Gruppen zu berechnen. Ist diese Berechnung praktisch nicht möglich, kann die Signatur nur geprüft, aber ohne den privaten Schlüssel nicht berechnet werden.

Claus Peter Schnorr

Die Verfahren zur Identifikation und zur Signatur wurden von Claus Peter Schnorr patentiert. Die Schutzfrist ist inzwischen abgelaufen. Das Patent war exklusiv an das Unternehmen RSA lizenziert. Auch das deutsche Unternehmen Siemens hat eine nicht-exklusive Lizenz erworben. Schnorr warf im Rahmen der Standardisierung IEEE P1363 dem amerikanischen National Institute of Standards vor, mit dem von ihm entwickelten Signatur-Verfahren, Digital Signature Algorithm (DSA), sein Patent zu verletzen.

Die Sicherheit des Verfahrens ist nur gegeben, wenn die Ordnung der Untergruppe hinreichend groß ist. Die Signatur kann sonst mit der Pollard-Rho-Methode gefälscht werden. Die von Professor Schnorr vorgeschlagene Größenordnung für die Gruppenordnung q mit 140 Bits kann heute nicht mehr als ausreichend bewertet werden.

Parameter des Signatur-Verfahrens Bearbeiten

Systemweite Parameter Bearbeiten

Alle Benutzer können diese Parameter gemeinsam nutzen:

Schnorr schlägt vor, eine Untergruppe von für ein primes zu wählen. Um eine Untergruppe von zu finden, muss (p-1), die Ordnung von , in Primzahlen faktorisiert werden. Dann kann (p-1) als mal einem Cofaktor h geschrieben werden. Wenn g ein Generator von ist, kann ein Generator von als bestimmt werden.

Die Länge des privaten Schlüssels und der Signatur werden allein durch die Ordnung der Untergruppe bestimmt.

Privater Schlüssel zur Signaturerstellung Bearbeiten

Der private Schlüssel besteht aus einer zufällig gewählten Zahl

  • mit

Öffentlicher Schlüssel zur Prüfung der Signatur Bearbeiten

Der öffentliche Schlüssel ist das entsprechende Gruppenelement :

Berechnung der Signatur Bearbeiten

Um eine Nachricht zu unterschreiben, wird folgendermaßen verfahren:

  1. Wähle zufällig mit .
  2. Setze
  3. Setze . Dabei ist die Konkatenation.
  4. Setze .

Die Unterschrift der Nachricht ist das Tupel oder .

Für elliptische Kurven formuliert Bearbeiten

Wir betrachten eine elliptische Kurve der Ordnung q über GF(p). Der Generator G ist ein Punkt auf der Kurve und es sei der öffentliche Schlüssel.

  1. Wähle zufällig mit .
  2. Setze
  3. Setze . Dabei ist die Konkatenation und die -Koordinate des Punktes .
  4. Setze . Falls die Bitlänge von größer als die Bitlänge von ist, werden vor der Berechnung von die überzähligen (rechten) Bits von gestrichen.

Die Unterschrift der Nachricht ist das Tupel oder .

Verifizieren der Signatur Bearbeiten

Um eine Unterschrift einer Nachricht zu verifizieren, wird folgendermaßen verfahren:

  1. Setze
  2. Setze
  3. Akzeptiere die Unterschrift genau dann, wenn ist.

Wenn die Unterschrift im Format ist, kann es wie folgt verifiziert werden:

  1. Setze
  2. Akzeptiere die Unterschrift genau dann, wenn ist.

Mit elliptischer Kurve Bearbeiten

  1. Berechne
  2. Setze
  3. Akzeptiere die Unterschrift genau dann, wenn ist.

Wenn die Unterschrift im Format ist, kann es wie folgt verifiziert werden:

  1. Berechne
  2. Akzeptiere die Unterschrift genau dann, wenn ist.

Multi-Signatur Bearbeiten

Mit Schnorr-Signaturen ist es möglich, eine Nachricht mit mehreren Schlüsseln in einer Signatur zu unterschreiben.

Ein-Partei-Signaturen Bearbeiten

  1. Der Unterschreiber ist im Besitz von mehreren privaten Schlüsseln , womit auch mehrere öffentliche Schlüssel existieren
  2. Der Unterschreiber berechnet
  3. Beim Verifizieren ist

Batch verification Bearbeiten

Wenn mit unterschrieben wird, so ist es möglich, Signaturen und öffentliche Schlüssel zusammen zu rechnen.

Dies kann verwendet werden, um mehrere Signaturen gleichzeitig zu verifizieren. Das könnte in der Bitcoin-Blockchain verwendet werden, damit nicht alle Nodes alle Transaktionen validieren müssen.

Rogue key attack Bearbeiten

Man sollte nicht als Signatur vertrauen, da nicht erkennbar ist, ob es die Summe der öffentlichen Schlüssel ist oder nur der öffentliche Schlüssel einer Partei.

Bellare-Neven-Verfahren Bearbeiten

Eine Lösung ist, dass jede Partei den Hash aller öffentlichen Schlüssel mit-unterschreibt.

  2. bleibt das Produkt der einzelnen noncen:
  3. ist eine partielle Signatur die jeder für sich berechnet
  4. die danach zusammen addiert werden:

Mit kann man es verifizieren.

MuSig Bearbeiten

  3. so dass:
  4. so dass: Man sollte erst mit den anderen Parteien teilen, wenn man ein Commitment auf deren erhalten hat.

Dieses Verfahren hat den Vorteil, dass nur die involvierten Parteien die einzelnen öffentlichen Schlüssel kennen müssen. Ein Außenstehender kann mit dem kombinierten öffentlichen Schlüssel bestätigen, dass es sich um eine valide Signatur handelt. Besonders bei Blockchain-Anwendungen, in denen Privatsphäre wertvoll und Speicherplatz knapp ist, könnte das Schnorr-Verfahren, am Beispiel der Bitcoin-Blockchain bis zu 25 % Speicherplatz einsparen.

Sicherheitsdiskussion (informell) Bearbeiten

Der Wert xe und damit auch der Wert x wird durch die Zufallszahl k sicher verschlüsselt (One-Time-Pad). Die Sicherheit ist daher unter bestimmten Voraussetzungen über die verwendeten Zufallszahlen (k) und der Hashfunktion (Random-Oracle-Modell) auf die Komplexität des Diskreten Logarithmus in der verwendeten Gruppe beweisbar zu reduzieren, das heißt: Wer das Schnorr-Signatur-Schema berechnen kann, kann auch den Diskreten Logarithmus berechnen. Es ist kein Verfahren bekannt, mit dem sich der Diskrete Logarithmus in multiplikativen Gruppen von endlichen Körpern mit heutigen Computern effizient berechnen lässt. Diese beweisbare Reduktion auf bekannte, als schwierig eingestufte Probleme ist typisch für Sicherheitsbeweise bei kryptographischen Systemen mit öffentlichen Schlüsseln.

Im Random-Oracle-Modell nimmt man an, die Hashfunktion verhalte sich wie eine zufällige Funktion und ein Angreifer kann die Funktionswerte nur über ein Orakel für die Funktionswerte berechnen. Mit Hilfe eines Widerspruchsbeweises zeigt man nun die Korrektheit des Verfahrens: Angenommen, es gäbe einen erfolgreichen Unterschriftenfälscher für das Signaturverfahren. Dieses kann man nutzen, um aus dem öffentlichen Schlüssel den geheimen Schlüssel zu bestimmen, also den Diskreten Logarithmus von zu berechnen – im Widerspruch zur Annahme, der Diskrete Logarithmus sei schwierig.

  1. Simuliere den Algorithmus zum Unterschreiben einer Nachricht , speichere Zustand beim Aufruf des Orakels, um zu berechnen.
  2. Wiederhole die Simulation am gespeicherten Zustand, gib allerdings ein anderes zurück (Dies geht im Random-Oracle-Modell).
  3. Seien und die beiden (verschiedenen) Unterschriften zur gleichen Nachricht und gleichem Zufallswert bzw. .
  4. Es gilt , also .

Die Division durch ist möglich: Da prim ist, existiert zu jeder Zahl ungleich 0 auch ein Inverses modulo .

Anforderung an die Zufallszahlen Bearbeiten

Aus den obigen Ausführungen folgt, dass sich die Zufallszahlen k, die zur Berechnung der Signatur verwendet werden, keinesfalls wiederholen dürfen. Würde eine Zufallszahl zur Signatur zweier unterschiedlicher Nachrichten verwendet, könnte der private Schlüssel x aus öffentlich bekannten Werten berechnet werden. Damit könnten dann Signaturen von einem Angreifer gefälscht werden. Weiterhin dürfen die Zufallszahlen für den Angreifer nicht berechenbar sein, da er sonst x berechnen könnte.

Fälschung der Signatur ohne Kenntnis des privaten Schlüssels Bearbeiten

In den meisten Betrachtungen zur digitale Signatur wird eine Fragestellung ganz ausgeklammert. Es wird unterstellt, dass die Signatur nur zu fälschen sei, wenn der private Schlüssel x vom Angreifer ermittelt werden kann. Es ist jedoch auch denkbar zu einer vorgegebenen Signatur, zu einem Wertepaar (e,s), eine gefälschte Nachricht m zu finden, so dass die Prüfung der Signatur erfolgreich ist. Dazu genügt es, wenn der Hashwert H(r || m) den gewünschten, vom Fälscher erwünschten Wert, nämlich den vorgegebenen Wert e ergibt. Um dies auszuschließen, muss die Hashfunktion Preimage-resistent sein.

Eine solche Fälschung würde jedoch nur die Fälschung einer einzigen Nachricht ermöglichen. Wichtiger ist daher die Geheimhaltung des privaten Schlüssels x. Die Geheimhaltung ist mathematisch beweisbar sichergestellt, wenn der Zufallswert k echt zufällig und gleichverteilt ist.

Literatur Bearbeiten

Weblinks Bearbeiten

  • Claus Peter Schnorr, Vorlesung Kryptographie I/II, Kapitel 1.7, online (PDF; 454 kB)

Einzelnachweise Bearbeiten

  1. Patent EP0384475: Angemeldet am 22. Februar 1990.‌
  2. Patent US4995082: Angemeldet am 23. Februar 1990.‌
  3. (Nicht mehr online verfügbar.) Archiviert vom Original am 13. Oktober 2016; abgerufen am 25. Januar 2018.
  4. Claus Peter Schnorr: Efficient Signature Generation by Smart Cards. Journal of Cryptology, Vol. 4, 1991, S. 161–174., https://publikationen.ub.uni-frankfurt.de/opus4/frontdoor/deliver/index/docId/4280/file/schnorr.pdf
  5. Github: BIP-340. Abgerufen am 15. März 2020.
  6. UCSD: Paper. Abgerufen am 15. März 2020.
  7. Sam Wouters: Why Schnorr signatures will help solve 2 of Bitcoin’s biggest problems today, 4. Juli 2017. Abgerufen am 30. Dezember 2017.
  8. Blockstream: Schnorr Multisig. Abgerufen am 15. März 2020.
  9. iarc: Multi-Signatures with Applications to Bitcoin. Abgerufen am 15. März 2020.
  10. David Pointcheval, Jacques Stern: Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13 (3), 2000, S. 361–396.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Schnorr Signatur ist eine kryptographische Methode zur Berechnung und Prufung digitaler Signaturen Sie wurde in den Jahren 1989 bis 1991 von dem deutschen Mathematiker Claus Peter Schnorr ausgehend von der Schnorr Identifikation entwickelt und publiziert Das Signaturverfahren ist aus dem verwandten Identifikationsverfahren auch Zero Knowledge Beweisverfahren genannt entstanden Im Gegensatz zur Fiat Shamir Identifikation ist keine mehrstufige Interaktion notwendig Anders als bei der Schnorr Identifikation wird beim Signaturverfahren eine Hashfunktion benotigt Es wird nicht zwingend eine kollisionsresistente Hashfunktion benotigt anders als beim Digital Signature Algorithm Die Sicherheit beruht praktisch allein auf der Schwierigkeit den sogenannten diskreten Logarithmus in endlichen Gruppen zu berechnen Ist diese Berechnung praktisch nicht moglich kann die Signatur nur gepruft aber ohne den privaten Schlussel nicht berechnet werden Claus Peter SchnorrDie Verfahren zur Identifikation und zur Signatur wurden von Claus Peter Schnorr patentiert 1 2 Die Schutzfrist ist inzwischen abgelaufen Das Patent war exklusiv an das Unternehmen RSA lizenziert Auch das deutsche Unternehmen Siemens hat eine nicht exklusive Lizenz erworben Schnorr warf im Rahmen der Standardisierung IEEE P1363 dem amerikanischen National Institute of Standards vor mit dem von ihm entwickelten Signatur Verfahren Digital Signature Algorithm DSA sein Patent zu verletzen 3 Die Sicherheit des Verfahrens ist nur gegeben wenn die Ordnung der Untergruppe hinreichend gross ist Die Signatur kann sonst mit der Pollard Rho Methode gefalscht werden Die von Professor Schnorr vorgeschlagene Grossenordnung fur die Gruppenordnung q mit 140 Bits 4 kann heute nicht mehr als ausreichend bewertet werden Inhaltsverzeichnis 1 Parameter des Signatur Verfahrens 1 1 Systemweite Parameter 1 2 Privater Schlussel zur Signaturerstellung 1 3 Offentlicher Schlussel zur Prufung der Signatur 2 Berechnung der Signatur 2 1 Fur elliptische Kurven formuliert 3 Verifizieren der Signatur 3 1 Mit elliptischer Kurve 4 Multi Signatur 4 1 Ein Partei Signaturen 4 2 Batch verification 4 2 1 Rogue key attack 4 3 Bellare Neven Verfahren 4 4 MuSig 5 Sicherheitsdiskussion informell 5 1 Anforderung an die Zufallszahlen 6 Falschung der Signatur ohne Kenntnis des privaten Schlussels 7 Literatur 8 Weblinks 9 EinzelnachweiseParameter des Signatur Verfahrens BearbeitenSystemweite Parameter Bearbeiten Alle Benutzer konnen diese Parameter gemeinsam nutzen Eine Gruppe G displaystyle G nbsp primer Ordnung q G displaystyle q G nbsp Diese ist zyklisch sei g displaystyle g nbsp ein Generator Eine kryptografische Hash Funktion H displaystyle H nbsp mit Wertebereich 0 q 1 displaystyle 0 q 1 nbsp Schnorr schlagt vor eine Untergruppe G displaystyle G nbsp von Z p displaystyle Z p nbsp fur ein primes p displaystyle p nbsp zu wahlen Um eine Untergruppe von Z p displaystyle Z p nbsp zu finden muss p 1 die Ordnung von Z p displaystyle Z p nbsp in Primzahlen faktorisiert werden Dann kann p 1 als q G displaystyle q G nbsp mal einem Cofaktor h geschrieben werden Wenn g ein Generator von Z p displaystyle Z p nbsp ist kann ein Generator von G displaystyle G nbsp als g h displaystyle g h nbsp bestimmt werden Die Lange des privaten Schlussels und der Signatur werden allein durch die Ordnung der Untergruppe q G displaystyle q G nbsp bestimmt Privater Schlussel zur Signaturerstellung Bearbeiten Der private Schlussel besteht aus einer zufallig gewahlten Zahl x displaystyle x nbsp mit 0 lt x lt q displaystyle 0 lt x lt q nbsp Offentlicher Schlussel zur Prufung der Signatur Bearbeiten Der offentliche Schlussel x displaystyle x nbsp ist das entsprechende Gruppenelement y displaystyle y nbsp y g x displaystyle y g x nbsp Berechnung der Signatur BearbeitenUm eine Nachricht m displaystyle m nbsp zu unterschreiben wird folgendermassen verfahren Wahle k displaystyle k nbsp zufallig mit 0 lt k lt q displaystyle 0 lt k lt q nbsp Setze r g k displaystyle r g k nbsp Setze e H r m displaystyle e H r m nbsp Dabei ist displaystyle nbsp die Konkatenation Setze s k x e mod q displaystyle s k xe bmod q nbsp Die Unterschrift der Nachricht ist das Tupel e s displaystyle e s nbsp oder r s displaystyle r s nbsp Fur elliptische Kurven formuliert Bearbeiten Wir betrachten eine elliptische Kurve der Ordnung q uber GF p Der Generator G ist ein Punkt auf der Kurve und es sei Y x G displaystyle Y x cdot G nbsp der offentliche Schlussel Wahle k displaystyle k nbsp zufallig mit 0 lt k lt q displaystyle 0 lt k lt q nbsp Setze R k G displaystyle R k cdot G nbsp Setze e H R x m displaystyle e H R x m nbsp Dabei ist displaystyle nbsp die Konkatenation und R x displaystyle R x nbsp die x displaystyle x nbsp Koordinate des Punktes R displaystyle R nbsp Setze s k x e mod q displaystyle s k xe bmod q nbsp Falls die Bitlange von e displaystyle e nbsp grosser als die Bitlange von q displaystyle q nbsp ist werden vor der Berechnung von s displaystyle s nbsp die uberzahligen rechten Bits von e displaystyle e nbsp gestrichen Die Unterschrift der Nachricht m displaystyle m nbsp ist das Tupel e s displaystyle e s nbsp oder R s displaystyle R s nbsp Verifizieren der Signatur BearbeitenUm eine Unterschrift e s displaystyle e s nbsp einer Nachricht m displaystyle m nbsp zu verifizieren wird folgendermassen verfahren Setze r v g s y e displaystyle r v g s cdot y e nbsp Setze e v H r v m displaystyle e v H r v m nbsp Akzeptiere die Unterschrift genau dann wenn e v e displaystyle e v e nbsp ist Wenn die Unterschrift im Format r s displaystyle r s nbsp ist kann es wie folgt verifiziert werden Setze r v g s y H r m displaystyle r v g s cdot y H r m nbsp Akzeptiere die Unterschrift genau dann wenn r v r displaystyle r v r nbsp ist Mit elliptischer Kurve Bearbeiten Berechne R s G e Y displaystyle R s cdot G e cdot Y nbsp Setze e v H R x m displaystyle e v H R x m nbsp Akzeptiere die Unterschrift genau dann wenn e v e displaystyle e v e nbsp ist Wenn die Unterschrift im Format R s displaystyle R s nbsp ist kann es wie folgt verifiziert werden Berechne R v s G H R x m Y displaystyle R v s cdot G H R x m cdot Y nbsp Akzeptiere die Unterschrift genau dann wenn R v R displaystyle R v R nbsp ist Multi Signatur BearbeitenMit Schnorr Signaturen ist es moglich eine Nachricht mit mehreren Schlusseln in einer Signatur zu unterschreiben Ein Partei Signaturen Bearbeiten Der Unterschreiber ist im Besitz von mehreren privaten Schlusseln x i displaystyle x i nbsp womit auch mehrere offentliche Schlussel y i displaystyle y i nbsp existieren Der Unterschreiber berechnet s k x 1 e x 2 e x 3 e displaystyle s k x 1 cdot e x 2 cdot e x 3 cdot e dotsb nbsp Beim Verifizieren ist r v g s y 1 e y 2 e y 3 e displaystyle r v g s cdot y 1 e cdot y 2 e cdot y 3 e cdot ldots nbsp Batch verification Bearbeiten Wenn mit r s displaystyle r s nbsp unterschrieben wird so ist es moglich Signaturen und offentliche Schlussel zusammen zu rechnen s s 1 s 2 s 3 displaystyle s s 1 s 2 s 3 dotsb nbsp r r 1 r 2 r 3 displaystyle r r 1 cdot r 2 cdot r 3 cdot ldots nbsp y y 1 y 2 y 3 displaystyle y y 1 cdot y 2 cdot y 3 cdot ldots nbsp Dies kann verwendet werden um mehrere Signaturen gleichzeitig zu verifizieren Das konnte in der Bitcoin Blockchain verwendet werden damit nicht alle Nodes alle Transaktionen validieren mussen 5 Rogue key attack Bearbeiten Man sollte y displaystyle y nbsp nicht als Signatur vertrauen da nicht erkennbar ist ob es die Summe der offentlichen Schlussel ist oder nur der offentliche Schlussel einer Partei Bellare Neven Verfahren Bearbeiten Eine Losung ist dass jede Partei den Hash aller offentlichen Schlussel mit unterschreibt L H y 1 y 2 y 3 displaystyle L H y 1 y 2 y 3 dotsb nbsp r displaystyle r nbsp bleibt das Produkt der einzelnen noncen r r 1 r 2 r 3 displaystyle r r 1 cdot r 2 cdot r 3 cdot ldots nbsp s i displaystyle s i nbsp ist eine partielle Signatur die jeder fur sich berechnet s i k i x H L y i r m displaystyle s i k i x cdot H L y i r m nbsp die danach zusammen addiert werden s s 1 s 2 s 3 displaystyle s s 1 s 2 s 3 dotsb nbsp Mit g s r y 1 H L y 1 r m y 2 H L y 2 r m y 3 H L y 3 r m displaystyle g s r cdot y 1 H L y 1 r m cdot y 2 H L y 2 r m cdot y 3 H L y 3 r m cdot ldots nbsp kann man es verifizieren 6 MuSig Bearbeiten L H y 1 y 2 y 3 displaystyle L H y 1 y 2 y 3 dotsb nbsp a i H L y i displaystyle a i H L y i nbsp y y 1 a 1 y 2 a 2 y 3 a 3 displaystyle y y 1 a 1 cdot y 2 a 2 cdot y 3 a 3 cdot ldots nbsp so dass y g x 1 a 1 x 2 a 2 x 3 a 3 displaystyle y g x 1 cdot a 1 x 2 cdot a 2 x 3 cdot a 3 dotsb nbsp r r 1 r 2 r 3 displaystyle r r 1 cdot r 2 cdot r 3 cdot ldots nbsp so dass r g k 1 k 2 k 3 displaystyle r g k 1 k 2 k 3 dotsb nbsp Man sollte r i displaystyle r i nbsp erst mit den anderen Parteien teilen wenn man ein Commitment auf deren r i displaystyle r i nbsp erhalten hat c H y r m displaystyle c H y r m nbsp s i r i c a i x i displaystyle s i r i ca i x i nbsp s s 1 s 2 s 3 displaystyle s s 1 s 2 s 3 dotsb nbsp Dieses Verfahren hat den Vorteil dass nur die involvierten Parteien die einzelnen offentlichen Schlussel kennen mussen Ein Aussenstehender kann mit dem kombinierten offentlichen Schlussel bestatigen dass es sich um eine valide Signatur handelt Besonders bei Blockchain Anwendungen in denen Privatsphare wertvoll und Speicherplatz knapp ist konnte das Schnorr Verfahren am Beispiel der Bitcoin Blockchain bis zu 25 Speicherplatz einsparen 7 8 9 Sicherheitsdiskussion informell BearbeitenDer Wert xe und damit auch der Wert x wird durch die Zufallszahl k sicher verschlusselt One Time Pad Die Sicherheit ist daher unter bestimmten Voraussetzungen uber die verwendeten Zufallszahlen k und der Hashfunktion Random Oracle Modell auf die Komplexitat des Diskreten Logarithmus in der verwendeten Gruppe beweisbar zu reduzieren das heisst Wer das Schnorr Signatur Schema berechnen kann kann auch den Diskreten Logarithmus berechnen 10 Es ist kein Verfahren bekannt mit dem sich der Diskrete Logarithmus in multiplikativen Gruppen von endlichen Korpern mit heutigen Computern effizient berechnen lasst Diese beweisbare Reduktion auf bekannte als schwierig eingestufte Probleme ist typisch fur Sicherheitsbeweise bei kryptographischen Systemen mit offentlichen Schlusseln Im Random Oracle Modell nimmt man an die Hashfunktion verhalte sich wie eine zufallige Funktion und ein Angreifer kann die Funktionswerte nur uber ein Orakel fur die Funktionswerte berechnen Mit Hilfe eines Widerspruchsbeweises zeigt man nun die Korrektheit des Verfahrens Angenommen es gabe einen erfolgreichen Unterschriftenfalscher fur das Signaturverfahren Dieses kann man nutzen um aus dem offentlichen Schlussel y g x displaystyle y g x nbsp den geheimen Schlussel x displaystyle x nbsp zu bestimmen also den Diskreten Logarithmus x displaystyle x nbsp von y displaystyle y nbsp zu berechnen im Widerspruch zur Annahme der Diskrete Logarithmus sei schwierig Simuliere den Algorithmus zum Unterschreiben einer Nachricht m displaystyle m nbsp speichere Zustand beim Aufruf des Orakels um e 1 H m r displaystyle e 1 H m r nbsp zu berechnen Wiederhole die Simulation am gespeicherten Zustand gib allerdings ein anderes e 2 H m r displaystyle e 2 H m r nbsp zuruck Dies geht im Random Oracle Modell Seien s 1 displaystyle s 1 nbsp und s 2 displaystyle s 2 nbsp die beiden verschiedenen Unterschriften zur gleichen Nachricht m displaystyle m nbsp und gleichem Zufallswert k displaystyle k nbsp bzw r displaystyle r nbsp Es gilt s 1 s 2 k x e 1 k x e 2 x e 1 e 2 mod q displaystyle s 1 s 2 k xe 1 k xe 2 x e 1 e 2 mod q nbsp also x s 1 s 2 e 1 e 2 mod q displaystyle x s 1 s 2 e 1 e 2 mod q nbsp Die Division durch e 1 e 2 displaystyle e 1 e 2 nbsp ist moglich Da q displaystyle q nbsp prim ist existiert zu jeder Zahl ungleich 0 auch ein Inverses modulo q displaystyle q nbsp Anforderung an die Zufallszahlen Bearbeiten Aus den obigen Ausfuhrungen folgt dass sich die Zufallszahlen k die zur Berechnung der Signatur verwendet werden keinesfalls wiederholen durfen Wurde eine Zufallszahl zur Signatur zweier unterschiedlicher Nachrichten verwendet konnte der private Schlussel x aus offentlich bekannten Werten berechnet werden Damit konnten dann Signaturen von einem Angreifer gefalscht werden Weiterhin durfen die Zufallszahlen fur den Angreifer nicht berechenbar sein da er sonst x berechnen konnte Falschung der Signatur ohne Kenntnis des privaten Schlussels BearbeitenIn den meisten Betrachtungen zur digitale Signatur wird eine Fragestellung ganz ausgeklammert Es wird unterstellt dass die Signatur nur zu falschen sei wenn der private Schlussel x vom Angreifer ermittelt werden kann Es ist jedoch auch denkbar zu einer vorgegebenen Signatur zu einem Wertepaar e s eine gefalschte Nachricht m zu finden so dass die Prufung der Signatur erfolgreich ist Dazu genugt es wenn der Hashwert H r m den gewunschten vom Falscher erwunschten Wert namlich den vorgegebenen Wert e ergibt Um dies auszuschliessen muss die Hashfunktion Preimage resistent sein Eine solche Falschung wurde jedoch nur die Falschung einer einzigen Nachricht ermoglichen Wichtiger ist daher die Geheimhaltung des privaten Schlussels x Die Geheimhaltung ist mathematisch beweisbar sichergestellt wenn der Zufallswert k echt zufallig und gleichverteilt ist Literatur BearbeitenClaus Peter Schnorr Efficient Signature Generation by Smart Cards Journal of Cryptology Vol 4 1991 S 161 174 Online PDF 0 7 MB Bruce Schneier Angewandte Kryptographie Addison Wesley 1996 ISBN 3 89319 854 7 S 583 Weblinks BearbeitenClaus Peter Schnorr Vorlesung Kryptographie I II Kapitel 1 7 online PDF 454 kB Einzelnachweise Bearbeiten Patent EP0384475 Angemeldet am 22 Februar 1990 Patent US4995082 Angemeldet am 23 Februar 1990 IEEE P1363 Patent Reply from Claus Peter Schnorr Nicht mehr online verfugbar Archiviert vom Original am 13 Oktober 2016 abgerufen am 25 Januar 2018 Claus Peter Schnorr Efficient Signature Generation by Smart Cards Journal of Cryptology Vol 4 1991 S 161 174 https publikationen ub uni frankfurt de opus4 frontdoor deliver index docId 4280 file schnorr pdf Github BIP 340 Abgerufen am 15 Marz 2020 UCSD Paper Abgerufen am 15 Marz 2020 Sam Wouters Why Schnorr signatures will help solve 2 of Bitcoin s biggest problems today 4 Juli 2017 Abgerufen am 30 Dezember 2017 Blockstream Schnorr Multisig Abgerufen am 15 Marz 2020 iarc Multi Signatures with Applications to Bitcoin Abgerufen am 15 Marz 2020 David Pointcheval Jacques Stern Security arguments for digital signatures and blind signatures Journal of Cryptology 13 3 2000 S 361 396 Abgerufen von https de wikipedia org w index php title Schnorr Signatur amp oldid 237962194