Nehmen wir an, Sie wollen etwas im Versandhandel kaufen und mit Kreditkarte bezahlen. Wenn Sie deren Nummer per Telephon oder Internet durchgeben, könnte jemand sie abhören beziehungsweise mitlesen und mißbrauchen. Noch kritischer ist die Übertragung der persönlichen Geheimzahl (PIN), die zur Scheckkarte gehört. Deshalb verwenden vor allem die Banken Verschlüsselungsverfahren; der Datenverkehr bleibt vertraulich, solange niemand den Code knackt. Aber wie sich herausgestellt hat, reicht dieser Schutz im Internet nicht aus. Man will die Sicherheit haben, daß niemand – auch nicht der Hersteller des Verschlüsselungsverfahrens – an die Informationen kommen kann.

Eine Lösung des Problems läuft darauf hinaus, die empfindsame Nachricht gar nicht erst zu verschicken – auch nicht verschlüsselt. Trotzdem kann der Absender dem Empfänger die entscheidende Gewißheit vermitteln, daß er derjenige ist, der er zu sein behauptet, also zum Beispiel der Bank beweisen, daß er die Geheimzahl kennt, ohne sie preiszugeben. Diese Authentifizierung funktioniert mit den sogenannten Zero-Knowledge-Protokollen.

Das Prinzip läßt sich anhand einer Aufgabe erklären, die eine Verschärfung des notorischen Vierfarbenproblems ist: Auf einer Landkarte sind die Staaten mit nur drei Farben so zu kennzeichnen, daß aneinandergrenzende stets verschiedene Farben haben.

Wenn überhaupt eine solche 3-Färbung existiert, ist sie bei komplizierteren Karten nahezu unmöglich zu finden. Bei der Kontoeröffnung hat Ihnen eine Treuhandstelle eine korrekt gefärbte Karte als legitimierendes Geheimnis anvertraut. Die Bank kennt nur die ungefärbte Karte. Wie können Sie nun von zu Hause aus die Bank überzeugen, daß Sie im Besitz einer 3-Färbung sind, ohne die Färbung selbst zu übermitteln?

Nehmen wir zunächst ein vereinfachtes – unrealistisches – Verfahren. Die Bank hat Ihnen einen speziell versiegelten Computer in die Wohnung gestellt. In diesen geben Sie Ihre geheime Färbung ein. Dank der Konstruktion der Maschine können Sie sicher sein, daß sie die geheime Information nicht preisgibt; die Bank ihrerseits vertraut darauf, daß der Computer nur das richtige Programm ausführt und sonst nichts.

Die Bank – ebenfalls vertreten durch einen Computer – deutet nun auf ein Stück Grenze, und Ihr Computer meldet daraufhin die Farben der beiden angrenzenden Länder – aber nicht unbedingt die echten. Zuvor wendet er nach dem Zufallsprinzip eine Permutation auf das Farbschema an, bezeichnet also beispielsweise alle roten Länder als blau, alle zuvor blauen als rot und läßt die gelben gelb. Wenn die ursprüngliche 3-Färbung regelgerecht war, sind die beiden rückgemeldeten Farben verschieden.

Die Bank wiederholt nun diesen Vorgang für jedes Stück Grenze. Sind Sie nicht im Besitz einer 3-Färbung, wird die Bank über kurz oder lang auf zwei benachbarte Länder stoßen, deren Farben – ob permutiert oder nicht – gleich sind. Wenn das nicht geschieht, kann der Bankcomputer davon überzeugt sein, daß Sie die echte Färbung kennen (Bild); und weil Ihre Maschine zufällig unter den sechs möglichen Permutationen dreier Farben hin- und herschaltet, vermag die Bank – oder der Ganove, der die Datenleitung angezapft hat - Ihre ursprüngliche Färbung nicht zu ermitteln.

Wie kann man dessen so sicher sein? Stellen Sie sich vor, ein Einbrecher klemmt den Computer in Ihrer Wohnung ab und ersetzt ihn durch seinen eigenen, der auf jede Anfrage der Bank einfach zwei verschiedene, nach dem Zufallsprinzip ausgewählte Farben angibt. Dann ist die gefälschte Antwort nicht von der echten zu unterscheiden. Nicht einmal ein Inhaber des Geheimnisses könnte dem Betrüger auf die Schliche kommen; denn es gibt stets eine Permutation, welche die echten Farben an der abgefragten Grenze in die geratenen umwandelt. Es geht also wirklich null Wissen (zero knowledge) über die Leitung.

Gleichzeitig wird offensichtlich, daß das Verfahren in dieser Form nicht praktikabel ist. Der Computer in Ihrer Wohnung samt der Datenleitung zur Bank spielt die Rolle eines Notars. Ein gleicherweise verschwiegenes, absolut vertrauenswürdiges System ist mit Hardware-Mitteln nicht zu realisieren. Vielmehr muß der Computer die Information "die Farben sind verschieden" übermitteln und zugleich beweisen, daß er nicht manipuliert worden ist; aber aus beiden Informationen zusammen könnte man die gesamte Färbung rekonstruieren.

Der Ausweg aus diesem Dilemma liegt in einem pokerähnlichen Spiel. Sie als derjenige, der etwas zu beweisen hat (der prover), legen der überprüfenden Stelle (dem verifier) – in unserem Beispiel der Bank – zwei verdeckte Karten vor. Die Bank darf nur eine aufdecken, aber sie darf sich aussuchen, welche. Aufdecken der einen Karte liefert eine Auskunft der Art "zwei verschiedene Farben"; Aufdecken der anderen gibt der Bank Gelegenheit zu überprüfen, ob Sie gemogelt haben. Ein Betrüger kann stets eine glaubwürdige Karte hinlegen – aber nur eine von beiden; also hängt es vom Zufall ab, ob die Bank auf den Betrug hereinfällt, und die Chance dafür sinkt mit jeder Wiederholung der Prüfung.

In der Praxis verwendet man statt der Kartenfärbung ein anderes Problem: die Zerlegung einer großen Zahl n in zwei Primfaktoren p und q. Wenn n etwa 200 Dezimalstellen lang ist, kann kein bekanntes Verfahren solche Faktoren innerhalb der Zeit finden, die das Universum existiert (vergleiche "Faktorisierung großer Zahlen" von Johannes Buchmann, Spektrum der Wissenschaft, September 1996, Seite 80). Die Faktoren p und q sind also ebenso wie eine 3-Färbung als legitimierendes Geheimnis geeignet, selbst wenn n bekannt ist.

Den beiden verdeckten Karten entspricht in der Praxis ein sogenannter Kanal für Vergessenstransfer (oblivious transfer channel). Man kann mit zahlentheoretischen Mitteln ein Äquivalent eines Kanals konstruieren, bei dem der Empfänger nur eine (frei wählbare) Nachricht von zwei angebotenen zu lesen vermag (vergleiche "Sichere offene Datennetze" von Thomas Beth, Spektrum der Wissenschaft, Mai 1995, Seite 46). Dafür sind statt der üblichen vierstelligen Geheimzahl zwei hundertstellige Zahlen zu verwenden (Kasten auf dieser Seite). Es gibt praktischere Stategien, aber die sind komplizierter zu erklären.

Vor zwei Jahrhunderten hat Carl Friedrich Gauß (1777 bis 1855), einer der Begründer der Zahlentheorie, diese seine Geistesschöpfung als die "Königin der Mathematik" bezeichnet. Nun sind Königinnen zwar prachtvoll, haben aber sonst nicht viel zu sagen, und man kann Gaußens Satz mit Fug auch so verstehen: Noch vor 20 Jahren galt das Studium der ganzen Zahlen als reines Denken im Elfenbeinturm, schön, aber nutzlos. Heute aber drängen ihre Erkenntnisse mit Macht in die kommerzielle Praxis.

Digitale Signale sind als ganze Zahlen interpretierbar; darum sind Verfahren zur Manipulation digitaler Information wie etwa Codierung fast zwangsläufig Anwendungen der Zahlentheorie. Zero-Knowledge-Beweise und Vergessenstransfer sind nur zwei neuere Ideen, die aus ihren Tiefen gefördert wurden.

Inspiriert von diesen Ideen sandte mir Tom Sales aus Somerset (New Jersey) eine interessante Variante eines Kartenspiels namens Eleusis, das Martin Gardner im Juni 1959 und im Oktober 1970 im "Scientific American" vorgestellt hat: Ein Spieler setzt die Regeln, schweigt darüber, und die anderen haben sie herauszufinden, indem sie gesagt bekommen, ob ihre Spielzüge zulässig sind.

In einem dreieckigen Zimmer sitzt eine (deterministische) Maus; in jeder Ecke ist ein Sortiment farbiger Glühbirnen angebracht. Die Maus hat Angst vor den Lichtern und rennt von Ecke zu Ecke, indem sie gewissen Regeln folgt, etwa: "Wenn das Licht in meiner Ecke rot ist und das rechts von mir grün, laufe ich zur rechten Nachbarecke." Ein Spieler setzt die Regeln, und die anderen versuchen sie zu ermitteln, indem sie Lichter anschalten und beobachten, was die Maus tut. Alle Regeln beziehen sich auf die jeweils aktuelle Position der Maus.

Nun mache man die Maus unsichtbar. Dann ist es unmöglich, die Regeln herauszufinden; aber zu beliebigen Zeitpunkten kann ein Beobachter die Maus mit einem Blitzlicht sichtbar machen und sich so davon überzeugen, daß sie tatsächlich den Regeln folgt.

An die Stelle der zu übermittelnden Klartext-Nachricht tritt eine Folge von Lichtsignalen, die chiffrierte Nachricht ist die Bewegung der Maus, und die Regeln sind der Verschlüsselungsalgorithmus. Es ergibt sich ein interessantes System zur vertraulichen Kommunikation – mit einem Hauch von Wissenlosigkeit.

Literaturhinweise

- A Course in Number Theory and Cryptography. Von Neal Koblitz. Springer, New York 1994.

– Im abstrakten Gebiet. Kapitel 8 in: Mathematische Expeditionen. Von Ivars Peterson. Spektrum Akademischer Verlag, Heidelberg 1992.

Kasten: Ein Übertragungsprotokoll mit Vergessenstransfer

Sie und Ihre Bank kennen beide zwei Primzahlen p und q sowie deren Produkt n. Eine vertrauenswürdige, unabhängige Quelle liefert auf Anforderung beiden Parteien Folgen von Nullen und Einsen, aus denen sie alle Zufallszahlen konstruieren können, die das Protokoll verlangt. Wenn Sie die Bank davon überzeugen wollen, daß Sie p und q kennen, ohne diese Zahlen selbst zu enthüllen, ist folgendes Protokoll anzuwenden: 1. Die unabhängige Quelle erzeugt eine Zufallszahl x, behält sie für sich und sendet Ihnen und der Bank den Rest r, der beim Teilen von x² durch n bleibt (r=x² mod n). 2. Nach der Zahlentheorie hat r genau vier verschiedene Quadratwurzeln modulo n; das sind Zahlen, die man anstelle von x in obige Gleichung einsetzen kann. Eine davon ist x selbst, eine weitere n-x. Die beiden anderen sind eine Zahl y und n-y. Sie berechnen alle vier Wurzeln. Das ist leicht, wenn man p und q kennt; andernfalls ist es praktisch unmöglich. (Umgekehrt kann man aus der Kenntnis der vier Wurzeln p und q bestimmen.) 3. Sie wählen zufällig eine dieser vier Zahlen aus; nennen wir sie z. 4. Sie wählen eine Zufallszahl k und schicken der Bank die natürliche Zahl s=k² mod n. Dann berechnen Sie die zwei Zahlen a=k mod n und b=kz mod n. Schicken Sie a und b (aber nicht k) über den Kanal mit Vergessenstransfer an die Bank. 5. Die Bank kann genau eine dieser beiden Zahlen lesen. Sie überprüft, ob deren Quadrat mod n gleich s ist (wenn sie a gelesen hat), oder gleich rs (wenn sie b gelesen hat). Wenn Sie z nicht kennen, könnten Sie versuchen, die Bank zu täuschen, indem Sie zunächst irgendein b wählen, das dazu passende s ausrechnen und ihr statt k² mod n dieses s übermitteln. Der Täuschungsversuch fliegt auf, wenn die Bank in diesem Falle a statt b liest; denn zu einem gegebenen s beziehungsweise k² das passende a zu finden ist wieder praktisch unmöglich. Andererseits ist es auch ohne Kenntnis von z nicht schwer, der Bank ein passendes Paar aus s und a zu liefern. Wenn ein Betrüger also im voraus wüßte, welche der beiden Zahlen die Bank liest, könnte er ihr überzeugende Daten anbringen. Da er das aber nur raten kann, hat er in jedem Versuch eine Trefferwahrscheinlichkeit von lediglich 50 Prozent. 6. Diese Schritte werden T-mal wiederholt. Mit jeder Wiederholung halbiert sich die Chance eines Betrügers, den Test zu bestehen. Am Ende weiß die Bank mit der Wahrscheinlichkeit 1-2^-T (also beliebig nahe an der Gewißheit), daß Sie die Faktorisierung kennen. Beachten Sie, daß die Bank keine Nachrichten an Sie schicken muß. Das Protokoll ist also nicht interaktiv.


Aus: Spektrum der Wissenschaft 2 / 1997, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH