Die Sicherheit des RSA

a) Direkter Angriff auf den Klartext

===> Das Problem kann vernachlässigt werden.

b) Angriff auf den Schlüssel

Es ist kein besseres Verfahren bekannt; möglicherweise sind beide Probleme äquivalent (im komplexitätstheoretischen Sinn, also die Lösungen gleich aufwendig).

Entscheidend für die Sicherheit also:

Wie schnell kann man große Zahlen faktorisieren?

Wie schnell kann man faktorisieren?

• Es gibt »schnelle« Verfahren nur für spezielle Zahlen (der Gestalt a^b ± c mit »kleinem« a und c). Diese Zahlen werden durch die Nebenbedingungen für die RSA- Schlüsselerzeugung praktisch ausgeschlossen.
• Die schnellsten allgemeinen Verfahren
  • Zahlkörpersieb u. ä. (Siverman 1987, Pomerance 1988, A. K. Lenstra/ H. W. Lenstra/ Manasse/ Pollard 1990),
  • Elliptische-Kurven-Faktorisierung (H. W. Lenstra 1987, Atkin/Morain 1993),
  haben einen Zeitaufwand der Größenordnung

Daraus ergeben sich folgende Schätzungen:

rsa120 (399 Bit)	830 MIPS-Jahre	(auf schnellem Rechner machbar)
rsa129 (429 Bit)	4600 MIPS-Jahre	(1994 im Internet)
512-Bit-Modul	420000 MIPS-Jahre	(vorläufig sicher)
700-Bit-Modul	4.2 × 109 MIPS-Jahre	(langfristig sicher)
1024-Bit-Modul	2.8 × 1015 MIPS-Jahre	(!!)

Schätzungen von Rivest (Grenze in Dezimalstellen):

Jahr	optimistisch	mittel	pessimistisch
1990	117	155	388
1995	122	163	421
2000	127	172	455
2005	132	181	490
2010	137	190	528
2015	142	199	567
2020	147	204	607

Vorsicht: Alle diese Schätzungen sind mit sehr großer Unsicherheit behaftet.

Weitere Sicherheitsprobleme

• Die RSA-Falle: Entschlüsseln einer Nachricht durch versehentliches, möglicherweise blindes Unterschreiben.
• Die Homomorphie-Eigenschaft des RSA.
• Verwendung kleiner Exponenten.
• Gleicher Modul für mehrere Teilnehmer.

Zurück zum Inhaltsverzeichnis

E-Mail an Pommerening@imsd.uni-mainz.de.