Die Sicherheit des RSA

2a. Kryptographische Basistechniken

Die Sicherheit des RSA-Verfahrens

Genaueres im Kapitel Kryptoanalyse des RSA-Verfahrens der Kryptologie-Vorlesung

a) Direkter Angriff auf den Klartext

Iterieren der Verschlüsselung ergibt:

E^r(c) = c^{e^r}

Da die Exponenten mod f(n) reduziert werden können, sich also in der endlichen multiplikativen Gruppe des Restklassenrings Z/f(n)Z bewegen, gibt es ein r mit

e^r º 1 (mod f(n)), also E^r(c) = c, also E^r-1(c) = m (!!)

Die Wahrscheinlichkeit, dass für einen gegebenen Geheimtext c der Exponent r klein ist, ist extrem gering.

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

b) Angriff auf den Schlüssel

Wer den Modul n = pq faktorisieren kann, kann den geheimen Exponenten d aus dem öffentlichen e bestimmen.

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. ä. (Silverman 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

L_n =

Daraus ergeben sich folgende Schätzungen:

Zahl	Dezimalstellen	Aufwand	Status
rsa120 (399 Bit)	120	100 MIPS-Jahre	(auf schnellem PC in 1 Woche machbar)
rsa140 (466 Bit)	140	2000 MIPS-Jahre	(te Riele, CWI, 1999)
512-Bit-Modul	154	100000 MIPS-Jahre	(te Riele, CWI, 1999)
1024-Bit-Modul	308	10¹¹ MIPS-Jahre	(kurzfristige Sicherheitsgrenze)
2048-Bit-Modul	616	10¹⁵ MIPS-Jahre	(mittelfristige Sicherheitsgrenze)

... solange die Mathematiker keine wesentlich schnelleren Faktorisierungsverfahren finden!

Schätzungen von Rivest (80er Jahre) [Grenze in Dezimalstellen - im Bereich von 2048 Bit entspricht die pessimistische Schätzung dem heutigen Stand]:

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.

Neu:

Shamirs »TWINKLE« (= The Weizmann Institute Key Locating Machine) - Hardware-Umsetzung einer Idee von Lehmer aus den 30er-Jahren, die das Faktorisieren um den Faktor 100 - 1000 beschleunigt (ohne die Größenordnung zu ändern).
Selecting Cryptographic Key Sizes (Arjen Lenstra, Eric Verheul); zu pessimistisch, da der Speicherbedarf der Verfahren nicht berücksichtigt wurde.
Circuits for integer factorization: A proposal (Daniel J. Bernstein) - verdreifacht (!) die Stellenzahl, die bei festem Aufwand für das schnellste Faktorisierungsverfahren erreichbar ist.

Nach Bernsteins Vorschlag ist der Aufwand für das Zahlkörpersieb:

Zeit	L_n^{1.19 + o(1)}
Speicherpaltz	L_n^{0.79 + o(1)}

Die Abschätzung von Lenstra/Verheul sieht jetzt eher zu optimistisch aus. 1024-Bit-Schlüssel sollten schnellstens aus dem Verkehr gezogen werden! 2048-Bit-Schlüssel sind gerade noch für ein paar Jahre sicher.

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.

Vorlesung Datenschutz und Datensicherheit, Johannes-Gutenberg-Universität Mainz
Autor: Klaus Pommerening, 31. März 1999; letzte Änderung: 8. Dezember 2001.
E-Mail an Pommerening@imsd.uni-mainz.de.