Worum geht es in dieser Aktivität?

Es ist klar, dass du auch geheime Nachrichten über Computernetzwerke senden möchtest, die niemand außer dem beabsichtigten Empfänger entschlüsseln kann, egal wie clever oder wie schwer es versucht wird. Und natürlich gibt es viele Möglichkeiten dies zu tun, falls Sender und Empfänger einen geheimen Schlüssel benutzen. Aber das clevere an der Public-Key-Verschlüsselung ist, dass Amy eine sichere Nachricht ohne irgendeine geheime vorherige Absprache, an Bill senden kann und er einfach sein „Schloss“ von einem öffentlichen Ort wie einer Website abholt.

Geheimhaltung ist nur eine Seite der Kryptographie. Eine andere ist die Authentifizierung: Wenn Amy eine Nachricht von Bill erhält, woher weiß sie dann, dass sie wirklich von ihm kommt und nicht von einem Betrüger? Angenommen sie erhält eine E-Mail von ihm, in der steht: „Liebling, ich sitze hier fest ohne Geld. Bitte überweise 100 Euro auf mein Bankkonto, Nummer 0241-45-784329 – Dein Schatz, Bill.“ Wie kann sie wissen, ob sie wirklich von Bill kommt? Einige Public-Key-Kryptosysteme können auch dafür verwendet werden. So wie Amy eine geheime Nachricht an Bill sendet, indem sie sie mit seinem öffentlichen Schlüssel verschlüsselt, kann er ihr eine Nachricht schicken, die nur er erzeugen kann, indem er sie mit seinem privaten Schlüssel verschlüsselt. Wenn Amy sie mit Bills öffentlichem Schlüssel entschlüsseln kann, muss sie von ihm kommen. Natürlich könnte auch jeder andere sie entschlüsseln, da der Schlüssel öffentlich ist, aber wenn die Nachricht nur für Amy bestimmt ist, kann Bill sie dann ein zweites Mal mit Amys öffentlichem Schlüssel verschlüsseln. Diese duale Codierung bietet sowohl Geheimhaltung, als auch Authentifizierung mit demselben Grundschema öffentlicher und privater Schlüssel.

Jetzt ist es an der Zeit zu gestehen, dass das in dieser Aktivität dargestellte Schema eines Verschlüsselungssystems mit öffentlichem Schlüssel dem in der Industrie sehr ähnlich ist. Allerdings ist es kein sicheres Verfahren - selbst wenn eine ziemlich große Karte verwendet wird.

Obwohl es keinen Weg gibt, den minimalen Weg zu finden, um einen Eiswagen auf einer willkürlichen Karte zu platzieren und demzufolge das Schema auch sicher ist, gibt es eine ganz andere Methode, es anzugreifen. Es ist unwahrscheinlich, dass die SchülerInnen (zumindest vor der Sekundarstufe) auf die Idee kommen. Aber sie sollten zumindest wissen, dass eine Methode existiert. Man könnte sagen, das Schema, das wir uns angesehen haben, ist schulisch aber nicht mathematisch sicher. Bitte ignoriere den nächsten Absatz, wenn Mathematik nicht so dein Fach ist!

Nummeriere die Kreuzungen auf der Karte mit 1, 2, 3, ... Bezeichne die ursprünglichen Zahlen der Kreuzungen als b1, b2, b3, ..., und die Zahlen, die übermittelt werden als t1, t2, t3, .... Angenommen Kreuzung 1 ist mit den Kreuzungen 2, 3 und 4 verbunden, dann ist die Zahl, die für die Kreuzung 1 übermittelt wird

t1 = b1+b2+b3+b4 .

Natürlich gibt es für jede Kreuzung ähnliche Gleichungen—tatsächlich gibt es so viel Gleichungen wie die Anzahl der Unbekannten b1, b2, b3, .... Eine lauschende Person kennt die öffentliche Karte und die übermittelten Zahlen t1, t2, t3, ... und kann deshalb die Gleichungen aufschreiben und mit einem Gleichungslösungsprogramm zu einer Lösung kommen. Sobald die ursprünglichen Zahlen erhalten wurden, entspricht die Nachricht einfach ihrer Summe - es ist tatsächlich nicht notwendig, die Entschlüsselungskarte zu finden.

Der erforderliche Rechenaufwand zur Lösung der Gleichungen unter Verwendung des Gauß’schen Eliminationsverfahren ist proportional zur dritten Potenz der Anzahl der Gleichungen, aber da diese Gleichungen dünn besetzt sind - die meisten Koeffizienten sind Null - gibt es noch effizientere Techniken. Vergleiche das mit dem exponentiellen Rechenaufwand, der - soweit bekannt - der beste ist, um die Entschlüsselungskarte zu erstellen.

Wir hoffen, du fühlst dich nicht überfordert! Tatsächlich sind die Prozesse, die in echten Kryptosystemen mit öffentlichem Schlüssel enthalten sind, praktisch identisch mit dem, was wir gesehen haben, abgesehen davon, dass die Techniken, die sie zum Verschlüsseln verwenden, verschieden - und auch nicht per Hand ausführbar sind. Die ursprüngliche Public-Key-Methode und immer noch eine der sichersten, basiert auf der Schwierigkeit große Zahlen zu faktorisieren.

Welche sind die Faktoren der 100-stelligen Zahl?

9,412,343,607,359,262,946,971,172,136,294,514,357,528,981,378,983,082,541,347,532,211,942,640,121,301,590,698,634,089, 611,468,911,681? Verbringe nicht allzu viel Zeit mit dieser Frage!

86,759,222,313,428,390,812,218,077,095,850,708,048, 977 und 108,488,104,853,637,470,612,961,399,842,972,948,409,834,611,525,790,577,216,753 sind die gesuchten Faktoren. Es gibt keine
anderen Faktoren – beide sind Primzahlen. Sie zu finden ist eine ziemlich aufwendige Aufgabe: Tatsächlich ist es ein mehrmonatiges Projekt für einen Supercomputer.

In einem echten Public-Key-Kryptosystem könnte Bill nun die 100-stellige Zahl als seinen öffentlichen Schlüssel und die beiden Faktoren als privaten Schlüssel verwenden. Es wäre nicht schwer, solche Schlüssel zu finden: Dazu brauchst du nur eine Möglichkeit große Primzahlen zu berechnen. Finde zwei Primzahlen, die groß genug sind (das ist nicht so schwer), multipliziere sie, und - tada, da ist dein öffentlicher Schlüssel. Das Multiplizieren großer Zahlen ist für einen Computer keine große Sache. Mit dem öffentlichen Schlüssel kann niemand deinen privaten Schlüssel finden, es sei denn er hat mehrere Monate Zugriff auf einen Supercomputer. Und wenn dir das nicht reicht, verwende 200-stellige Primzahlen anstelle von 100-stelligen - das wird die Faktorisierung um Jahre verlangsamen! Die Hauptsache ist, dass die Kosten für das Knacken des Schlüssels höher sind als der Wert der Informationen, die er freischalten würde. In der Praxis sind 512-Bit- oder größere Schlüssel zum Einrichten sicherer Verbindungen üblich, was ungefähr 155 Dezimalziffern oder mehr entspricht.

Wir haben noch immer keinen Weg gefunden, eine Nachricht unter Verwendung eines öffentlichen Schlüssels auf Primzahl-Basis so zu verschlüsseln, dass sie ohne den privaten Schlüssel nicht entschlüsselt werden kann. Um das zu tun, ist das Leben nicht ganz so einfach, wie wir es oben beschrieben haben. Es sind nicht die beiden Primzahlen, die als privater Schlüssel verwendet werden und ihr Produkt, das als öffentlicher Schlüssel verwendet wird, sondern Zahlen, die von ihnen abgeleitet sind. Aber der Effekt ist der gleiche: Du kannst den Code knacken, indem du die Zahl faktorisierst. Wie auch immer, es ist nicht schwer, diese Schwierigkeiten zu überwinden und das Schema zu einem geeigneten Verschlüsselungs- und Entschlüsselungsalgorithmus zu machen, darauf wollen wir aber jetzt nicht weiter eingehen. Diese Aktivität hat bereits genug Arbeit geleistet!

Wie sicher ist ein auf Primzahlen basiertes System? Nun, die Faktorisierung großer Zahlen ist ein Problem, das seit mehreren Jahrhunderten die Aufmerksamkeit der größten MathematikerInnen der Welt auf sich gezogen hat, und während Methoden entdeckt wurden, die wesentlich besser sind als die Brut-Force-Methode (d.h. es mit allen möglichen Faktoren auszuprobieren) ist man bisher nicht zu einem sehr schnellen (d.h. polynomiellen) Algorithmus gekommen. (Niemand hat bewiesen, dass ein solcher Algorithmus auch unmöglich ist.) Somit scheint das Schema nicht nur für SchülerInnen sicher zu sein, sondern auch für MathematikerInnen. Aber Achtung: Wir müssen vorsichtig sein. So wie sich herausstellte, dass es eine Möglichkeit gibt Bills Code zu knacken, ohne das Problem der Touristenstadt zu lösen, könnte es einen Weg geben, die Primzahlcodes zu knacken, ohne große Zahlen zu faktorisieren. Die Menschen haben das soweit sorgfältig überprüft und es scheint in Ordnung zu sein.

Ein weiterer Vorbehalt ist, dass ein Eindringling, wenn es nur ein paar mögliche Nachrichten gibt, jede von ihnen nacheinander mit dem öffentlichen Schlüssel verschlüsselt und die tatsächliche Nachricht mit allen möglichen Resultaten vergleicht. Amys Methode verhindert das, da es viele Möglichkeiten gibt die gleiche Nachricht zu verschlüsseln, abhängig davon, welche Zahlen ausgewählt und zum Codewert addiert wurden. In der Praxis sind kryptographische Systeme so konzipiert, dass es zu viele mögliche Nachrichten gibt, um es sogar mit Hilfe eines sehr schnellen Computers auszuprobieren.

Es ist nicht bekannt, ob eine schnelle Methode zur Lösung des Problems der Primfaktorzerlegung existiert. Niemand hat es geschafft eine zu entwickeln, aber es ist auch nicht bewiesen, dass eine schnelle Methode unmöglich ist. Wenn ein schneller Algorithmus zur Lösung dieses Problems gefunden wird, werden viele derzeit verwendete kryptographische Systeme unsicher werden. In Teil IV betrachteten wir NP-vollständige Probleme, die alle zusammen stehen oder fallen. Das bedeutet: Wenn eines von ihnen effizient lösbar ist, dann sind auch alle anderen lösbar. Da sehr viel (erfolgloser) Aufwand betrieben wurde, um schnelle Algorithmen für diese Probleme zu finden, schienen sie ausgezeichnete Kandidaten zum Entwurf sicherer Kryptosysteme zu sein. Leider gibt es Schwierigkeiten mit diesem Vorgehen und bis jetzt waren die EntwicklerInnen von Kryptosystemen gezwungen, sich auf Probleme (wie Primfaktorzerlegung) zu verlassen, die in der Tat einfacher zu lösen sind als die NP-vollständigen Probleme - vielleicht sogar sehr viel einfacher. Die Antworten auf die Fragen, die sich daraus ergeben, sind der Industrie viele Millionen Euro wert und gelten als entscheidend für die nationale Sicherheit. Kryptographie ist heute ein sehr aktives Forschungsgebiet in der Informatik.

Weiterführende Literatur

Harels Buch Algorithmics behandelt Public-Key-Kryptographie; es wird erläutert, wie große Primzahlen verwendet werden, um ein sicheres öffentliches Schlüsselsystem zu erstellen. Als Standardliteratur zum Thema Kryptographie zählt Cryptography and Data Security von Dorothy Denning; ein mehr praxisorientiertes Buch heißt Applied Cryptography von Bruce Schneier. Das Buch Turing Omnibus von Dewdney beschreibt ein weiteres System zur Anwendung von Public Key-Kryptographie.