Asymmetrische Chiffren - Kryptographie und IT-Sicherheit - page 126

Es bedeutet l equiv die äquivalente Länge eines symmetrischen Schlüssels. Bei einem guten
symmetrischen Verfahren müssen maximal alle |K|=2 lequiv von einem Angreifer durchprobiert
werden. Mit (4.2-9) können wir also zunächst feststellen: Ein RSA-Schlüssel müsste, wenn es
nur dieses einfache Faktorisierungsverfahren gäbe, mindestens doppelt so lang sein wie ein
guter symmetrischer Schlüssel, um die gleiche Sicherheit zu bieten.
Zum Leidwesen der Benutzer von RSA sind in den letzten 20 Jahren deutlich schnellere Algo-
rithmen zur Faktorisierung bekannt geworden. Das hat zur Folge, dass die Schlüssel für RSA
viel länger gewählt werden müssen, um noch sicher vor Faktorisierung zu sein. Schnelle Me-
thoden für die Faktorisierung sind Gegenstand der Forschung, und sie liegen außerhalb des
Rahmens für dieses Buch. Einen Überblick und Hinweis auf weitere Literatur finden sich z.B.
in [Bu04] und [BNS05].

Äquivalente Schlüssellänge für RSA
Für einen derzeit schnellsten Faktorisierungs-Algorithmus wird die Laufzeit L n in [Bu04] an-
gegeben mit:

u 1 u
v(logn) (loglogn)

L[u, v] e mit u 1/ 3, v const (4.2-10)

Die Konstante u=1/3 gilt für einen bestimmten Algorithmus und sie bestimmt die Laufzeit
wesentlich. Der Teilausdruck (log n) entspricht der Stellenlänge l n des Moduls n bis auf einen
Faktor (log n=l n ·log 2). Der Exponent in (4.2-10) ändert sich bei Umrechnung der Basis von e
auf 2 ebenfalls nur um einen Faktor (e, Basis für natürlichen Logarithmus). Damit können wir
entsprechend (4.2-8) die Länge eines äquivalenten symmetrischen Schlüssels angeben.

1/3 2/3

l : (log n) (log log n) mit log n l log 2 (4.2-11)

equiv n

Die rechte Seite in (4.2-11) gibt an, bis auf einen unbestimmten Faktor v, wie die Länge l equiv
eines äquivalenten, symmetrischen Schlüssels von der Stellenlänge l n des RSA-Moduls n ab-
hängt. Diese Abhängigkeit ist in Tab. 4-7 dargestellt.

Tab. 4-7: Schlüssel-Längen l n für RSA
im Vergleich zu symmetrischen Schlüsseln der Länge l equiv .

RSA: l n =ld n prop.

l equiv

equiv vgl. l k

512 9,0 56 56

1024 12,4 77 80

2048 16,9 105 112

4096 22,7 141 128/160

8192 30,5 190 192/256

In der ersten Spalte finden sich für RSA gängige und zukünftige Längen l n des Moduls. Sie
sind im Allgemeinen gleich der RSA-Schlüssellänge. In der zweiten Spalte stehen die aus
(4.2-11) berechneten Werte. Sie werden für die dritte Spalte proportional hochgerechnet zu der
Länge l equiv eines äquivalenten, symmetrischen Schlüssels. Der Proportionalitätsfaktor wurde
pragmatisch so gewählt, dass der 512-Bit-RSA-Schlüssel einem symmetrischen 56-Bit-
Schlüssel äquivalent ist. Der gewählte Faktor kann dadurch begründet werden, dass diese bei-