Wie die entschlüsselte Kryptographie hilft bei Lotto und Glücksspiel Teil 1

Warum gibt es so wenige Weise, aber Dummköpfe im Überfluss?
Weil sie Zahlen wollen, sind sie so zahllos.
Augusta Lovelace

Offensichtlich … In den düsteren Spionagezeiten des Kalten Krieges sammelten Undercover-Agenten streng geheime Informationen, verschlüsselten ihre Erkenntnisse mit streng geheimen Codes und schmuggelten dann die Botschaft auf Mikrofilm über geheime Briefkästen an ihre Regierungen. Die Geheimhaltung der Erkenntnisse, der Verschlüsselungstechnik und der codierten Botschaften war für diese supergeheimen Spione von größter Bedeutung.

Überraschung … Heute können Spione ihre Verschlüsselungsmethoden der ganzen Welt mitteilen und ihre streng geheimen, verschlüsselten Nachrichten in Zeitungen und im Internet veröffentlichen. Paradoxerweise ist dieses öffentliche Verschlüsselungsprojekt, bei dem jeder Zugang zum Verschlüsselungsverfahren und zu den verschlüsselten Nachrichten hat, sogar sicherer als die romantische Methode von Agent 007, attraktiven Spioninnen Mikrofiches mit einen Zungenkuss zu übergeben. Vielleicht ist sie für viele sogar genauso verführerisch.
Nichts für ungut, James.

Spione und unser Universum haben eines gemeinsam – beide behalten Geheimnisse für sich, die uns verborgen bleiben. Zu den köstlichsten Freuden des geistigen Lebens gehören Mysterien und Geheimnisse. Wenn wir eine verschlüsselte Botschaft betrachten, wissen wir, dass sie ein Geheimnis enthält, das wir lesen könnten, wenn wir nur den Schlüssel dafür hätten. Ähnlich ist es beim Studium ungelöster mathematischer Fragen, denn dabei erleben wir, dass das Universum selbst Geheimnisse bewahrt, die wir vielleicht enthüllen könnten, wenn wir sie nur aus der richtigen Perspektive betrachteten.

Der Zauber, der Geheimnisse umgibt, hat damit zu tun, dass wir vom ganzen Bild nur einen kleinen Ausschnitt kennen. Verlockende Bruchstücke einer unvollständigen Enthüllung scheuchen uns durch einen Wald tiefer, dunkler Geheimnisse. Jedes Fragment und jedes bisschen Information gibt uns einen Hinweis auf die Wahrheit, der wir auf der Spur sind. In manchen Fällen können wir messen, wie nah wir dieser Wahrheit gekommen sind; in anderen Fällen können wir nicht einmal raten, ob wir der ganzen Wahrheit schon bis auf einen Zentimeter nahegekommen sind oder ob kein Mensch sie je erfahren wird.

Bei unserer Erforschung von bewahrten und offenbarten Geheimnissen konzentrieren wir uns zunächst auf die Welt der Spionage und aufs Internet, wo Geheimnisse routinemäßig bewahrt und mit Hilfe ungewöhnlicher Geheimcodes übermittelt werden – Geheimcodes nämlich, die veröffentlicht werden.

Geheimnisse verschicken
Wenn wir an Geheimnisse und an den Umgang mit ihnen denken, kommen wir sehr schnell auf Codes zu sprechen. Geheimcodes werden nicht nur von Spionen verwendet. In Wirklichkeit benutzen wir Nichtspione allesamt täglich geheime Codes, ohne es zu bemerken. Das Codierungsprojekt, das wir jetzt erforschen wollen, gehört zu den Methoden, die in der Computerpraxis angewandt werden, wenn wir online Geld überweisen, die Datenübertragungstechnik ATM (Asynchronous Transfer Mode) anwenden, über das Internet mit Aktien handeln oder unsere Kreditkartennummer in ein Formular auf einer Website eintippen. Der Schlüssel zu dieser modernen Form, heikle Informationen auszutauschen, hat mit Zahlen zu tun. Wer hätte gedacht, dass der einfache Prozess des Multiplizierens zweier Zahlen dem Internethandel und der vertraulichen Übermittlung geheimer Informationen zugrunde liegt?

Solange der Mensch Feinde gehabt hat, hat es auch Geheim-codes gegeben. Julius Cäsar, der eine Menge Feinde hatte (zu denen auch Brutus gehörte), erfand ein eigenes Codierungsschema, das heute unter dem Begriff Cäsar-Verschlüsselung (oder Verschiebechiffre) bekannt ist. Wer sich mit solchen Verschlüsselungsspielen in Zeitungsbeilagen beschäftigt hat, kennt das Schema – ein Buchstabe wird durch einen anderen ersetzt. So ließe sich beispielsweise HELLO als QLAAJ verschlüsseln (wobei hier das H durch ein Q ersetzt wird, das E durch ein L, das L durch ein A und das O durch ein J). Die Cäsar-Verschlüsselung hat allerdings drei erhebliche Nachteile. Ihr erster Nachteil besteht darin, dass sie – wie Cäsar selbst entdecken musste – indirekt zu unserer Ermordung führen könnte. Die beiden anderen Probleme sind nicht unbedingt lebensbedrohlich, aber dennoch ernst zu nehmen. Denn erstens lässt sich der Code sehr leicht knacken, und zweitens wäre der Code vollständig wertlos, wenn das Codebuch in die falschen Hände geriete.

Die Tatsache, dass der Code leicht zu knacken ist, wird täglich aufs Neue von Zeitungslesern demonstriert, die auf den Knobelseiten verschlüsselte Botschaften aufdröseln. Wer den Code knackt, hat in Wirklichkeit auch das Codebuch gestohlen. Wäre das Codebuch Mark Anton in die Hände gefallen, wäre er mit Sicherheit in der Lage gewesen, jede beliebige codierte Botschaft zu entschlüsseln. (Sähe er ein Q, ersetzte er es durch ein H und so weiter.) Die Leichtigkeit, mit der der Code geknackt werden kann, ruft nach einem komplizierteren Codierungsschema.

Allerdings scheint es keine Lösung für das Problem eines gestohlenen Codebuches zu geben – wenn jemand das Verfahren kennt, eine Nachricht zu verschlüsseln, scheint er offensichtlich auch die umgekehrte Prozedur zu beherrschen, die es ihm erlaubt, eine verschlüsselte Botschaft zu decodieren.

Überraschung. Es gibt ein Codierungsschema, das unserer Intuition zuwiderläuft und wobei selbst mein genaues Wissen um die Verschlüsselung der Nachricht es mir nicht erlaubt, sie zu entschlüsseln. Nur der ausdrückliche Empfänger, der eine zusätzliche Information besitzt, kann die Nachricht decodieren. Eigentlich könnten wir also den Verschlüsselungsprozess vollständig veröffentlichen – das heißt, ihn der ganzen Welt kundtun ohne deshalb seine Wirksamkeit zu beeinträchtigen. Wie ist ein solch paradox klingendes Codierungsschema möglich? Die Antwort ist so schwer oder so leicht, wie eine Zahl in Faktoren zu zerlegen.

Im Grunde geht es darum: Wie ist es möglich, dass das Wissen um die Verschlüsselungsmethode von Botschaften nicht automatisch auch den Entschlüsselungsprozess preisgibt? Die Antwort auf diese grundlegende Frage ist nicht nur der Schlüssel zum Verständnis des Funktionierens eines solchen der Intuition zuwiderlaufenden Codierungsschemas, sondern auch der Schlüssel zur Freigabe bestimmter Details des Programms an sich.

Wir fangen, wie immer, ganz einfach an. Angenommen, ein Mann namens Simon gibt bekannt, dass er an die Zahl 15 denkt. Bis jetzt würden wir diese Nachricht noch nicht als sensationell einstufen. Sollte der einfältige Simon dann offenbaren, dass die Zahl 15 als Produkt zweier kleinerer Zahlen betrachtet werden kann, würden wir auch jetzt noch nicht CNN alarmieren. Jeder weiß, dass 15 = 3 X 5. Worum geht es also? Nun, nehmen wir an, Simon sagte, er denke jetzt an eine größere Zahl, die ebenfalls das Produkt zweier kleinerer Zahlen ist, und dass diese neue Zahl 33 laute. Auch in diesem Fall können wir leicht feststellen, dass 33 = 3 X 11. Betrachten wir nun die beiden kleineren Zahlen, nämlich die Faktoren der ersten Zahl, als Simons Geheimnis. Bei 15 und 33 ist das natürlich noch kein großes Geheimnis, da wir ziemlich schnell herausfinden, dass 15 = 3X5 und 33 = 3 X 11.

Nehmen wir weiterhin an, dass Simon mittlerweile an größere Zahlen denkt, die jeweils das Produkt zweier kleinerer Zahlen sind. Wenn Simon also 247 sagt, dann lassen sich hier die beiden Faktoren nicht so schnell finden wie bei den Beispielen zuvor. Mit etwas Anstrengung würden wir entdecken, dass 247 = 13 X 19.WennSimon 1219 sagt, müssten wir noch angestrengter nachdenken, um zu erkennen, dass 1219 = 23 X 53. Und sollte er etwa 1 308 ii9verkiinden, wären wir gezwungen, unsere Taschenrechner herauszuholen, um schließlich herauszufinden, dass 1 308 119 = 661 X 1979. Aber selbst die meisten normalen Taschenrechner wären überfordert, wenn Simon 17158904089 ansagte, wenngleich ein Computer es schaffen und feststellen würde, dass 17158904089 = 104729 X 163 841.

Aber wenn Simon folgende Zahl ansagte:
1328471832150192341410877618237418234A817234187431832576 123818234718237481237481237648127351726354726345837457812 37617246512349123457712834576187236451872345618273456712 63498172347612374619278364591278345647382736465728371287
36451982735691284756918237417263549182734198273498127365 49128734512736451827346591823741991623581641823749712653 48172634598716239874561982375691827345618273648237187234 812634731,
würde selbst der schnellste Computer der Welt länger brauchen, als das Universum alt ist, um die beiden Faktoren mit Hilfe einer heute bekannten Methode zu finden.

Das Szenario veranschaulicht eine interessante Kluft zwischen theoretischem und praktischem Wissen. Wir haben eine Zahl- zum Beispiel diese hier mit 401 Ziffern -, und wir werden davon in Kenntnis gesetzt, dass Simon weiß, sie sei das Produkt zweier kleinerer Zahlen. Theoretisch könnten wir diese Faktoren durch Versuch und Irrtum herausfinden, aber das Verfahren würde eine unglaublich lange Zeit in Anspruch nehmen. Vom praktischen Gesichtspunkt aus betrachtet, bleibt die eigentliche Zerlegung der Zahl in Faktoren unbekannt, obwohl wir wissen, dass Simons Zahl zerlegt werden kann.

Public-Key-Codes
Diese einfache und womöglich trivial klingende Beobachtung ist der Schlüssel zur Public-Key-Kryptographie. Nehmen wir an, Simon möchte die Welt wissen lassen, er sei bereit, verschlüsselte Botschaften zu empfangen. Er gibt eine riesige Zahl wie die oben aufgeführte 401-stellige Zahl bekannt, die kein Mensch und kein Computer in ihre Faktoren zerlegen können. Obendrein veröffentlicht er seine arithmetischen Anweisungen, wie man diese Zahl benutzen muss, um eine Nachricht in eine verschlüsselte Nachricht zu verwandeln. Um eine an Simon geschickte verschlüsselte Botschaft zu entschlüsseln, bedarf es, wie wir später noch sehen werden, einiger arithmetischer Schritte, für die die geheimen Faktoren seiner großen, öffentlich bekannt gegebenen Zahl unentbehrlich sind. Da niemand sonst außer Simon selbst diese beiden Faktoren kennt, kann niemand die an Simon geschickten verschlüsselten Nachrichten entschlüsseln außer Simon persönlich.

Deshalb müssen die verschlüsselten Nachrichten nicht geheim gehalten werden – sie können in Zeitungen oder im Internet veröffentlicht werden, denn nur Simon wird in der Lage sein, aus dem Zahlensalat etwas Sinnvolles herauszulesen.

Wie sehen also die Verfahren zur Verschlüsselung und Entschlüsselung aus, und was trägt das Wissen um die Faktoren zur Entschlüsselung bei? Nachdem wir eine Übersicht gegeben haben, werden wir ein vollständiges Beispiel mit kleinen Zahlen anbieten, sodass Sie selbst erkennen können, wie es funktioniert.

Sagen wir, wir wollen die Nachricht HELLO an Simon schicken. Wir beginnen damit, diese Botschaft in Zahlen umzuwandeln. In unserem System wird jeder Buchstabe in eine aus zwei Ziffern bestehende Zahl umgewandelt, die seiner Stellung im Alphabet entspricht – das heißt A ist 01, B ist 02 und so weiter bis Z = 26. Demnach wird unsere Nachricht HELLO in die Zahl 0805121216 umgewandelt. Beachten Sie, dass wir die Nullen beibehalten. Wir hängen einfach alle zweistelligen Zahlen aneinander: In diesem Fall die 08, die 05 die 12 und so weiter. Als Nächstes erheben wir diese Zahl in eine ziemlich hohe Potenz (die von Simon öffentlich bekannt gegeben wird). Schließlich nehmen wir diese riesige Zahl und teilen sie durch die von Simon öffentlich angesagte 401-stellige Zahl, wobei ein Rest zurückbleibt. Und dieser Rest ist die verschlüsselte Botschaft, die wir an Simon schicken. In Wirklichkeit erledigen natürlich Computer die ganzen Berechnungen für uns. Simon erhält die verschlüsselte Nachricht (die eigentlich nur eine Zahl ist), erhebt sie in eine geheim gehaltene Potenz, wobei die beiden geheimen Faktoren ins Spiel kommen, und findet dann den Rest, wenn er diese monströse Zahl durch seine 401-stellige Zahl teilt. Überraschenderweise lautet die Antwort 0805121216, die Simon ganz einfach in Buchstaben umwandeln kann, die unser ursprüngliches HELLO bedeuten.

Zusammengefasst lässt sich sagen: Um eine Zahl zu verschlüsseln, erheben wir diese Zahl in eine öffentlich bekannt gemachte Potenz, und errechnen dann den Rest, nachdem wir die potenzierte Zahl durch eine zweite öffentlich bekannt gemachte Zahl dividieren. Der gefundene Rest ist die codierte Zahl. Um diese codierte Zahl zu entschlüsseln, erhebt Simon sie in eine andere Potenz (die nur er allein kennt) und berechnet erneut den Rest, nachdem er sie wieder durch eine öffentlich bekannte Zahl teilt. Dieser Rest wird erstaunlicherweise die ursprüngliche Zahl sein, die die Botschaft entschlüsselt.

Jetzt wollen wir ein praktisches Beispiel mit kleinen Zahlen geben, um zu veranschaulichen, wie beim Verschlüsselungsschema die Faktoren der großen Zahl ins Spiel kommen. Mancher Leser gibt sich vielleicht mit dieser gerade vorgestellten Übersicht zufrieden. Diesen klugen Lesern raten wir, den folgenden Abschnitt zu überspringen. Andere Leser wiederum finden vielleicht Vergnügen daran, dem numerischen Prozess bei der Arbeit zuzusehen. Für diese unerschrockenen Mitmenschen ist der folgende Abschnitt gedacht.

Wie die entschlüsselte Kryptographie hilft bei Lotto und Glücksspiel Teil 2