Die Zahl, die aus der Kalte kam: Wenn Mathematik zum Abenteuer wird

Große Primzahlen

Was, so lautet die offene Frage, hindert die russischen Agenten daran, wie Toby Esterhase zu rechnen? Denn sie kennen wie der Circus sowohl den Modul 221 und den Exponenten 11 als auch die kodierte Nachricht 184 des George Smiley. Was hindert sie, den Rest von 18435 nach Division durch 221 zu ermitteln?

Sie kennen den Geheimexponenten 35 nicht, lautet die Antwort.

Aber könnten sie nicht aus der Kenntnis des Moduls 221 und des Exponenten 11 diesen Geheimexponenten 35 ermitteln? Irgendwie ist das ja auch den Eierköpfen im Circus gelungen, die dann den Zettel mit der Zahl 35 im Tresor versperrten.

Die Antwort lautet: Das ist tatsächlich möglich. Und es ist auch kein Geheimnis, wie man zur Zahl 35 kommt. Allerdings nur, wenn man weiß, dass 221 das Produkt der Primzahlen 13 und 17 ist: 13 × 17 = 221. Danach ist alles sehr einfach. Man geht nach dem folgenden „Rezept“ vor: Von den beiden Primzahlen 13 und 17 zieht man jeweils 1 ab, erhält also die Zahlen 12 und 16, und bildet deren Produkt: 12 × 16 = 192. Diese Zahl 192 ist der „Geheimmodul“.

Dann schreibt man eine Tabelle der stets um die Zahl 1 vermehrten Vielfachen des Geheimmoduls 192 auf, mit anderen Worten: die Zahlen

1 × 192 + 1 = 192 + 1 = 193,

2 × 192 + 1 = 384 + 1 = 385,

3 × 192 + 1 = 576 + 1 = 577,

4 × 192 + 1 = 768 + 1 = 769,

5 × 192 + 1 = 960 + 1 = 961,

…

Irgendwann wird eine der so berechneten Zahlen 193, 385, 577, 769, 961, … durch den Exponenten 11 teilbar sein. In unserem Beispiel ist es zufällig bereits bei der zweiten Zahl dieser Liste der Fall: Es gilt 385 : 11 = 35. Und schon ist der Geheimexponent 35 gefunden.

Wenn das so einfach ist – wozu der ganze Aufwand? Tatsächlich ist es nur deshalb einfach, weil in unserer Geschichte die kleine Zahl 221 der Modul war und es bei dieser kleinen Zahl mühelos war, sie als Produkt von Primzahlen zu schreiben. Hätte der Circus hingegen eine große Zahl als Modul genannt, wäre es um die Einfachheit geschehen gewesen.

An dieser Stelle muss zugegeben werden, dass die Geschichte von Smiley und dessen Verlangen nach dem Agenten 007 zu simpel erzählt wurde und sich in Wahrheit nie so hätte zutragen können. Denn das Verschlüsselungsverfahren, welches hier vorgestellt wurde, ist erst 1977 am Massachusetts Institute of Technology erfunden worden.16 Zu dieser Zeit war George Smiley längst im endgültigen Ruhestand und hatte sich, so John le Carré, „in Steeple Aston als zurückgezogen lebender Kauz etabliert. Mit ein paar liebenswerten Eigenschaften, zum Beispiel Selbstgespräche führen, wenn er durch das Städtchen schlenderte.“

Das hier geschilderte Prinzip des von den Informatikern Ronald L. Rivest, Adi Shamir und Leonard Adleman entwickelten Verfahrens, den Anfangsbuchstaben ihrer Nachnamen entsprechend RSA-Verfahren genannt, jedoch stimmt: Man nehme zwei Primzahlen – in unserem Beispiel 13 und 17 – und multipliziere sie. Daraus erhält man den Modul. Bei uns lautete er 13 × 17 = 221. Dann nehme man irgendeine Zahl – in unserem Beispiel war es die Zahl 11 –, die der Exponent heißt. (Ganz frei ist man in der Wahl des Exponenten nicht, aber das ist ein nebensächliches Detail.) Dann kann man eine Zahl, die man geheim halten möchte, dadurch kodieren, dass man ihre Potenz mit dem Exponenten als Hochzahl bildet und deren Rest nach der Division durch den Modul als chiffrierte Zahl seinem Partner mitteilt. Smiley hatte in unserer Geschichte die Zahl 7 mitteilen wollen. Er chiffrierte sie, indem er 711 berechnete und den Rest nach Division durch 221, also die Zahl 184, als chiffrierte Zahl an den Circus schickte. Dechiffriert kann die kodierte Zahl dadurch werden, dass man von den Primzahlen, von denen man ausgegangen war, jeweils 1 abzieht und das Produkt dieser Zahlen bildet. Wir nannten das Produkt der beiden um 1 verminderten Primzahlen den „Geheimmodul“. In unserer Erzählung war er die Zahl 12 × 16 = 192. Weil in unserer Geschichte 2 × 192 + 1 = 35 × 11 ist, war 35 der Geheimexponent. Die Potenz der chiffrierten Zahl mit dem Geheimexponenten als Hochzahl ergibt, wenn man den Rest nach der Division durch den Modul betrachtet, die ursprüngliche Zahl, die der Sender geheim halten wollte, zurück. Bei uns hatte Toby Esterhase 18435 durch 221 dividiert und ist so zu Smileys Wunsch nach den Agenten mit der Nummer 7 gelangt.

Beim echten RSA-Verfahren, nicht dem unserer Geschichte, sind jedoch die Primzahlen, deren Produkt den Modul ergibt, unvergleichlich größer als 13 oder 17. Es sind riesige Primzahlen, dreihundert oder vierhundert Stellen lang. Und das Produkt dieser beiden Primzahlen ergibt einen gigantischen Modul, der mehr als 700 Stellen besitzen kann. Solche Rechnungen gelingen natürlich nur mit einem Computer, aber die Maschine ist beim Multiplizieren blitzschnell. Den Modul des RSA-Verfahrens hat man sekundenschnell berechnet.

Und es macht dem Geheimdienst nichts aus, wenn die ganze Welt diesen Modul kennt. Denn aus einer 700-stelligen Zahl die beiden Primzahlen herauszukitzeln, deren Produkt sie ist, bedarf mühevoller Rechnungen. Bis heute ist kein schnelles Verfahren dafür bekannt. Selbst große, rechenstarke Computer brauchen viele Monate, bis sie die beiden Primfaktoren aufgefunden haben. Für das Dechiffrieren aber ist die Kenntnis der beiden Primzahlen unumgänglich. Denn nur mit ihnen kann man den Geheimmodul und schließlich den Geheimexponenten berechnen. Ohne sie ist es aussichtslos, den Geheimexponenten zu entlarven.

Wenn der Modul bereits einige Wochen, gar Monate bekannt ist, wird natürlich die Kodierung von Botschaften mit ihm unsicher. Vielleicht hat der Gegner bereits die beiden Primzahlen ermittelt, als deren Produkt dieser Modul entsteht. Darum wechseln die Geheimdienste nach bestimmten Zeiträumen die Module und die Exponenten, die sie für die Kodierungen heranziehen. Dies können sie ohne große Schwierigkeiten. Es gibt schließlich eine unendliche Fülle von Primzahlen, sogar eine regelrechte Überfülle. Die Anzahl der höchstens 400-stelligen Primzahlen allein beträgt mehr als 10397, das ist eine Zahl, die mit der Ziffer 1 beginnt und bei der sage und schreibe 397 Nullen angeschlossen werden.17

Nicht nur Geheimdienste brauchen das RSA-Verfahren.

Tippt man in das Tastenfeld eines Geldausgabeautomaten den Code seiner Kontokarte ein, wird die Nummer dieses Codes über eine öffentliche Telefonleitung an die kontoführende Bank übermittelt. Doch kein Fremder soll diesen Code abhören dürfen. Darum wird er automatisch im Geldausgabeautomaten chiffriert und erst bei der Bank des Kontoinhabers wieder dechiffriert. Das RSA-Verfahren findet bei solch alltäglichen und myriadenfach während eines Tages vollzogenen Handlungen seine Anwendung.

Führt man über Internet eine Bestellung durch und zahlt man mit Kreditkarte, muss die Nummer dieser Karte an die Rechnungsadresse übermittelt werden. Es wäre höchst gefährlich, wenn Fremde diese Übertragung anzapfen und die Daten der Kreditkarte ablesen könnten. Darum sichern sich die Firmen ab, indem sie die Kartennummer sofort nach dem Eintippen chiffrieren und erst bei Eingang an der gewünschten Adresse wieder dechiffrieren. Das RSA-Verfahren schafft so Sicherheit beim elektronischen Handel.

Doch man darf die Augen nicht verschließen: Der eigentliche Sinn und Zweck des RSA-Verfahrens war und ist, den Geheimdiensten ihr verdorbenes Geschäft zu erleichtern: das Verbergen und Täuschen, das Lügen und Betrügen.