Zum Glück interessiert sich kaum jemand für meine Steuererklärung – bei mir gibt es wenig zu holen. Tatsächlich hätte ein Angreifer aber die verschlüsselte Kommunikation zwischen meinem Laptop und dem Drucker abfangen und eventuell entschlüsseln können, um an diese Dokumente zu kommen. Denn 2022 stellte der Informatiker Hanno Böck fest, dass sich einige Verschlüsselungen ganz einfach knacken lassen, wie er in einem Beitrag für »The International Association for Cryptologic Research« beschreibt. Dafür hatte er nicht etwa einen neuen, besonders cleveren Algorithmus ausgetüftelt. Nein, er griff auf eine Methode zurück, die der französische Gelehrte Pierre de Fermat bereits im 17. Jahrhundert entwickelt hat.

Fermat ist vor allem für eine Vermutung bekannt, die erst Mitte der 1990er Jahre bewiesen wurde. Der Clou an der Sache: Fermat hatte in einer Notiz am Rand eines Buchs behauptet, einen ganz wunderbaren Beweis zu haben, nur bliebe ihm leider nicht genug Platz, um ihn an dieser Stelle zu notieren. Das war der wohl größte Streich der Mathematikgeschichte – denn diesen vermeintlich wunderbaren Beweis suchten Fachleute vergeblich. Erst nach mehr als 350 Jahren und der Entwicklung völlig neuer mathematischer Gebiete konnte der »große Satz von Fermat« endlich bewiesen werden.

Neben Streichen hat Fermat der Fachwelt allerlei Nützliches beigetragen. So legte er den Grundstein für die Wahrscheinlichkeitstheorie und beschäftigte sich auch viel mit Primzahlen – jenen Werten, die nur durch eins und sich selbst teilbar sind. Seine Erkenntnisse in diesem Bereich nutzte Böck mehrere Jahrhunderte später, um vermeintlich sichere Verschlüsselungen auszuhebeln.

Komplexe Probleme für die Sicherheit

Moderne Verschlüsselungssysteme basieren auf schwierigen Mathematikaufgaben. Die Funktionsweise ist ähnlich wie bei einem Vorhängeschloss: Die Aufgabe (das Schloss) ist ohne zusätzliche Information (der Schlüssel) nicht zu lösen. Eine verbreitete Methode für ein solches Verfahren ist die so genannte RSA-Kryptografie, die mit Primzahlen zusammenhängt. Sie beruht auf der Schwierigkeit, große Zahlen in ein Produkt aus Primzahlen zu zerlegen.

Primzahlen werden auch gern als die Atome der Zahlentheorie bezeichnet: Sie sind die unteilbaren Bausteine, aus denen sich die natürlichen Zahlen aufbauen. Jede andere Zahl lässt sich als ein eindeutiges Produkt aus Primzahlen schreiben, zum Beispiel 15 = 3·5 oder 20 = 2·2·5. Für kleine Werte ist es leicht, die Primteiler zu ermitteln. Aber wie sieht es zum Beispiel mit 7 327 328 314 aus? Bisher gibt es kein Computerprogramm, das in der Lage ist, die Primteiler beliebig großer Zahlen in annehmbarer Zeit zu berechnen.

Genau das nutzt die RSA-Kryptografie aus. Sie verschlüsselt Daten mit Hilfe von großen Zahlen. Das kann man sich vereinfacht gesehen so vorstellen: Angenommen, eine Person will das Wort SPEKTRUM, das aus acht Buchstaben besteht, verschlüsselt an einen Empfänger senden. Dafür nutzt sie eine große achtstellige Zahl wie 34 674 321 und verschiebt jeden Buchstaben von SPEKTRUM um die jeweilige Ziffer; S wird also zu V, P wird zu T und so weiter. Am Ende erhält man also das verschlüsselte Wort: VTKRXUWN. Dieses kann ein Sender nun an eine andere Person schicken, ohne dass ein Mithörer in der Lage ist, die Nachricht zu entschlüsseln.

Allerdings sollte der Empfänger das ursprüngliche Wort SPEKTRUM ermitteln können. Dafür braucht er entweder den Schlüssel, also 34 674 321, oder er einen entscheidenden Hinweis, um den Schlüssel zu berechnen. Da Ersteres immer ein Risiko birgt – ein Angreifer könnte die Kommunikation zwischen beiden Parteien mithören und so den Schlüssel abgreifen – bietet die RSA-Kryptografie eine Möglichkeit, den Schlüssel durch eine Reihe von cleveren Ideen auf sichere Weise zu rekonstruieren, wie ich in einer früheren Kolumne erläutert habe.

Die Idee ist folgende: Bevor sich der Empfänger die geheime Nachricht sendet, erzeugen die beiden Parteien gemeinsam aus öffentlich zugänglichen Informationen einen Schlüssel. Die Sicherheit wird dadurch gewährleistet, dass Sender und Empfänger jeweils im Geheimen große Primzahlen verwenden, die sie miteinander multiplizieren. Sie senden sich aber nur die Ergebnisse dieser Berechnungen zu. Ein Mithörer bräuchte die Primzahlen zur Erzeugung des Schlüssels, da er aber nur die Produkte abfangen kann und diese nicht faktorisieren kann, ist er hilflos.

Wie man einen sicheren Schlüssel erzeugt

Die Idee eines sicheren Schlüsselaustauschs lässt sich vereinfacht durch Farbeimer erklären: Angenommen, Alice und Bob wollen einen Schlüssel generieren. Dafür einigen sie sich zunächst auf eine gemeinsame Ausgangsfarbe, die öffentlich einsehbar ist, zum Beispiel Gelb – sie entspricht dem öffentlichen Schlüssel. Alice und Bob besitzen außerdem jeweils eine geheime Farbe (Alice Rot und Bob Türkis), die niemand sonst kennt. Dies ist der private Schlüssel. Beide mischen die abgesprochene gelbe Farbe mit ihrer Geheimfarbe.

Alice erhält so eine orange Mischung und Bob eine hellblaue. Nun tauschen Alice und Bob ihre Mischfarben öffentlich aus: Alice besitzt jetzt den hellblauen Farbeimer und Bob den orangenen. Um dann den symmetrischen Schlüssel zu generieren, schütten Alice und Bob in ihre Mischfarbe jeweils ihre Geheimfarbe. Somit erhalten beide dasselbe Ergebnis: eine braune Pampe.

Die braune Farbmischung entspricht in diesem Bild dem symmetrischen Schlüssel, mit dem Alice und Bob über ein Protokoll wie Lucifer sicher kommunizieren können. Selbst wenn ein Angreifer die ausgetauschten Farbeimer unterwegs abgegriffen hätte, könnte er ohne Kenntnis der jeweiligen Geheimfarben nicht auf das entstandene Ergebnis schließen.

Die Sicherheit der RSA-Kryptografie basiert also darauf, dass es superschwer ist, große Zahlen in ihre Primzahlen zu zerlegen. Bereits vor mehr als 350 Jahren beschäftigte sich Fermat mit ähnlichen Problemen; auch er wollte wissen, wie man Zahlen in ihre Primzahl-Bestandteile faktorisieren kann. Allerdings tat er das aus reiner mathematischer Neugier – damals waren noch keine kryptografischen Verfahren zum sicheren Schlüsselaustausch bekannt.

Die Fermat-Faktorisierung

Und tatsächlich fand Fermat einen Weg, um selbst große Zahlen, die das Produkt zweier Primzahlen sind, zu faktorisieren. Seine Methode ist nicht einmal kompliziert: Man braucht dafür bloß einen Taschenrechner (den hatte Fermat nicht, weshalb er wohl viel Zeit mit langwierigen Berechnungen verbrachte). Und um seine Zeitgenossen zu beeindrucken, führte Fermat die Methode an der Beispielzahl n = 2 027 651 281 vor.

Die Fermat-Faktorisierung funktioniert folgendermaßen: Man nimmt die Zahl n, in diesem Fall 2 027 651 281, und zieht daraus die Wurzel. In der Regel wird dabei ein krummer Wert herauskommen, so auch hier: √2 027 651 281 ≈ 45 029,45. Dann rundet man auf, erhält also 45 030. Diese Zahl wird quadriert, und von dem Ergebnis wird der ursprüngliche Wert n abgezogen: 45 030² − 2 027 651 281 = 49 619. Nun muss man prüfen, ob das Ergebnis eine Quadratzahl ist. Das ist hier nicht der Fall.

Also macht man weiter. Man startet wieder mit der aufgerundeten Wurzel 45 030, addiert 1 hinzu und quadriert dann das Ergebnis, um davon den ursprünglichen Wert n abzuziehen, also: 45 031² − 2 027 651 281 = 139 680 und prüft wieder, ob das Ergebnis eine Quadratzahl ist. Das ist wieder nicht der Fall.

Deshalb wiederholt man das Ganze. Dieses Mal addiert man zu 45 030 zwei hinzu und quadriert wieder das Ergebnis, von dem man den ursprünglichen Wert n abzieht: 45 032² − 2 027 651 281 = 229 743. Wieder keine Quadratzahl.

Fermat muss wirklich viel Geduld gehabt haben (zumal er ja keinen Taschenrechner hatte). Man muss das Verfahren insgesamt elfmal durchführen, bis man eine Quadratzahl vorfindet: 45 041² − 2 027 651 281 = 1 040 400 = 1020².

Und wie bringt uns das jetzt weiter? In der obigen Gleichung ist eine quadrierte Zahl y² (in diesem Fall 45 041²) minus n gleich eine andere quadrierte Zahl x² (in diesem Fall 1020²), also y² − n = x². Diese Gleichung kann man umstellen: y² − x² = n. Die linke Seite entspricht der dritten binomischen Formel: (y−x)·(y+x) = n. Damit hat man die Zahl n automatisch in zwei Zahlen y−x und y+x faktorisiert. Für das Beispiel mit n = 2 027 651 281 lauten die zwei Faktoren also 45 041−1020 = 44 021 und 45 041+1020 = 46 061. Beide sind Primzahlen.

Angriff auf den Drucker

Tatsächlich funktioniert diese Faktorisierungsmethode immer für ungerade n – allerdings können selbst Computer sie nur dann schnell genug ausführen, wenn die beiden Primfaktoren von n nicht zu weit auseinanderliegen, also ungefähr die gleiche Größenordnung haben. Und genau hier lag das Problem, das der Informatiker Hanno Böck in einer Programmbibliothek aufdeckte, die verschiedene Firmen nutzten: Die für die Verschlüsselung erzeugten Primzahlen waren nicht zufällig genug. Das Programm wählte oftmals zwei Primzahlen aus, die nah beieinander sind. Damit lässt sich die Faktorisierung von Fermat zum Aushebeln der Verschlüsselung nutzen.

Böck erkannte, dass die Drucker bestimmter Firmen solche mangelhaften Verschlüsselungen verwendeten. Diese greifen auf RSA-Kryptografie zurück, um beispielsweise vertrauliche Unterlagen zu schützen, die durch ein Netzwerk an den Drucker geschickt werden. Jetzt bleibt nur zu hoffen, dass diese und auch andere Firmen die Sicherheitslücken geschlossen haben.

Ohnehin werden viele Unternehmen ihre Verschlüsselungsstandards in den kommenden Jahren überdenken müssen: Denn, auch wenn gewöhnliche Rechner an der Faktorisierung großer Zahlen scheitern, wird das bei leistungsfähigen Quantencomputern anders sein. Diese greifen bei der Berechnung allerdings auf komplizierte Prinzipien der Quantenmechanik zurück, von denen Fermat vor mehr als 350 Jahren definitiv noch nichts wissen konnte.