Kryptographie III

Die bekannteste ‘Public Key’-Verschlüsselungsmethode ist RSA.
Ihre Sicherheit beruht auf der Unmöglichkeit, astronomisch große Zahlen in Primfaktoren zu zerlegen. Effektive Angriffe auf RSA gibt es nur mit ‘Quantencomputern’, die aber bisher nicht gebaut werden können.

Das größte Problem bei der verschlüsselten Übermittlung von Nachrichten ist die Geheimhaltung des Schlüssels. Ein bekanntes Beispiel dafür ist das Knacken des ENIGMA-Schlüssels im 2. Weltkrieg durch den Mathematiker Alan Turing, wodurch
den Allierten zum Beispiel bei der Invasion 1944 die deutschen Gefechtsaufstellungen in der Normandie bekannt waren.

Deshalb gelten Verfahren als besonders sicher, deren Sicherheit nicht von der Geheimhaltung des Schlüssels abhängt: sogenannte asymmetrische (‘public key’) Verfahren, bei denen man auch bei Kenntnis der Verschlüsselungsmethode nicht sofort die Entschlüsselungsmethode kennt.

Das einfachste asymmetrische Verfahren, sowohl vom Verständnis als auch für die Implementierung in Soft- und Hardware ist RSA (benannt nach den Entwicklern Rivest, Shamir und Adleman).

RSA ist eine reale Anwendung für klassische Methoden der Zahlentheorie (Euklidischer Algorithmus, Kleiner Satz von Fermat) und ist deshalb ein gern gewähltes Beispiel für Vorträge über die praktische Relevanz der Mathematik. Das hat natürlich zur Folge, daß man auch im Internet viele ausführliche Erklärungen des RSA-Algorithmus findet (z.B. hier), so daß ich mich hier vielleicht etwas knapper fassen kann.

Die Asymmetrie des RSA-Verfahrens beruht letztendlich darauf, daß es leicht ist, zwei Zahlen zu multiplizieren, daß es aber schwierig ist, aus dem Produkt auf die beiden Faktoren zu schließen.

Sender A legt zwei große Primzahlen p und q fest. Das Produkt n=pq macht er öffentlich, die Faktoren p und q teilt er aber nur einmal B mit und hält sie ansonsten geheim. Korrektur: Das Produkt n=pq und eine Zahl d macht er öffentlich.

Wir nehmen an, daß die Nachrichten (bzw. ihre einzelnen Bits) als ganze Zahlen zwischen 0 und pq vorliegen.

Der öffentliche Schlüssel besteht nun aus n und einer ganzen Zahl d. Die Zahl d wird von A nicht geheim gehalten, und ist damit nicht nur B, sondern auch einem Hacker E bekannt.

Die Verschlüsselungsfunktion ist
x –> x^d modulo pq,
wobei die Schreibweise ‘modulo pq’ bedeutet, daß wir den Rest von x^d nach Divsion durch pq nehmen. (Nach Verschlüsselung haben wir also wieder eine Zahl zwischen 0 und pq.)

WENN jemand p,q kennt, dann kann er mit jedem einfachen Computeralgebra-System die Entschlüsselungsfunktion berechnen. Nämlich, durch Anwendung des Euklidischen Algorithmus kann man zunächst eine ganze Zahl e berechnen, so daß
de =1 modulo (p-1)(q-1).
Und dann ist die Entschlüsselungsfunktion einfach gegeben durch
y –> y^e modulo pq.
Der Beweis ist eine einfache Anwendung des Kleinen Satzes von Fermat.
(Die mathematischen Rechnungen im Detail kann man z.B. bei Kant sehr kurz und gut erklärt nachlesen.)

Um es noch einmal zusammenzufassen: p und q sind nur Sender und Empfänger bekannt, n=pq und d sind öffentlich. e kann man leicht berechnen, wenn man d und (p-1)(q-1) kennt.

Um den RSA-Algorithmus zu knacken, muß man also neben n=pq auch (p-1)(q-1) kennen. Man kann sich leicht überlegen, daß dies äquivalent dazu ist, p und q berechnen zu können. Die Frage ist also, ob man aus der Kenntnis des Produkts zweier Primzahlen die beiden Primzahlen bestimmen kann.

Nun weiß natürlich jeder, daß es kein Problem ist, Zahlen wie etwa 21 oder 35 als Produkt zweier Primzahlen zu zerlegen. Schwierig wird es aber, wenn man astronomisch große Zahlen verwendet. Es gibt diverse Algorithmen zur Primfaktorzerlegung, die aber für sehr große Zahlen alle nicht praktikabel sind.

Allerdings werden die Algorithmen immer besser und deshalb muß man immer größere Zahlen verwenden, um die Sicherheit von RSA garantieren zu können. Als RSA 1977 entwickelt wurde, galten 125-stellige Zahlen als praktisch nicht faktorisierbar, und damit also als absolut sicher für die Verwendung in der RSA-Verschlüsselung.

1999 gab es einen öffentlichen Wettbewerb zur Faktorisierung einer 140-stelligen Zahl. (Die Zahl war vorher von einer Jury als Produkt zweier großer Primzahlen ausgewählt worden, und die Jury hielt diese beiden Primzahlen während des Wettbewerbes natürlich geheim.) Die Faktorisierung gelang tatsächlich mit 4-wöchigem Einsatz von 200 Rechnern.

2003-2005 gelang die Faktorisierung einer 200-stelligen Zahl mit zweijähriger Arbeit eines Rechnerpools unter Leitung der Bonner Mathematiker Jens Franke und Thorsten Kleinjung. Für praktische Zwecke geht man heute aber noch davon aus, daß 200-stellige Zahlen mit vernünftigem Aufwand nicht faktorisierbar sind und damit also Sicherheit für das RSA-Verfahren garantieren. Aktuell gibt es eine 309-stellige Zahl, auf deren Faktorisierung von der RSA-Firma ein Preis in Höhe von 100000 US-Dollar ausgesetzt ist.

Es gibt allerdings einen Algorithmus für Quantencomputer, mit dem man Primfaktorenzerlegungen effektiv berechnen könnte, wenn es Quantencomputer geben würde. Für diesen Algorithmus erhielt Peter Shor 1998 die Nevanlinna-Medaille, eine Art Nobelpreis für Theoretische Informatik, der alle 4 Jahre vergeben wird. Damals, in den 90er Jahren, galt Shor’s Algorithmus eher als theoretischer Erfolg, weil man nicht damit rechnete, in absehbarer Zeit Quantencomputer bauen zu können. Inzwischen gibt es aber weltweit viele Experimentalphysiker, die an praktischen Realisierungen von Quantencomputern arbeiten. Vielleicht wird es also in 10 oder 20 Jahren bereits Quantencomputer geben. Aus Sicht unserer heutigen Verschlüsselungstechniken wäre dies allerdings eine Katastrophe.

Referenz: Teil 1, Teil 2

Ein Online-Formular zum Verschlüsseln von Texten mit RSA findet man hier auf mathematik.de.