Cryptography Reference
In-Depth Information
4.2.3 Sicherheit von RSA
Der private RSA-Schlüssel d kann aus dem öffentlichen Schlüssel (e, n) berechnet werden,
falls entweder (n) oder die Faktorisierung n = p·q aus n ermittelt werden könnte. Diese bei-
den Probleme sind äquivalent [BNS05].
Man könnte fälschlich meinen, dass (n)=(p1)·(q1) sich „ganz in der Nähe von“ n=p·q
befindet, also durch Probieren gefunden werden könnte. Dies ist jedoch nicht der Fall, denn
der „Abstand“ ist n(n)=p+q1. Das heißt, für den Fall dass q eine Zahl von z.B. l q 522 Bit
ist, dann müssten ca. 2 522 Zahlen durchprobiert werden, was nicht durchführbar ist (die Zahl p
der Größenordnung von 2 502 in dem Beispiel ist dagegen relativ klein und spielt keine Rolle).
Die Sicherheit des RSA hängt davon ab, dass ein Angreifer aus dem Modul n und dem öffent-
lichen Schlüssel e den zugehörigen privaten Schlüssel nicht berechnen kann. Deshalb darf es
nicht möglich sein, den Modul n in realistischer Zeit zu faktorisieren, d.h. einen der beiden
Faktoren p oder q zu finden. (Der andere Faktor ergibt sich leicht durch Division von n durch
den gefundenen Faktor).
Ob der Aufwand für das Faktorisieren oberhalb einer gewissen Schranke liegt, konnte bisher
nicht bewiesen werden. Es ist also nicht auszuschließen, dass ein Mathematiker einen Algo-
rithmus findet, der die Faktorisierung auch für sehr große Zahlen löst. Dann wäre der RSA-
Algorithmus nicht mehr verwendbar. Die Sicherheit des RSA-Algorithmus hängt also von
einem offenen mathematischen Problem ab. Deshalb ist es notwendig, für den Bedarfsfall
Alternativen zu haben.
Eine andere Art von Angriff, der „Seitenkanalangriff“, stützt sich auf eine Kombination von
kryptographischen und elektronischen Möglichkeiten. In [CrypTool] ist solch ein Seitenkanal-
angriff implementiert (Menü Analyse \ Asymmetrische Verfahren \ Seitenkanalangriff auf
Textbook-RSA).
4.2.3.1 Faktorisierungsproblem, äquivalente Schlüssellänge
Die Faktorisierungs-Algorithmen bestimmen, wie groß der Modul n für RSA zu wählen ist. Je
leistungsfähiger faktorisiert werden kann, umso größer muss die Stellenzahl des Moduls sein.
Wir wollen der Frage nachgehen, wie lang der Modul n wirklich sein muss. Eine ausführliche
Darstellung über Faktorisierung und Primzahlen findet sich in [CrypTool].
Der simpelste Algorithmus, um n zu faktorisieren, ist, n probeweise durch 3, 5, 7,... zu dividie-
ren und zu prüfen, ob ein Rest von 0 sich ergibt. (Die geraden Zahlen kann man weglassen,
weil ein Primfaktor eine ungerade Zahl ist). Es sind maximal 1/2·n Versuche erforderlich,
weil bei zwei Primfaktoren der kleinere Faktor höchstens den Wert n haben kann. Die Zahl
der Versuche ist dabei maximal L n .
l
ld (1/ 2
n )
l/21
L / 2n2
2
2
i
l
ldn
(4.2-8)
equiv
n
n
n
Darin bedeuten ld der Logarithmus zur Basis 2 (log 2 ) und l n die Zahl der Binärstellen, um den
Modul n als Dualzahl darzustellen. Die zunächst unnötig erscheinende Umformung in (4.2-8)
führt auf ein anschauliches Maß l equiv .
l
l
/ 2
1
(4.2-9)
equiv
n
Search WWH ::




Custom Search