Skip to content

Kryptographie: Digitale Gutscheine (nicht nur) vom Weihnachtsmann

Kurzfristige Planänderung: Eigentlich wollte ich diesen Text "zwischen den Jahren" veröffentlichen und heute das Thema "WLAN-Sicherheit" beenden. Aber da nächste Woche sowieso kaum jemand arbeitet habe ich mich entschlossen, diese "Weihnachtsausgabe" schon vor Weihnachten zu veröffentlichen. Der nächste reguläre Text, mit dem dann wirklich das Thema "WLAN-Sicherheit" abgeschlossen wird, erscheint am 4. Januar.

Heute geht es um etwas, was ich schon während des Studiums sehr interessant fand: Blinde Signaturen. Der Jahreszeit angepasst in ein weihnachtliches Gewand gehüllt, denn blinde Signaturen kann man z.B. verwenden, um digitale Gutscheine auszugeben. Und genau das lasse ich jetzt den Weihnachtsmann tun...

Wie der Weihnachtsmann digitale Gutscheine einführte...

Natürlich benutzt auch der Weihnachtsmann inzwischen Computer. Als es einmal Probleme mit der Spielzeugmaschine gab und absehbar war, dass unmöglich genug Geschenke produziert werden konnten, hatte der für den IT-Bereich zuständige Elf einen Vorschlag: Es sollten digitale Gutscheine verschenkt werden, die die Kinder dann anschließend im lokalen Spielzeuggeschäft einlösen können.

Diese Gutscheine sollten eine Reihe von Forderungen erfüllen (siehe [1]):

  • Ihre Echtheit muss überprüfbar sein.
    Dies ist bei digitalen Gutscheinen kein Problem: Der Weihnachtsmann signiert sie und gibt natürlich nur echte Gutscheine aus.
  • Sie müssen fälschungssicher sein.
    Bei digitalen Gutscheinen bedeutet dies insbesondere, dass sie nicht mehrmals eingelöst werden können, da sich ein Kopieren nicht verhindern lässt. Diese Forderung ist schon nicht mehr so einfach zu erfüllen. Jeder Versuch, einen bereits eingelösten Gutschein erneut einzulösen, muss erkannt werden. Der Händler muss also jeden vorgelegten Gutschein vom Weihnachtsmann überprüfen lassen, bevor er ihn akzeptiert.
  • Aus Datenschutzgründen sollen sie anonym sein.
    Das bedeutet: Der Händler kennt zwar den Kunden, beim Einreichen des Gutscheins beim Weihnachtsmann kann dieser aber nur erkennen, dass der Gutschein von ihm stammt und vom Händler eingereicht wurde. Wer der Kunde ist, ist nicht zu erkennen.

Ein Protokoll, das diese Forderungen erfüllt, lässt sich anschaulich folgendermaßen darstellen:

  • Wird ein Blatt Papier in einen innen mit Kohlepapier versehenen Briefumschlag gesteckt und der Umschlag dann mit einer Markierung versehen, so wird der Abdruck dieser Markierung auf das Papier übertragen.
  • Nun wird angenommen, dass der Weihnachtsmann eine spezielle Markierung (zum Beispiel ein Siegel) besitzt, welche den garantierten Wert von beispielsweise 25 Euro hat: Der Weihnachtsmann zahlt für jedes Blatt Papier mit der Markierung 25 Euro aus.
  • Helfer stecken nun die Gutscheine (d.h. ein Blatt Papier) in solche Umschläge und bringen sie zum Weihnachtsmann. Der versieht die Umschläge auf der Außenseite mit der Markierung. Zur Bescherung werden diese Umschläge dann als Geschenk verteilt.
  • Der Beschenkte entnimmt den Gutschein, geht nach Weihnachten in ein Geschäft, holt sich sein Geschenk und "bezahlt" mit dem Gutschein. Die Geschäfte überprüfen die Markierung auf dem Gutschein, bevor sie ihn als Zahlungsmittel akzeptieren.
    Wenn der Weihnachtsmann die Gutscheine von den Geschäften zur Gutschrift vorgelegt bekommt, weiß er, dass die Gutscheine sich in von ihm markierten Umschlägen befanden. Da er aber nicht weiß, welcher Gutschein sich in welchem Umschlag befand, weiß er auch nicht, welches Kind in welchem Geschäft war.

Abbildung1 zeigt das Vorgehen:

Blinde Signatur am Beispiel eines Umschlags
Abb. 1: Blinde Signatur am Beispiel eines Umschlags

Die Grundidee dieses Verfahrens wird als blinde Signatur bezeichnet: Jemand signiert etwas, ohne es dabei zu sehen. Er kann später erkennen, dass er das, was er zurückerhält, selber signiert hat. Er weiß aber nicht, wie es bei der Signatur ausgesehen hat.

Realisierung

Für das Protokoll wird ein Signatursystem mit folgenden Eigenschaften verwendet:
Nachrichten können vom Weihnachtsmann signiert und diese Signatur kann von allen anderen Teilnehmern getestet werden. Es existieren eine Signierfunktion sign und eine Testfunktion test, für die gilt

1.	test( sign(a) ) = a = sign( test(a) )
2.	sign( a * b ) = sign( a ) * sign( b).

Die Lösung mit einer Digitalen Signatur funktioniert analog dem oben beschriebenen Verfahren mit Umschlägen:

  • Jeder Helfer wählt eine zufällige Zahl und bildet daraus eine "spezielle Zahl" n. Diese Zahl entspricht dem Blatt Papier im Beispiel.
  • Er wählt eine zufällige Zahl r, entsprechend einem Umschlag.
  • Dann wird
    test(r) * n
    berechnet, was dem Einstecken des Papiers in den Umschlag entspricht.
  • Das Ergebnis wird dem Weihnachtsmann übermittelt, der eine signierte Kopie zurückschickt:
    sign( test(r) * n )
    Dies entspricht dem markierten Briefumschlag.
  • Diese Zahl kann als
    sign( test(r) ) * sign(n)
    betrachtet und r durch Multiplikation mit seiner multiplikativen Inversen entfernt werden. Man erhält den signierten Gutschein
    sign(n)
    (entsprechend dem Entfernen des Briefumschlags).
    Die Korrektheit der Signatur kann durch Anwendung des öffentlichen Schlüssels test des Weihnachtsmanns überprüft werden, denn wenn alles OK ist gilt
    test( sign(n) ) = n
  • Im Geschäft kann geprüft werden, ob
    test( sign(n) )
    (also n) eine "spezielle Zahl" und damit ein gültiger Gutschein ist.
    Um die mehrfache Einlösung eines Gutscheins zu verhindern, führt der Weihnachtsmann eine Liste bereits eingelöster Gutscheine. Das Geschäft fragt beim Weihnachtsmann nach, ob der Gutschein eingelöst wird und akzeptiert ihn nur bei einer positiven Antwort.

Das Verfahren der blinden Signatur wurde 1982 [2] von David Chaum vorgestellt, der daraus das "digitale Geld" ecash entwickelt hat. Eine ziemlich pfiffige Lösung, die sich leider nicht durchgesetzt hat. Das von Chaum für die Verbreitung von ecash gegründete Unternehmen DigiCash ging Pleite, bevor ecash sich in den USA durchsetzen konnte. In Europa gab es bereits vielversprechende Erfolge.

Literaturverweise

  • [1] David Chaum: "Privacy Protected Payments - Unconditional Payer and/or Payee Untraceability";
    SMART CARD 2000: The Future of IC-Cards; Proceedings of the IFIP WG 11.6 International Conference; Laxenburg (Austria), 19.-20.10.1987, North-Holland, Amsterdam 1989, 69-93.
  • [2] David Chaum: "Blind signatures for untraceable payments";
    Advances in Cryptology - Crypto '82; Springer, Heidelberg 1983; 199-203. (PDF)

In der nächsten Woche gibt es keinen Grundlagentext. In der ersten Januarwoche, konkret am 4.1.2018, gibt es die bereits in der vorigen Woche angekündigte Abschlussfolge zur WLAN-Sicherheit.

Ich wünsche Ihnen allen ein frohes Fest, einen guten Rutsch ins neue Jahr und ein erfolgreiches 2018!

Carsten Eilers

>
        </div>
                
        <footer class= Kategorien: Grundlagen

Trackbacks

Keine Trackbacks