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

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

Mit den Zahlen spielen
Nehmen wir an, Simon macht öffentlich die Zahlen 7 und 33 bekannt und erklärt dabei, wie man sie benutzt, um eine Botschaft zu verschlüsseln. Um ihm eine verschlüsselte Nachricht zu schicken, sollen wir zunächst die Buchstaben in eine Zahl umwandeln, die Zahl in die siebte Potenz erheben, das Ergebnis durch 33 dividieren und so den Rest finden. Dieser Rest sei dann die verschlüsselte Botschaft, die wir ihm schicken sollen. Angenommen, wir wollen ihm beispielsweise die geheime Botschaft E senden:
1) Wir wandeln E in 05 um.
2) Wir erheben 5 in die siebente Potenz: 5/7 = 78 125
3) Wir teilen diese Zahl durch 33 und erhalten den Rest: 78 125 ÷ 33 = 2367 mit dem Rest 14.
4) Also ist 14 unsere verschlüsselte Nachricht.

Jetzt decodiert Simon die verschlüsselte Nachricht, indem er sie in die dritte Potenz erhebt, das Ergebnis durch 33 teilt, den Rest erhält und diese Zahl in einen Buchstaben zurückverwandelt. Aus Gründen, die unten erklärt werden, weiß Simon (und ausschließlich Simon), dass das Erheben in die dritte Potenz der Schlüssel zur Entzifferung ist. Wir wollen uns nun ansehen, wie Simon mit der verschlüsselten Botschaft 14 verfährt:
1) Er erhebt 14 in die dritte Potenz: 14/3 = 2744.
2) Er teilt diese Zahl durch 33 und findet den Rest: 2744 ÷ 33 = 83 mit dem Rest 5.
3) Er wandelt die Zahl 5 in E um.
4) Auf diese Weise hat Simon die geheime Botschaft entschlüsselt.

Versuchen Sie dieses Verschlüsseln und Entschlüsseln einmal selbst, indem Sie einen Taschenrechner benutzen. Fangen Sie mit einer beliebigen Zahl an, die kleiner als 33 ist. Wenn Sie nun jene Zahl in die siebente Potenz erheben, den Rest finden, nachdem Sie sie durch 33 geteilt haben, diesen Rest dann in die dritte Potenz erheben und den Rest finden, wenn Sie sie durch 33 geteilt haben, werden Sie entdecken, dass Sie wieder bei Ihrer Ausgangszahl angelangt sind. Unergründliche Magie? Ganz und gar nicht – nur wunderbare Mathematik.

Wie also gelangen die Faktoren von 33 in den Prozess? Zuerst stellen wir fest, dass 33 = 3 X 11 (und dass 3 und n nicht weiter in Faktoren zerlegt werden können – es sind Primzahlen). Als Nächstes multiplizieren wir den um i verringerten ersten Faktor mit dem um r verringerten zweiten Faktor und addieren 1:(3-1) X (11- 1) + 1 =21. Da dieses Ergebnis in Faktoren zerlegt werden kann (21=7X3), lässt sich einer dieser Faktoren, nämlich 7, als Verschlüsselungsmodus benutzen, während der andere Faktor, die 3, als Entschlüsselungsmodus eingesetzt wird. Dieses einfache Beispiel ist ein sehr spezieller Fall eines viel allgemeineren Verfahrens, das wesentlich größere Werte benötigt.

Im wirklichen Leben sind die Schritte im Verschlüsselungs- und Entschlüsselungsprozess mit Zahlen verknüpft, die Hunderte von Ziffern haben. Und auch die Botschaften sind normalerweise etwas länger als E oder HELLO. Die Größe der Zahlen, die Simon bekannt gibt – eine für den Verschlüsselungsmodus, eine andere zum Dividieren, um den Rest zu erhalten -, hängen von den jeweils aktuellen Fähigkeiten der Computer ab, Zahlen in Faktoren zu zerlegen. Computer haben endliche Fähigkeiten, und daher existeren zu jeder beliebigen Zeit Zahlen, die so groß sind, dass sie nie vom jeweils leistungsstärksten Computer geknackt werden können. Um einen wahrhaftig unknackbaren Code zu schaffen, benötigen wir lediglich zwei Primzahlen, die beide so groß sind, dass ihr Produkt bei weitem die Kapazität jedes Computers überschreitet, eine Zahl in ihre Faktoren zu zerlegen. Wie aber gelingt es Computern, diese unverschämt großen Zahlen zu multiplizieren, wenn sie das Ergebnis nicht in Faktoren zerlegen können? Die Antwort lautet, dass die Multiplikation oder das Erheben von Zahlen in riesige Potenzen sowie das Errechnen von Resten rechnerisch einfach ist, selbst wenn die Zahlen Hunderte oder lausende von Ziffern haben, während die Faktorzerlegung von Zahlen mit mehreren hundert Ziffern rechnerisch äußerst schwierig und – zwar nicht theoretisch, aber praktisch – unmöglich ist.

Wie viel ist Ihre Information wert?
Zwei wichtige Fragen, die ganz von selbst aufkommen, hängen eigentlich zusammen: Wie groß sollte Simons Zahl sein? Wie wertvoll ist die Information, die Simon erhält? Je wertvoller die Information ist, desto größer sollte die Zahl sein. Je kleiner die Zahl ist, umso leichter ist der Code zu knacken. So ist beispielsweise die mit der Zahl 33 verknüpfte Verschlüsselungsmethode sofort zu durchschauen, da jeder erkennen kann, dass 33 = 3 X 11. Mehr Zeit und Anstrengung bedarf jedoch das Knacken eines Codes, der mit der Zahl 17 158904089 verbunden ist. Hier müsste schon ein Computer eingesetzt werden, und die Information müsste dementsprechend wertvoll sein, damit es sich lohnt, die Zahl zu knacken. Wenn wir andererseits mit dieser elfstelligen Zahl Angelegenheiten der nationalen Sicherheit verschlüsselten, wäre der bescheidene Aufwand, der nötig wäre, um herauszufinden, dass 17 158904089 = 104729 X 163841, und damit den Code zu knacken, auf jeden Fall von enormem Wert für einen Staatsfeind. Deshalb benötigen wir für wichtige Informationen eine wesentlich größere Zahl, um die Sicherheit zu gewährleisten.

In unserem technologischen Zeitalter ist es von größter Bedeutung, den Wert von Informationen zu erforschen. Dement-sprechend ist der Wert von Public-Key-Verschlüsselungsprogrammen recht hoch. Wie wir im nächsten Kapitel herausfinden werden, betrachten Mathematiker eine Zahl wie 400000000 als winzigen Wert im Verhältnis zu allen anderen Zahlen. Es gibt jedoch ein recht einfaches Mittel, um den Wert für jeden, Mathematiker eingeschlossen, groß erscheinen zu lassen – indem man ein Dollarzeichen davorsetzt: $ 400000000. Vor rund zehn Jahren zahlte die Firma Security Dynamics vierhundert Millionen Dollar, um ein Verschlüsselungsunternehmen zu kaufen, das dieses Public-Key-Verfahren entwickelt hatte. Kein schlechter Fang für eine Handvoll Mathematiker, die ein paar, arithmetisch betrachtet, einfache Schritte überaus scharfsinnig gebündelt hatten.

Ist das Knacken wirklich so schwer‘?
Könnten wir Simons Zahl in Faktoren zerlegen, ließe sich sein Code knacken. Gelänge es uns, eine einfache Methode zur Faktorzerlegung zu finden, wäre der Code erledigt. Heute weiß niemand, ob eine handhabbare und schnelle Methode existiert, riesige Zahlen in Faktoren zu zerlegen. Aber es könnte durchaus ein schlaues Verfahren der Faktorzerlegung geben, das es noch der letzten Klapperkiste von Computer erlauben würde, unsere 401- stellige Zahl in wenigen Sekunden in Faktoren zu zerlegen. Sollte ein Hacker eine solche Methode finden, dann werden wir Verwüstungen von solchen Ausmaßen erleben, wie sie nur das Internet auslösen kann.
Gibt es vielleicht, aus einer leicht verschobenen Perspektive betrachtet, eine teuflisch raffinierte Methode, das Verschlüsselungsprogramm zu knacken, ohne die Zahlen zu zerlegen? Niemand kennt die Antwort auf diese äußerst wichtige Frage. Da wir die Antwort jedoch nicht kennen, bedeutet dies wieder einmal, dass wir den Code eben nicht knacken können. Bis wir also unseren augenblicklichen Stand der Unwissenheit nicht überwunden haben, bleibt dieses Verschlüsselungsverfahren geheim. Public-Key-Verschlüsselung ist ein herausragendes Beispiel für die Ausbeutung unserer Unwissenheit zu unserem eigenen Vorteil.

Die Geheimnisse des Universums
In den Schulen wird die Mathematik recht häufig auf langweilige und verzerrte Art und Weise dargestellt. Vielen Schülern wird der Eindruck vermittelt, die Mathematik sei in ihrer Gesamtheit erforscht, und alle mathematischen Fragen seien bereits beantwortet. Viele Menschen glauben, die Mathematik höre jenseits der schwindelnden Höhen der Differenzialrechnug auf. Aber obwohl es über die Differenzialrechnung hinaus einen beachtlichen Wissensschatz gibt, den sich die Mathematiker erarbeitet haben, bleibt in Wirklichkeit fast die gesamte Mathematik außerhalb unserer Reichweite. Trotz vieler Jahrhunderte des Bemühens verwehrt uns das Universum noch immer eine Antwort auf die meisten mathematischen Fragen.

Eigentlich ist es schon ein wenig peinlich, zuzugeben, dass es noch immer einfach klingende Fragen gibt, die kein Mathematiker beantworten kann. Selbst im Rahmen der grundlegendsten Bausteine der Zahlen hält das Universum die Antworten auf einfache Fragen geheim und vor unserer Neugier verborgen. Wir wollen dieses Kapitel über Geheimnisse mit der Erforschung einiger Mysterien abschließen, die zu beantworten die Natur ablehnt.

Zahlen um Ihrer Selbst Willen. Seit Tausenden von Jahren lieben die Menschen Zahlen und finden in ihnen Muster und Strukturen. Die Anziehungskraft der Zahlen ist weder auf den Wunsch beschränkt, die Welt auf vernünftige Art und Weise zu verändern, noch wird sie in erster Linie von diesem Verlangen gespeist. Wenn wir beobachten, wie Zahlen miteinander in Verbindung stehen, erkennen wir das verborgene Funktionieren eines grundlegenden Konzepts. Diese Beobachtungen stammen von Menschen, die Zahlen wirklich lieben. Sie sprechen zu ihnen.

Manchmal aber sprechen die Zahlen nicht laut genug, um sie hören zu können. Dann vernehmen wir nur ein verführerisches Flüstern, ahnen die Möglichkeiten, ohne die Befriedigung erleben zu können, die eine Vollendung hervorruft. In der Zahlentheorie gibt es eine Menge grundlegender Fragen, die bis heute unbeantwortet geblieben sind.

Erinnern Sie sich daran, dass eine Primzahl eine ganze Zahl größer als i ist, die nicht als das Produkt kleinerer ganzer Zahlen aufgefasst werden kann. Die erste Handvoll Primzahlen sind 2, 3, 5, 7, 11, 13 und 17. Die Zahl 6 ist keine Primzahl, da sie auch als 2 X 3 notiert werden kann. Jede ganze Zahl, die größer als 1 ist, ist entweder eine Primzahl oder das Produkt von Primzahlen. Die Primzahlen sind die Bausteine – oder gewissermaßen die Elementarteilchen – für die ganzen Zahlen. Sie sind die unteilbaren Einheiten, aus denen alle anderen Zahlen bestehen. Und in dieser Eigenschaft gehören Primzahlen seit eh und je zu den am häufigsten untersuchten Ideen der Menschheitsgeschichte. Doch es gibt Fragen zu Primzahlen, die Mathematiker über Jahrhunderte hinweg verblüfft haben und die unbeantwortet geblieben sind. Zwei davon wollen wir jetzt vorstellen.

Die Goldbach-Vermutung. Jede gerade Zahl größer als 2 kann als Summe zweier Primzahlen dargestellt werden. Diese Vermutung wurde von Christian Goldbach am 2. Juni 1742 formuliert und blieb bis heute ungelöst – das heißt, niemand weiß, ob sie richtig oder falsch ist. Betrachten wir einige Beispiele, erkennen wir, dass diese Vermutung für kleine Zahlen zu gelten scheint: 4=2 + 2; 6 = 3 + 3; 8 = 3+5; 10 = 3 +7; 12 = 5 + 7; 14 = 3 + 11 und 16 = 5 + 11 … Tatsächlich haben Mathematiker mit Hilfe von Computern und abstrakter Argumentation belegen können, dass jede gerade Zahl bis ungefähr 1017 die Summe zweier Primzahlen ist. Das ist zwar eine außerordentlich lange Liste von Zahlen, aber es bleiben noch unendlich viel mehr Zahlen übrig, die verifiziert werden müssen. Als Veranschaulichung, wie weit wir von einer Lösung dieser Frage entfernt sind, sollten wir bedenken, dass 1939 bewiesen wurde, jede gerade Zahl könne als Summe von nicht mehr als 300000 Primzahlen ausgedrückt werden! Offensichtlich haben wir noch einen weiten Weg vor uns, um von 300000 auf 2 herunterzukommen.

Angenommen, irgendjemand beweist eines Tages die Goldbach- Vermutung oder denkt sich ein Gegenbeispiel aus, das heißt, er gibt eine gerade Zahl an, die nachweislich nicht die Summe zweier Primzahlen ist. Würde dies tatsächlich einen Unterschied ausmachen? Unsere erste Reaktion ist: Wahrscheinlich nicht. Denn was würde ein solcher Beweis schon verändern? Recht häufig scheinen mathematische Entdeckungen von Machbarkeit und Nutzen ziemlich weit entfernt zu sein. Aber wie uns die Geschichte gelehrt hat, können mathematische Fragen, die mit unserem heutigen Alltagsleben anscheinend überhaupt nichts zu tun haben, den Schlüssel für unser künftiges Alltagsleben bereithalten. Zusammen mit einigen vor 350 Jahren entdeckten abstrakten Einsichten wurde die uralte Vorstellung von Primzahlen zur Grundlage für die Public- Key-Kryptographie. Vielleicht wird in 100 Jahren eine Lösung für die Goldbach-Vermutung zu einem weiteren Geldregen von 400000000 Dollar führen – nur dass diese Summe in 100 Jahren einen Kaufwert von höchstens noch 24,99 Dollar haben wird.

Zwei Jahre lang war die Lösung tatsächlich 1000000 Dollar wert. Eine Stiftung lobte diesen Preis aus für den Fall, dass jemand die Goldbach-Vermutung zwischen dem 20. März 2000 und dem 20. März 2002 verifizieren könne. Wir vermuten, dass die Stiftung nicht allzu besorgt darüber war, einen Riesenscheck ausstellen zu müssen – und dazu kam es dann ja auch in der Tat nicht.

Wenn wir uns die Primzahlen in ihrer Reihenfolge ansehen, stoßen wir auf das nächste berühmte Primzahl-Geheimnis. Gelegentlich finden wir nämlich zwei ungerade Primzahlen, die sich so nahe stehen, wie es numerisch eben möglich ist – das heißt, die beiden ungeraden Primzahlen flankieren die gerade Nicht-Primzahl zwischen ihnen: 5 und 7, xi und 13, 17 und 19, 29 und 31, 41 und 4 p Solche Paare nennen wir Primzahlzwillinge.

Primzahlzwillingvermutung. Es gibt unendlich viele Primzahlzwinge. Diese Vermutung hat die Mathematiker jahrhundertelang beschäftigt, aber wir wissen bis heute nicht, ob es unendlich viele Primzahlzwillinge gibt oder ob sie ab einem bestimmten Punkt aufhören zu existieren. Das größte augenblicklich bekannte Zwillingspaar hat jeweils 51090 Ziffern. Sie lauten:

33 218925 X 2/169690 – 1 und 33 218925 X 2/169690 + 1.

Ist es sinnlos, herauszufinden, ob die Primzahlzwillingsvermutung stimmt? Wer weiß – vielleicht ist sie der Schlüssel zu einem kosmologischen Tresor, dem wir erst noch begegnen müssen.

Eine Straße, die uns zur führt. Nun folgt ein stupides Spiel. Denken Sie sich eine beliebige Zahl aus und führen Sie dann folgende einfache Schritte durch:
1. Wenn es eine gerade Zahl ist, teilen Sie sie durch 2.
2. Ist es eine ungerade Zahl, multiplizieren Sie sie mit 3 und addieren Sie 1.
3. Wiederholen Sie das Verfahren, bis die Antwort 1 heißt.

Lassen Sie es uns ausprobieren. Angenommen, wir beginnen mit 19. Da es eine ungerade Zahl ist, multiplizieren wir sie mit 3 und addieren 1, was 58 ergibt. Da 58 eine gerade Zahl ist, teilen wir sie durch 2 und erhalten 29. Da 29 ungerade ist, multiplizieren wir sie mit 3 und addieren 1, was 88 ergibt. Da 88 gerade ist, teilen wir sie durch 2 und bekommen 44. Erneut teilen wir 44 durch 2, erhalten 22, teilen erneut durch 2 und erhalten 11. Da 11 ungerade ist, multiplizieren wir sie mit 3 und fügen 1 hinzu, um 34 zu bekommen. Die teilen wir durch 2 und erhalten 17. Da dies eine ungerade Zahl ist, multiplizieren wir sie mit 3 und erhalten 52. Da 52 eine gerade Zahl ist, teilen wir sie durch 2 und bekommen 26. Die teilen wir wieder durch 2 und erhalten 13. Da 13 ungerade ist, multiplizieren wir sie mit 3 und addieren 1, sodass wir 40 erhalten. Die teilen wir nun durch 2 und bekommen 20. Erneut durch 2 geteilt, erhalten wir 10. Noch einmal durch 2 geteilt, erhalten wir 5. Mit 3 multipliziert und 1 addiert, bekommen wir 16. Durch 2 geteilt, ergibt 8; erneut durch 2 geteilt ergibt 4; noch einmal durch 2 geteilt, ergibt 2 und zum letzten Mal durch 2 geteilt, ergibt 1. Jetzt sind wir bei 1 angelangt und hören auf.

Wenn wir das Verfahren mit ein paar weiteren, willkürlich ausgesuchten Zahlen durchführen, werden wir jedes Mal feststellen, dass wir schließlich bei 1 ankommen. Und tatsächlich haben ein paar Leute mit eindeutig zu viel Zeit, Hochgeschwindigkeitscomputern und ein wenig theoretischer Arbeit bewiesen, dass mit dieser Methode jede Zahl bis ungefähr 317 X 1015 schließlich auf die 1 zurückgeführt werden kann.

Ein rätselhaftes Verfahren. Wenn die Zahl ungerade ist, multiplizieren wir sie mit 3 und fügen 1 hinzu, und ist die Zahl gerade, teilen wir sie durch 2 (bekannt als 3x + 1-Prozedur) und enden stets bei 1?

Niemand weiß, warum. Und nicht sehr viele Leute machen sich Gedanken darüber. Aber ein paar seltsame Gestalten finden diese (und ähnliche) Fragen so faszinierend, dass sie bis spät in die Nacht hinein über Lösungsmöglichkeiten nachdenken und systematisch den Kopf gegen die Wand schlagen, bis entweder die Wand oder der Kopf allmählich nachgibt. Wird es etwas bedeuten, wenn sie die Frage beantworten können? Wer weiß das schon? Wir aber wissen, dass unser instinktiver Wunsch, uns mit der Welt der Zahlen zu beschäftigen, sich in der Vergangenheit schon außerordentlich bezahlt gemacht hat. – Abstrakte Vorstellungen über Primzahlen und Faktorzerlegung führten unerwarteterweise zur Public-Key-Kryptographie und zu relativer Sicherheit im Internethandel. Irgendwie scheint die menschliche Zahlenneugier vom Altertum bis zur heutigen Zeit in Übereinstimmung mit dem Universum zu sein.