Rudolf Taschner - Die Zahl, die aus der Kälte kam - Wenn Mathematik zum Abenteuer wird

Zusammengefasst besagt dies: Es ist

( a + 1) p = a p + 1 + …,

wobei alle Zahlen, die in den drei Punkten … verborgen sind, durch die Primzahl p teilbar sind.

Angenommen, so argumentiert Fermat nun weiter, wir wüssten bereits, dass ap – a durch p teilbar ist. Dann ist wegen der Rechnung

( a + 1) p – ( a + 1) = a p + 1 + … − ( a + 1) = a p + 1 + … − a − 1 = a p – a + …

und wegen der Tatsache, dass alle Zahlen, die in den drei Punkten verborgen sind, durch p teilbar sind, auch die Differenz ( a + 1) p – ( a + 1) durch p teilbar.

Damit hat Fermat das gezeigt, was er beweisen wollte. Denn 1 p − 1 ist klarerweise durch p teilbar. Die eben durchgeführte Überlegung zeigt, dass daher auch 2 p − 2 durch p teilbar ist. Die eben durchgeführte Überlegung noch einmal angewendet beweist, dass auch 3 p − 3 durch p teilbar ist. Die eben durchgeführte Überlegung noch einmal angewendet beweist, dass auch 4 p − 4 durch p teilbar ist. Und so kann man von jeder Zahl a , von der man weiß, dass ap – a durch p teilbar ist, zur nächsten Zahl a + 1 voranschreiten und auch von ihr feststellen, dass ( a + 1) p – ( a + 1) durch p teilbar ist.

Die hier bewiesene Erkenntnis wird der Satz von Fermat genannt. Allerdings nicht der „große Satz von Fermat“, von dem Simon Singh in seinem schönen Buch „Fermats letzter Satz“ erzählt, sondern der sogenannte „kleine Satz von Fermat“. Obwohl dieser Satz alles andere als „klein“, vielmehr sehr bedeutend ist. Nebenbei bemerkt: Fermat hat nicht verraten, wie er zu seinem „kleinen Satz“ gelangt ist. Erst ein Jahrhundert später fand Leonhard Euler heraus, warum dieser Satz stimmt.

Wenn man weiß, dass ap – a = a ( ap -1 − 1) durch die Primzahl p teilbar ist, und wenn die Zahl a selbst durch p nicht teilbar ist, folgt, dass ap -1 bei der Division durch p den Rest 1 besitzen muss . Denn wenn a nicht durch p teilbar ist, muss ap -1 − 1 durch p teilbar sein. Auch diese Aussage wird zuweilen der „kleine Satz von Fermat“ genannt.

Zum Beispiel muss die 12. Potenz jeder nicht durch 13 teilbaren Zahl nach Division durch 13 den Rest 1 lassen. Oder die 16. Potenz jeder nicht durch 17 teilbaren Zahl muss nach Division durch 17 den Rest 1 lassen.

Jetzt sind wir plötzlich bei der Chiffriermethode des George Smiley angelangt: Denn der kleine Satz von Fermat besagt, dass für jede nicht durch 13 teilbare Zahl a , insbesondere für a = 7, die Potenz a 12 nach Division durch 13 den Rest 1 lässt. Der kleine Satz von Fermat besagt auch, dass – falls a nicht durch 17 teilbar ist – die 16. Potenz von a 12, also die Zahl ( a 12)16 = a 12 × 16 = a 192 nach Division durch 17 den Rest 1 lässt. Und nach Division durch 13 lässt sie auch den Rest 1. Also lässt die Potenz a 192 nach Division durch den Modul 13 × 17 = 221 mit Sicherheit den Rest 1. Als Formel geschrieben: a 192 ≡ 1.

Die Zahl 192, die wir aus der Rechnung (13 − 1) × (17 − 1) = 12 × 16 erhalten, ist genauso geheim wie der von Toby Esterhase aus dem Tresor entnommene Geheimkoeffizient 35. Wir nennen 192 den „Geheimmodul“.

Die Eierköpfe des Circus ermittelten mit dem Geheimmodul 192 für den Exponenten 11 den Geheimexponenten 35. Diese Zahl 35 ist nämlich deshalb der Geheimexponent, weil für sie 35 × 11 = 1 + 2 × 192 gilt. 184 hatte Smiley über den Eisernen Vorhang hinweg zum Circus gefunkt. Dies war der Rest, der bei a = 7 nach Division von a 11 durch 221 verblieb. Allgemein nennen wir den Rest, der nach Division von a 11 durch 221 verbleibt, die codierte oder verschlüsselte Zahl c . In unserem Beispiel ist c = 184. Und Toby Esterhase berechnet den Rest von c 35 nach Division durch 221, also den Rest von ( a 11)35 nach Division durch 221. Damit entschlüsselt er nämlich die codierte Botschaft c zur ursprünglichen Nachricht a zurück. Warum?

Weil in ( a 11)35 die Zahl a insgesamt 35 × 11-mal mit sich multipliziert wird. Was wegen 35 × 11 = 1 + 2 × 192 bedeutet, dass die Zahl a insgesamt 2 × 192-mal und dann noch einmal mit sich multipliziert wird. Wenn man 192-mal a mit sich multipliziert, bleibt nach Division durch 221 der Rest 1. Wenn man das Gleiche 2 × 192-mal durchführt, bleibt auch der Rest 1, denn 1 × 1 = 1. Und wenn man diesen Rest 1 noch einmal mit a multipliziert, bleibt schlussendlich der Rest a × 1. Mit anderen Worten: Der Rest von c 35 nach Division durch den Modul 221 lautet a × 1, also a . Deshalb hat Toby Esterhase nach der Berechnung des Restes von 18435 den Wunsch George Smileys nach dem Agenten mit der Nummer 7 erkannt.

16 Tatsächlich hatte bereits drei Jahre zuvor der britische Mathematiker Clifford Christopher Cocks genau die gleiche Idee. Diese war aber in den USA völlig unbekannt, weil der britische Geheimdienst sie nicht nur vor der Sowjetunion, sondern auch vor den Vereinigten Staaten geheim hielt.

17 Dass man dies weiß, liegt am sogenannten Primzahlsatz, den bereits Gauß vermutet hatte: Die Anzahl der Primzahlen bis zu einer großen Zahl x beträgt ungefähr diese große Zahl x , dividiert durch ihren natürlichen Logarithmus. Dieser natürliche Logarithmus ist grob die Anzahl der Stellen von x multipliziert mit 2,3.

18 Es war entscheidend, dass Smiley den Zettel, den er aus seinem Schuh geholt hatte, nach dem Funken der verschlüsselten Nachricht verbrannte. Angenommen, er beginge die Todsünde, eine zweite Nachricht, zum Beispiel 0 0 3 0 0 3 0 0 3, mit der gleichen Folge wie zuvor zu verschlüsseln und zu senden. Verschlüsselt würde diese Nachricht, indem er die beiden Zeilen

1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 …

0 0 3 0 0 3 0 0 3

zur folgenden Zeile addiert:

1 4 4 5 9 5 6 5 6 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 …

und auf die Länge der Nachricht, also auf

1 4 4 5 9 5 6 5 6

zusammenstutzt. Smiley muss damit rechnen, dass Karla die beiden von ihm verschlüsselten Botschaften abfängt und Karlas Leute sie untereinanderschreiben:

1 4 8 5 9 9 6 5 0

1 4 4 5 9 5 6 5 6

Wenn sie die untere von der oberen modulo zehn subtrahieren , bekommen sie

0 0 4 0 0 4 0 0 4

also ein offensichtliches Muster. Muster sind der Angriffspunkt für erfolgreiche Attacken auf eine verschlüsselte Botschaft. Bei einer mehrfachen Verwendung des Zettels wäre daher die Verschlüsselung nicht mehr sicher. Deshalb darf er nur einmal verwendet werden, daher auch der Name „one time“ in OTP.

19 Gebilde, bei denen Ziffern endlos auftauchen, kennen schon Grundschulkinder, wenn sie dividieren lernen. Nur selten gehen Divisionen so schön wie bei 42 : 6 = 7 auf, meist bleibt bei ihnen ein Rest. Dividiert man zum Beispiel 42 durch 15, erhält man den Quotienten 2, denn zweimal ist 15 in 42 enthalten, aber es bleibt der Rest 12. Denn zweimal 15 ergibt nicht 42, sondern nur 30, und der Unterschied von 30 zu 42 beträgt eben dieser Rest. Man schreibt dafür

42 : 15 = 2 + 12 : 15.

Allein, die Division des Restes 12 durch 15 ist undurchführbar, weil 15 gar nicht in 12 enthalten ist. Adam Ries, der uns das Stellenwertsystem gelehrt hat, führte mit Hilfe der Zahl Null die Division dennoch weiter: Er fügte an den Rest 12 eine Null hinzu, multiplizierte also 12 mit 10, und konnte die sich so ergebende Division 120 : 15 restlos zu Ende bringen. In zwei Zeilen zusammengefasst: