Sicherheit

Das RSA-Verfahren ist sicher, weil:

• die Kenntnis des öffentlichen Schlüssels nicht den Schluss auf den privaten Schlüssel zulässt, da man hierzu n in die Primfaktoren zerlegen müsste. Das ist aber bei sehr großem n momentan noch nicht in vernünftiger Zeit möglich. Der RSA-Algorithmus verwendet das Konzept der trap-door-function oder Einwegfunktion mit "Hintertüre". Die Multiplikation von p und q ist leicht möglich, umgekehrt ist die Zerlegung des Produkts n in die Faktoren p und q nicht möglich. Nur mit Hilfe einer zusätzlichen Information quasi "über die Hintertür" kann die Umkehrung, d. h. die Entschlüsselung durchgeführt werden. Im RSA-Algorithmus ist die Kenntnis der Primzahlfaktoren diese Hintertür. Erst sie ermöglicht Bob die Entschlüsselung.
• Sender und Empfänger verwenden unterschiedliche Schlüssel (öffentlicher und privater Schlüssel). Der geheime Schlüssel muß niemals ausgetauscht werden.

Die Sicherheit des RSA-Algorithmus hängt also direkt von der Verfügbarkeit eines schnellen Faktorisierungsverfahrens ab. Solange die Faktorisierung nicht durch neue Algorithmen entscheidend beschleunigt werden kann, ist das RSA-Verfahren als sicher zu betrachten. Die Beschleunigung der verfügbaren Hardware, die für entsprechende Angriffe verwendet werden kann, lässt sich durch längere Schlüssel recht einfach abfangen.

Allerdings müssen neben dem Verlass auf das zugrunde liegende zahlentheoretische Problem der Faktorisierung großer Zahlen auch noch einige weitere Faktoren gewährleistet sein:

• die Länge der Schlüssel muss ausreichend sein.
• die Schlüssel müssen geeignet erzeugt werden.
• die Anwendung des Verfahrens muss durchdacht sein.

Die notwendige Schlüssellänge = Komplexität hängt von der Entwicklung der Rechnergeschwindigkeit großer Zahlen ab. Als sicher gelten derzeit (im Jahr 2005) Schlüssellängen von über 1000 Bit.

Um auch mit kürzeren Schlüssellängen hohe Sicherheit bei asymmetrischer Verschlüsselung zu erzielen, kann man auch andere - auf ähnlichen Grundvoraussetzungen basierende - Verfahren verwenden. Die bekanntesten Verfahren beruhen auf der Schwierigkeit der Berechnung eines diskreten Logarithmus.

Verfahren

• Elgamal-Kryptosystem
• Elliptische-Kurven-Kryptosystem

Der entscheidende Vorteil der Verfahren im Vergleich zum RSA-Algorithmus ist, dass die sicheren Schlüssellängen erheblich kürzer sind und ein moderates Anwachsen der Schlüssellänge stärkere Erfolge bei der Erhöhung der Komplexität mit sich bringt.

Prognose für die Entwicklung der als sicher betrachteten Schlüssellängen für RSA bzw. Verfahren, die auf Diskretem Logarithmus basieren:

(Quelle: Arjen Lenstra und Eric Verheul: http://cryptosavvy.com).