RSA Verschlüsselung - Sicherheit

Diskussion von RSA

RSA stützt seine gesamte Sicherheit darauf, dass aus dem Modulus n und dem öffentlichen Schlüssel e keine Rückschlüsse auf den geheimen Schlüssel d gezogen werden können und dass die Faktorisierung von n (d. h. die Zerlegung von n in die Primzahlfaktoren p und q) so schwierig bleibt wie sie heute ist. Unglücklicherweise kann man jedoch nicht einmal beweisen, dass es sich bei der Faktorisierung von n um ein solch komplexes Problem handelt (man nimmt allerdings an, dass es so ist).

Wie bereits gesagt, benötigt man für RSA lange Schlüssel. Das sind nicht etwa Zahlen im Milliarden- oder Billionen-Bereich, sondern riesengroße Zahlen mit mehreren hundert Stellen. Das Problem ist, dass a) die Rechenleistung stark ansteigt und b) man neue Möglichkeiten zur Faktorisierung der Zahlen finden könnte. Das beste Verfahren für Zahlen mit mehr als ca. 110 Stellen ist momentan das allgemeine Zahlkörpersieb (siehe Tabelle). Die Schwere dieses Problems wird dann deutlich, wenn man sich einmal vor Augen hält, welche Aussagen über die Faktorisierung gemacht wurden. 1977 sagte Ron Rivest, die Faktorisierung einer 125-stelligen Zahl dauere 40 Billiarden Jahre. 17 Jahre später, 1994, wurde eine 129-stellige Zahl faktorisiert! Das zeigt nur, wie schwer es ist, auch nur annähernd genaue Aussagen zu treffen. Auf jeden Fall kann man wohl mit Gewissheit sagen, dass 512-Bit-Schlüssel schon längst nicht mehr ausreichen. 1024 Bit sollten das absolute Minimum sein. Wenn ich Ihnen allerdings einen Tipp geben darf, so sollten Sie mindestens 2048 Bit verwenden, um noch über einen längeren Zeitraum Ihren Schlüssel verwenden zu können.

Algorithmus	Eignung	Beschreibung
Zahlkörpersieb (Number Field Sieve, NFS)	für Zahlen ab 110 Stellen	Der schnellste bekannte Faktorisierungs-Algorithmus für Zahlen ab 110 Stellen; mit einer früheren Version wurde die neunte Fermat-Zahl 2⁵¹² + 1 faktorisiert.
Quadratisches Sieb (QS)	für Zahlen mit weniger als 110 Stellen	QS kam sehr häufig zum Einsatz; schnellere Versionen sind das multiple polynomial quadratic sieve und die Version double large prime variation.
Elliptische-Kurven-Algorithmen	kleinere Zahlen	Mit dieser Methode wurden lediglich 43-stellige Zahlen zerlegt. In diesem Bereich wird aber derzeit noch kräftig geforscht.
Pollards Monte-Carlo-Algorithmus	???	???
Kettenbruchmethode	???	noch nicht in Verwendung.
Versuchsweise Division	alle Zahlen	Die einfachste Methode: Man probiert einfach alle Primzahlen kleiner oder gleich der Quadratwurzel der zu faktorisierenden Zahl. Verständlicherweise ist der Algorithmus jedoch nicht sehr schnell.

Einige Verfahren zum Faktorisieren großer Zahlen

Jahr	Einzelpersonen	Unternehmen	Regierungen
1995	768	1280	1536
2000	1024	1280	1536
2005	1280	1536	2048
2010	1280	1536	2048
2015	1536	2048	2048

Empfohlene Längen für öffentliche Schlüssel (in Bit; Stand: 1994)

Zu obiger Tabelle: Derartige Voraussagen sind natürlich zu einem gewissen Grad immer unsinnig, da bahnbrechende technologische Fortschritte nicht berücksichtigt werden können. Wer weiß schon, wie weit wir im Jahre 2020 oder 2045 ist? Betrachtet man jedoch die Entwicklung der letzten Jahrzehnte, so können Sie grundsätzlich davon ausgehen, dass sich die Rechenleistung alle zehn Jahre verdoppelt. Die folgende Tabelle von Bruce Schneier gibt Voraussagen zur Faktorisierung für die nächsten Jahrzehnte:

Jahr	Schlüssellänge (Bit)
1995	1024
2005	2048
2015	4096
2025	8192
2035	16384
2045	32768

Längerfristige Voraussagen zur Faktorisierung

Ich allerdings halte diese Schätzungen für ausgesprochen pessimistisch und frage mich, ob 32768-Bit-Schlüssel (!) jemals geknackt werden können. Zieht man jedoch mögliche revolutionäre Entwicklungen in der Technik in Betracht (z. B. Quantencomputer), könnten sich diese Voraussagen durchaus als realistisch erweisen.

Neben den hier vorgestellten Angriffen gegen RSA gibt es noch einige weitere Methoden, die das Faktorisierungsproblem untergraben können. Da wäre z. B. ein Chosen-Ciphertext-Angriff, bei dem der Angreifer Alices Nachricht an Bob abfängt (und ähnliche Szenarien). Mit Hilfe bestimmter Operationen (und der Unterstützung von Alice, wenn sie des Vorgangs nicht gewahr wird) kann es dem Angreifer gelingen, die verschlüsselte Nachricht zu entschlüsseln.

Zudem erwies sich RSA als anfällig für Angriffe auf Systeme, die immer dasselbe Modul n verwenden, aber unterschiedliche e und d. Dies funktioniert leider nicht, da ein Angreifer unter Kenntnis von n, e₁, e₂, c₁ und c₂ (diese Zahlen sind ja öffentlich und nicht geheim!) der geheimen Nachricht m habhaft werden kann. Eine Gruppe von Benutzern sollte daher niemals einen gleichen Wert für n benutzen.

Auch existieren Angriffe gegen RSA mit kleinen Verschlüsselungs-Exponenten. Wird ein kleiner Wert für e gewählt, erhöht sich im Allgemeinen die Geschwindigkeit von RSA. Dies kann aber auch unvorteilhaft sein und Angriffe auf das System ermöglichen. Unter Kenntnis von e(e + 1)/2 linear abhängigen Nachrichten gibt es einen Angriff; bei weniger Nachrichten gibt es kein Problem. Sind die Nachrichten identisch, so genügen bereits e Nachrichten. Derartige Probleme lassen sich jedoch leicht umgehen, indem man die Nachricht mit unabhängigen Zufallswerten auffüllt, wie es viele RSA-Implementationen vormachen (z. B. PGP).

Des Weiteren wäre noch erwähnenswert, dass es in der Praxis – mal wieder – noch komplizierter aussieht. Zum Beispiel sollten die Primzahlen gewissen Anforderungen genügen, sonst wird der Algorithmus anfällig für Angriffe. Zudem ist das RSA-Kryptosystem nicht so einfach zu implementieren wie symmetrische Algorithmen wie DES oder RC4. Unbemerkt könnten sich also irgendwo Fehler einschleichen. Außerdem ist RSA so langsam, dass es sich kaum lohnt, die Klartexte damit zu verschlüsseln. Man zieht es daher vor, den Schlüssel, der dem Chiffrieren des Klartextes mit Hilfe eines symmetrischen Verfahrens dient, mit RSA zu verschlüsseln. So macht es z. B. PGP. Und noch ein Problem, bevor ich es vergesse: Natürlich muss man geeignete Primzahlen suchen, schließlich müssen bzw. sollten sie zufällig gewählt sein. Das heißt nicht, dass man eine zufällige Zahl aus der Menge der möglichen Zahlen herausgreift und dann versucht, diese zu faktorisieren – nein, das dauerte entschieden zu lang. Man benutzt statt dessen statistische Verfahren, um festzustellen, ob eine Zahl prim ist oder nicht. Wenn man diese Verfahren oft genug bei den Primzahl-Kandidaten durchführt, wird die Wahrscheinlichkeit immer größer, dass die Zahl prim ist. Da man diese Aussage aber trotzdem nicht mit 100%-iger Wahrscheinlichkeit zu treffen vermag, nennt man diese Zahlen, die statistischen Verfahren entstammen, auch Pseudoprimzahlen. Der Vorteil ist hierbei die Tatsache, dass die Frage "Ist n prim?" wesentlich leichter beantwortet werden kann als die Frage "Was sind die Faktoren von n?" – und genau daher rührt die Sicherheit von RSA! Ich kann schnell und einfach Primzahlen finden und deren Produkt bilden; viel schwerer ist es dagegen, anhand des Produktes herauszufinden, wie die Faktoren dieser Zahl lauten.

Machen Sie sich also bloß keine Sorgen wegen der Primzahlen:

Es gibt ausreichend viele Primzahlen der Länge 512 Bit. Die Anzahl der Primzahlen (10¹⁵¹) übersteigt die Anzahl der Atome im Universum (schätzungsweise 10⁸⁰) bei weitem.
Die Wahrscheinlichkeit, dass zwei Leute zufällig dieselbe Primzahl der Länge 512 Bit wählen, ist praktisch gleich null. Mit anderen Worten: Das wird nicht passieren.
Es ist physikalisch nicht möglich, eine Datenbank mit allen möglichen Primzahlen der Länge 512 Bit anzulegen.

Dies alles sollte man bei der Implementierung von RSA beachten, denn sonst könnte das gesamte Gerüst in sich zusammenbrechen und leicht gebrochen werden. Wenn Sie Programme einsetzen, die RSA benutzen, sollten Sie sicherstellen, dass dieses Programm vertrauenswürdig ist. PGP (wenigstens die Version 2.6.3i) gilt als sicher, da schon lange von allerlei Programmierern sorgfältig auf Fehler geprüft.

Zurück zum Hauptartikel über RSA