Nachdem wir Electronic Cash auf hohem Niveau beschrieben haben, wollen wir nun die konkreten Umsetzungen beschreiben, die in der Literatur vorgeschlagen wurden. Solche Implementierungen sind für den Offline-Fall gedacht; die Online-Protokolle sind lediglich Vereinfachungen. Der erste Schritt besteht darin, die verschiedenen Implementierungen der Public-Key-Kryptographie-Tools, die wir bereits beschrieben haben, zu diskutieren.
Zuerst müssen wir genauer festlegen, wie wir die identifizierenden Informationen, die dazu bestimmt sind, mehrere Spender zu fangen, einbeziehen (und bei Bedarf darauf zugreifen) können. Es gibt zwei Möglichkeiten, dies zu tun: die Cut-and-Choose-Methode und Zero-Knowledge-Proofs.
Wenn Alice eine Auszahlung machen möchte, konstruiert und blendet sie zuerst eine Nachricht, die aus K Zahlenpaaren besteht, wobei K groß genug ist, dass ein Ereignis mit der Wahrscheinlichkeit 2-K in der Praxis niemals eintreten wird. Diese Nummern haben die Eigenschaft, dass man Alice identifizieren kann, wenn man beide Teile eines Paares erhält, aber nicht übereinstimmende Teile sind nutzlos. Sie erhält dann von der Bank die Unterschrift dieser verblendeten Botschaft. (Dies geschieht so, dass die Bank überprüfen kann, ob die K-Zahlenpaare vorhanden sind und trotz der Verblendung die geforderten Eigenschaften besitzen.)
Wenn Alice ihre Münzen an Bob übergibt, ist seine Herausforderung für sie eine Reihe von K zufälligen Bits. Für jedes Bit sendet Alice das entsprechende Stück des entsprechenden Paares. Zum Beispiel, wenn der Bitstring 0110 beginnt. dann schickt Alice das erste Stück des ersten Paares, das zweite Stück des zweiten Paares, das zweite Stück des dritten Paares, das erste Stück des vierten Paares, usw. Wenn Bob die Münze bei der Bank deponiert, schickt er diese K-Stücke.
Wenn Alice ihre Münze wieder ausgibt, wird sie ein zweites Mal herausgefordert. Da jede Challenge ein zufälliger Bitstring ist, wird die neue Challenge in mindestens einem Bit mit der alten nicht übereinstimmen. Alice muss also das andere Stück des entsprechenden Paares aufdecken. Wenn die Bank die Münze ein zweites Mal erhält, nimmt sie die beiden Stücke und kombiniert sie, um die Identität von Alice zu enthüllen.
Obwohl konzeptionell einfach, ist dieses Schema nicht sehr effizient, da jede Münze von 2K großen Zahlen begleitet werden muss.
Der Begriff Zero-Knowledge-Proof bezieht sich auf jedes Protokoll in der Public-Key-Kryptographie, das die Kenntnis einer bestimmten Menge beweist, ohne sie zu enthüllen (oder sie leichter auffindbar zu machen). In diesem Fall erstellt Alice ein Schlüsselpaar, so dass der geheime Schlüssel auf ihre Identität verweist.
Dies geschieht so, dass die Bank über den öffentlichen Schlüssel überprüfen kann, ob der geheime Schlüssel trotz der Verblendung tatsächlich ihre Identität preisgibt. Im Zahlungsprotokoll gibt sie Bob den öffentlichen Schlüssel als Teil der elektronischen Münze. Sie beweist Bob dann durch einen Null-Wissens-Nachweis, dass sie den entsprechenden geheimen Schlüssel besitzt. Wenn sie auf zwei unterschiedliche Herausforderungen reagiert, können die identifizierenden Informationen zusammengefügt werden, um den geheimen Schlüssel und damit ihre Identität zu enthüllen.
Unser nächster Schritt ist die Beschreibung der digitalen Signaturen, die in den Implementierungen der oben genannten Protokolle verwendet wurden, und der Techniken, die verwendet wurden, um identifizierende Informationen einzubeziehen.
Es gibt zwei Arten von digitalen Signaturen, und beide Arten erscheinen in Electronic-Cash-Protokollen. Angenommen, der Unterzeichner hat ein Schlüsselpaar und eine Nachricht M, die signiert werden soll.
Für diese Art der Signatur haben wir eine Signierfunktion SSK mit dem geheimen Schlüssel SK und eine Verifizierungsfunktion VPK mit dem öffentlichen Schlüssel PK. Diese Funktionen sind invers, so daß
(*) VPK (SSK (M)) = M
Die Funktion VPK ist einfach zu implementieren, während SSK einfach ist, wenn man SK kennt, und ansonsten schwierig. So hat SSK angeblich eine Falltür oder geheime Menge, die es ermöglicht, eine kryptographische Berechnung durchzuführen, die ansonsten nicht durchführbar ist. Die Funktion VPK wird als Falltür-Einwegfunktion bezeichnet, da es sich um eine Einwegfunktion für jeden handelt, der die Falltür nicht kennt.
Bei dieser Art von Schema erhält der Prüfer die signierte Nachricht SSK (M), aber nicht den ursprünglichen Nachrichtentext. Der Verifizierer wendet dann die Verifikationsfunktion VPK an. In diesem Schritt wird sowohl die Identität des Unterzeichners überprüft als auch durch (*) der Nachrichtentext wiederhergestellt.
Bei dieser Art der Signatur führt der Unterzeichner eine Operation an der Nachricht mit seinem eigenen geheimen Schlüssel durch. Das Ergebnis gilt als Signatur der Nachricht und wird als Anhang zum Nachrichtentext mitgeschickt. Der Verifizierer überprüft eine Gleichung, die die Nachricht, den Anhang und den öffentlichen Schlüssel des Unterzeichners enthält. Wenn die Gleichung überprüft wird, weiß der Prüfer, dass der geheime Schlüssel des Unterzeichners zur Erzeugung der Signatur verwendet wurde.
Wir geben nun spezifische Algorithmen vor.
Die bekannteste Signatur mit Nachrichtenwiederherstellung ist die RSA-Signatur. Lassen Sie N eine schwer zu faktorisierende ganze Zahl sein. Der geheime Signaturschlüssel s und der öffentliche Verifizierungsschlüssel v sind Exponenten mit der Eigenschaft, dass
Msv = M (mod N) [ = hier sind 3 Variablen]
für alle Meldungen M. Gegeben v, ist es einfach, s zu finden, wenn man die Faktoren von N kennt, aber ansonsten schwierig. Die Karte "vth Wurzel von (mod N)" ist also eine Falltür-Einwegfunktion. Die Signatur von M ist
C := Ms (mod N);
um die Nachricht wiederherzustellen (und die Signatur zu verifizieren), berechnet man
M := Cv (mod N).
Das obige Schema ist leicht zu verblenden. Angenommen, Alice möchte, dass die Bank eine blinde Signatur der Nachricht M erstellt. Sie erzeugt eine Zufallszahl r und sendet
rv ⋅ M (mod N)
an die Bank zur Unterzeichnung. Die Bank tut dies mit der Rückgabe von
r ⋅ Ms (mod N)
Alice teilt dann dieses Ergebnis durch r. Das Ergebnis ist Ms (mod N), die Unterschrift der Bank von M, obwohl die Bank M noch nie gesehen hat.
Die Schnorr-Algorithmenfamilie umfasst ein Identifikationsverfahren und eine Signatur mit Anhang. Diese Algorithmen basieren auf einem Null-Kenntnis-Nachweis des Besitzes eines geheimen Schlüssels. Lassen Sie p und q große Primzahlen mit q Teilung (p - 1) sein. Lassen Sie g ein Generator sein, d.h. eine ganze Zahl zwischen 1 und p, so dass
gq = 1 (mod p). [ = hier sind 3 Unbekannte]
Wenn s eine ganze Zahl ist (mod q), dann ist die modulare Potenzierungsoperation auf s
f: s -> gs (mod p).
Die umgekehrte Operation wird als diskrete Logarithmusfunktion bezeichnet und bezeichnet.
logg t <- t.
Wenn p und q richtig gewählt sind, dann ist die modulare Potenzierung eine Einwegfunktion. Das heißt, es ist rechnerisch nicht möglich, einen diskreten Logarithmus zu finden.
Nehmen wir an, wir haben eine Linie
(**) y = mx + b
über das Feld der Ganzzahlen (mod q). Eine Linie kann beschrieben werden, indem man ihre Steigung m und den Abschnitt b angibt, aber wir werden sie wie folgt "verstecken". Lassen Sie
c = gb (mod p),
n = gm (mod p).
Dann geben uns c und n den "Schatten" der Linie unter f. Das Wissen um c und n gibt uns nicht die Steigung oder den Schnittpunkt der Linie, aber es ermöglicht uns festzustellen, ob ein bestimmter Punkt (x, y) auf der Linie ist. Denn wenn (x, y) erfüllt (**), dann muss es auch die Beziehung
(***) gy = nx. c (mod p). [ = hier sind 3 Unbekannte]
Umgekehrt muss jeder Punkt (x, y), der (***) befriedigend ist, auf der Linie liegen. Die Beziehung (***) kann von jedermann überprüft werden, da es sich nur um öffentliche Mengen handelt. So kann jeder überprüfen, ob ein bestimmter Punkt auf der Linie ist, aber Punkte auf der Linie können nur von jemandem erzeugt werden, der die geheimen Informationen kennt.
Das Schnorr-Basisprotokoll ist ein Null-Wissens-Nachweis, dass man eine vorgegebene Geheimzahl m besitzt. Angenommen, ein Benutzer (der "Prüfer") möchte einen anderen (den "Verifizierer") davon überzeugen, dass er m kennt, ohne es zu enthüllen. Er tut dies, indem er eine Linie (**) konstruiert und ihren Schatten an den Verifizierer schickt. Die Steigung der Linie wird als geheime Größe m angenommen, und der Prüfer wählt den Abschnitt zufällig, je nach Ausführung des Protokolls unterschiedlich. Das Protokoll geht dann wie folgt vor.
Schnorr-Beweis des Besitzes:
1. Alice schickt c (und ggf. n) an Bob.
2. Bob schickt Alice einen "Challenge"-Wert von x.
3. Alice antwortet mit dem Wert von y, so dass (x, y) auf der Linie steht.
4. Bob verifiziert mit (**), dass (x, y) auf der Linie ist.
Bob weiß jetzt, dass er mit jemandem spricht, der Punkte auf der Linie generieren kann. Diese Partei muss also die Steigung der Linie kennen, die die geheime Größe m ist.
Ein wichtiges Merkmal dieses Protokolls ist, dass es nur einmal pro Linie ausgeführt werden kann. Denn wenn er zwei beliebige Punkte (x0, y0) und (x1, y1) auf der Linie kennt, kann der Verifizierer die Steigung der Linie mit der bekannten Formel "rise over the run" berechnen.
m = y0 - y1 / x0 - x1 (mod q),
und diese Steigung ist die geheime Größe m. Deshalb muss jedes Mal ein neuer Abschnitt erzeugt werden. Wir nennen dies das Two-Points-on-a-line-Prinzip. Dieses Feature wird für Electronic-Cash-Protokolle nützlich sein, da wir ein Ausgabeverfahren definieren wollen, das nichts von einem geheimen Schlüssel enthüllt, wenn er einmal pro Münze verwendet wird, aber den Schlüssel enthüllt, wenn eine Münze zweimal ausgegeben wird.
Schnorr-Identifikation.
Das obige Protokoll kann zur Identifizierung von Benutzern in einem Netzwerk verwendet werden. Jedem Benutzer wird ein Schlüsselpaar zugeteilt, und jeder öffentliche Schlüssel wird als zugehörig zu einem bestimmten Benutzer beworben. Um sich zu identifizieren, muss ein Benutzer nur beweisen, dass er seinen geheimen Schlüssel kennt. Dies kann mit dem obigen Null-Wissen-Nachweis geschehen, da ihr öffentlicher Schlüssel mit ihrer Identität verknüpft ist.
Schnorr-Signatur.
Es ist einfach, das Schnorr-Identifikationsprotokoll in ein digitales Signaturschema umzuwandeln. Anstatt eine Aufforderung von einem Online-Verifizierer zu erhalten, nimmt der Unterzeichner einfach x als sicheren Hash der Nachricht und des Schattens der Linie. Dies beweist die Kenntnis seines geheimen Schlüssels in einer Weise, die sein Schlüsselpaar mit der Nachricht verknüpft.
Blinde Schnorr-Signatur.
Angenommen, Alice möchte eine blinde Schnorr-Signatur für ihre Münze erhalten, die sie an Bob ausgeben wird. Alice erzeugt zufällige Größen (mod q), die eine Veränderung von Variablen beschreiben. Diese Änderung der Variablen ersetzt die versteckte Linie der Bank durch eine andere Linie und den Punkt auf der Linie der Bank durch einen Punkt auf der neuen Linie. Wenn Bob die Unterschrift der Bank überprüft, überprüft er den neuen Punkt auf der neuen Linie. Die beiden Linien haben die gleiche Neigung, so dass die Unterschrift der Bank gültig bleibt. Wenn die Bank die Münze zur Einzahlung erhält, wird sie das Protokoll auf der neuen Linie implementiert sehen, aber sie wird nicht in der Lage sein, die Münze mit Alices Abhebung zu verknüpfen, da nur Alice die Änderung der Variablen kennt, die sich auf die beiden Linien beziehen.
Eine Variante von Schnorrs Signaturschema aus [6] wird in Electronic-Cash-Protokollen verwendet. Bei diesem modifizierten Schema handelt es sich um eine Art "Doppelschnorr"-Schema. Es handelt sich um eine einzelne Linie und einen Punkt, aber es werden zwei Schatten verwendet. Dieses Signaturschema kann ähnlich wie die gewöhnliche Schnorr-Signatur geblendet werden.
Wir haben die Schnorr-Algorithmen in Form von Ganzzahlen modulo a prime p beschrieben. Die Protokolle funktionieren jedoch in jeder Umgebung, in der das Analogon des diskreten Logarithmusproblems schwierig ist. Ein wichtiges Beispiel sind die elliptischen Kurven (siehe [10]). Elliptische-Kurven-basierte Protokolle sind viel schneller und erfordern die Übertragung von weitaus weniger Daten als nicht-elliptische Protokolle, die das gleiche Maß an Sicherheit bieten.
Wir können nun Zusammenfassungen der wichtigsten Offline-Cash-Schemata aus der wissenschaftlichen Literatur präsentieren. Es gibt drei: die von Chaum-Fiat-Naor [4], Brands [1] und Ferguson [9].
Dies war das erste Electronic-Cash-System und ist konzeptionell das einfachste. Die Bank erstellt eine elektronische Münze, indem sie eine blinde RSA-Signatur für den Auszahlungsantrag von Alice vornimmt, nachdem sie interaktiv verifiziert hat, dass Alice ihre Identifizierungsdaten auf der Münze angegeben hat. Die Vermeidung von Mehrfachausgaben wird durch die Cut-and-Choose-Methode erreicht. Aus diesem Grund ist diese Regelung relativ ineffizient.
Das Schema von Brands ist Schnorr-basiert.8 Tatsächlich wird ein Schnorr-Protokoll zweimal verwendet: Bei der Auszahlung führt die Bank eine blinde Chaum-Pederson-Signatur durch, und dann führt Alice einen Schnorr-Besitznachweis als Challenge-and-Response-Teil des Ausgabeprotokolls durch.
Der Auszahlungsschritt erzeugt eine Münze, die die Unterschrift der Bank enthält und sowohl die Identifizierungsdaten von Alice als auch den Schatten der Linie, die für den Besitznachweis verwendet werden soll, authentifiziert. Dies verpflichtet Alice dazu, diese bestimmte Linie im Ausgabeschritt zu verwenden. Wenn sie die Münze erneut ausgibt, muss sie die gleiche Linie zweimal verwenden, damit die Bank sie identifizieren kann.
Das Brands-Programm wird von vielen als das beste der drei Systeme angesehen, und zwar aus zwei Gründen. Erstens vermeidet es die umständliche Cut-and-Choose-Technik. Zweitens basiert es nur auf den Schnorr-Protokollen und kann daher in verschiedenen Einstellungen wie z.B. elliptischen Kurven implementiert werden.
Fergusons Schema ist RSA-basiert wie Chaum-Fiat-Naor. Aber es verwendet das "Two-Points-on-a-line"-Prinzip wie Brands. Die verwendete Signatur ist nicht wie oben beschrieben die blinde RSA-Signatur, sondern eine Variante, die als zufällige blinde RSA-Signatur bezeichnet wird. Die gewöhnliche blinde RSA-Regelung hat den Nachteil, dass die Bank absolut keine Ahnung hat, was sie unterzeichnet. Wie bereits erwähnt, ist dies kein Problem im Cut-and-Choose-Fall. Aber in diesem Fall kann es einem Zahler die Möglichkeit geben, den Mechanismus zur Identifizierung mehrerer Spender zu umgehen. Die randomisierte Version vermeidet dieses Problem, indem sowohl Alice als auch die Bank Zufallsdaten in die Nachricht einbringen. Die Bank weiß immer noch nicht, was sie unterschreibt, aber sie weiß, dass die Daten nicht böswillig ausgewählt wurden.
Der Rest des Protokolls ähnelt konzeptionell dem Schema von Brands. Die von der Bank zu unterzeichnende Botschaft enthält neben den Zufallsdaten auch den Schatten einer Linie, deren Neigung und Ausschnitt die Identität von Alice erkennen lassen. Während der Zahlung zeigt Alice einen Punkt auf dieser Linie an. Wenn sie dies zweimal macht, kann die Bank sie identifizieren.
Obwohl Ferguson's Schema die Cut-and-Choose-Technik vermeidet, ist es die komplizierteste der drei Techniken (hauptsächlich aufgrund der randomisierten blinden RSA-Signatur). Außerdem kann es nicht über elliptische Kurven implementiert werden, da es RSA-basiert ist.
__________
8 Zur Erleichterung der Darstellung geben wir eine vereinfachte Darstellung des Markenprotokolls.
Weiter mit 4. Optionale Merkmale ...