Worum geht es in dieser Aktivität?

In den letzten Jahren hat der Umfang des Handels über Computernetze stark zugenommen und es ist wichtig einen sicheren Austausch von elektronischen Zahlungen, vertraulichen Transaktionen und rechtsverbindlichen Dokumenten zu garantieren. Beim Thema Kryptographie geht es darum, auf sichere und private Weise zu kommunizieren. Vor einigen Jahrzehnten entdeckten InformatikerInnen die kontraintuitive Eigenschaft, dass durch Verfahren eine Geheimhaltung gewährleistet werden kann, die sicherstellt, dass bestimmte Informationen öffentlich zugänglich gemacht werden können. Das Ergebnis ist das sogenannte „Public-Key-Kryptosystem“ (siehe Aktivität 19), das heute weit verbreitet als der sicherste Weg zum Informationsaustausch verwendet wird. Beispielsweise hast du möglicherweise Einstellungen wie SSL (Secure Sockets Layer) oder TLS (Transport Layer Security) in deinem Webbrowser gesehen. Diese Systeme basieren auf öffentlichen Schlüsselsystemen, mit denen dein Webbrowser eine sichere Verbindung zu einer Website wie einer Bank aufbauen kann, selbst wenn jemand alle gesendeten Daten abhört.

Bei der Kryptographie geht es nicht nur darum, die Dinge geheim zu halten, sondern um Informationsaustausch zu kontrollieren, d.h. einschränken, was andere über dich herausfinden können und um Vertrauen zwischen geografisch getrennten Personen herzustellen. Formale Regeln oder „Protokolle“ für kryptographische Transaktionen wurden entwickelt, um solche scheinbar unmöglichen Dinge, wie fälschungssichere digitale Signaturen, zu ermöglichen und anderen zu sagen, dass man das ‚Geheimnis’ besitzt (etwa ein Passwort) ohne es tatsächlich enthüllen zu müssen. Ein Münzwurf per Telefon ist ein einfaches, aber analoges Problem, das auf den ersten Blick unmöglich erscheint.

In einer realen Situation würden Alicia und Benito selbst keine Schaltkreise entwerfen, sondern sich ein Computerprogramm anschaffen, das die Arbeit intern erledigt. Wahrscheinlich würde sich keiner für die Innereien der Software interessieren. Aber beide möchten sich darauf verlassen können, dass kein anderer in der Lage ist, das Ergebnis der Vorgangs zu beeinflussen, egal wie gute Computerkenntnisse er oder sie hat und wie intensiv es versucht wird.

Im Prinzip müssten alle Streitigkeiten durch einen neutralen Richter gelöst werden. Der Richter sollte den Schaltkreis, Alicias ursprüngliche Binärzahl, die Ausgabe, die sie ursprünglich Benito schickte, und die Vermutung erhalten, die Benito im Gegenzug geschickt hat. Sobald der Austausch abgeschlossen ist, handelt es sich um öffentliche Informationen, sodass beide Teilnehmer zustimmen müssen, dass dies dem Ergebnis zugrunde liegt. Der Richter wird in der Lage sein, Alicias ursprüngliche Zahl in dem Schaltkreis einzugeben und zu überprüfen, ob die Ausgabe wie erwartet ist. Dadurch kann gezeigt werden, ob die Entscheidung fair getroffen wurde. Es erübrigt sich zu erwähnen, dass es unwahrscheinlich ist, dass ein Streit entsteht, da es ein klares Vorgehen gibt um zu überprüfen, dass die Regeln befolgt wurden. Vergleiche das mit der Situation, in der Alicia eine Münze wirft und Benito Kopf oder Zahl sagt - kein Richter würde diesen Fall annehmen!

Ein Schaltkreis, der so klein ist wie der gezeigte, wäre in der Praxis nicht sehr nützlich, da es leicht ist einen Tisch zu benutzen und darauf zu schummeln. Die Verwendung von zweiunddreißig Binärziffern in der Eingabe würde einen besseren Schutz bieten. Aber auch das garantiert nicht, dass es schwer ist zu schummeln - das hängt von dem jeweiligen Schaltkreis ab. Andere Methoden könnten verwendet werden, wie die in Aktivität 15 („Touristenstadt“) eingeführte Einwegfunktion. Die in der Praxis verwendeten Methoden hängen häufig vom Faktorisieren großer Zahlen ab, von dem bekannt ist, dass es ein schweres Problem ist (obwohl, wie wir am Ende der nächsten Aktivität erfahren werden, es nicht NP-vollständig ist). Es ist leicht zu überprüfen, ob eine Zahl ein Faktor einer anderen ist, aber das Finden der Faktoren einer großen Zahl ist sehr zeitaufwendig. Dies macht es für Alicia und Benito (und den Richter) komplizierter sich von Hand durchzuarbeiten, obwohl dies, wie oben erwähnt, in der Praxis durch handelsübliche Software gemacht wird.

Digitale Signaturen basieren auf ähnlicher Grundlage. Indem Alicia die Ausgabe des Schaltkreises für den bestimmten geheimen Input, den sie gewählt hat, öffentlich macht, ist sie effektiv in der Lage zu beweisen, dass sie diejenige ist, welche die Ausgabe erzeugt hat, denn mit einer korrekten Einwegfunktion kann niemand anderes mit einer Eingabe kommen, die funktioniert. Niemand kann sich als Alicia ausgeben! Um eine gültige digitale Signatur zu erstellen ist ein komplexeres Protokoll erforderlich, das sicherstellt, dass Alicia eine bestimmte Nachricht signieren kann und, dass andere überprüfen können, ob Alicia die Unterzeichnerin ist, selbst wenn sie dies nicht behauptet. Das Prinzip ist das gleiche.

Eine andere Anwendung ist das Pokern über das Telefon in einer Umgebung, in der es keinen Schiedsrichter gibt, der die Karten austeilt und beide Hände der Spielenden aufzeichnet. Alles muss von den Spielenden selbst ausgeführt werden, wobei im Streitfall ein Schiedsrichter am Ende des Spiels hinzugezogen werden muss. Ähnliche Situationen ergeben sich tatsächlich bei Vertragsverhandlungen. Offensichtlich müssen SpielerInnen ihre Karten während des Spiels geheim halten. Aber sie müssen ehrlich sein - sie dürfen nicht behaupten ein Ass zu haben, es sei denn, sie haben tatsächlich ein Ass! Dies kann überprüft werden, indem man wartet, bis das Spiel vorbei ist und dann jedem Spielenden erlaubt, die ursprünglichen Karten der anderen MitspielerInnen und die Abfolge der Züge zu überprüfen. Ein anderes Problem ist es, wie man die Karten austeilen kann, obwohl man die Hände jedes Spielenden bis nach dem Spiel versteckt hält. Überraschenderweise ist es möglich, dies unter Verwendung eines kryptographischen Protokolls zu erreichen, das dem Münzwurf nicht unähnlich ist.

Kryptographische Protokolle sind bei elektronischen Transaktionen extrem wichtig, sei es um den Besitzer einer Debitkarte zu identifizieren, die Verwendung eines Mobiltelefons für einen Anruf zu autorisieren oder den Absender einer E-Mail zu authentifizieren. Die Fähigkeit, diese Dinge zuverlässig zu tun, ist entscheidend für den Erfolg des elektronischen Handels.

Weiterführende Literatur

Harels Buch Algorithmics behandelt digitale Signaturen und zugehörige kryptographische Protokolle. Es beschreibt auch, wie man Poker über das Telefon spielt; eine Idee, die erstmals 1981 in einem Kapitel namens „Mental Poker“ in dem Buch The Mathematical Gardener erwähnt wurde (herausgegeben von D.A. Klarner). Cryptography and Data Security von Dorothy Denning ist ein exzellenter Artikel über Kryptographie. Dewdneys Buch Turing Omnibus enthält einen Abschnitt über Boolesche Logik, der die Bausteine beschreibt, die für die Schaltkreise in dieser Aktivität verwendet werden.