Cryptography Reference
In-Depth Information
Allgemeines zum Thema RSA-Kryptoanalyse
Bei asymmetrischen Verschlüsselungsverfahren ist zwar vieles anders als bei sym-
metrischen. Das Ziel von Abhörer Mallory ist jedoch weitgehend das gleiche: Er
will an den Klartext oder einen privaten Schlüssel herankommen. Während es bei
symmetrischen Verfahren Ciphertext-Only-, Known-Plaintext- und Chosen-
Plaintext-Attacken gibt (Abschnitt 4.1.2), spielen bei asymmetrischen Verschlüs-
selungsalgorithmen nur zwei Angriffstypen eine wesentliche Rolle:
■
Public-Key-Only-Attacke
: In diesem Fall steht Mallory nur Alices öffentlicher
Schlüssel zur Verfügung. Diesen kann er nutzen, um beliebige Klartexte zu
verschlüsseln. Eine Public-Key-Only-Attacke schließt daher immer ein, dass
Mallory auch Klartext-Geheimtext-Paare analysieren kann.
■
Chosen-Ciphertext-Attacke
: In diesem Fall kann Mallory einen Geheimtext
frei wählen und ihn von Alice entschlüsseln lassen.
Eine Public-Key-Only-Attacke ist in unserem Alice-Bob-Mallory-Modell immer
möglich, da der öffentliche Schlüssel per Definition allen bekannt ist. Die Voraus-
setzungen für eine Chosen-Ciphertext-Attacke sind dagegen nur in bestimmten
Fällen gegeben, etwa wenn Mallory Zugriff auf ein RSA-Hardwaremodul hat.
Die Chosen-Ciphertext-Attacke bietet zwar bessere Voraussetzungen als eine
Public-Key-Only-Attacke, doch die Vorteile sind nicht wirklich dramatisch. Zu
den Besonderheiten asymmetrischer Verschlüsselungsverfahren gehört daher,
dass Mallory fast alle seine Angriffe ohne Insiderinformationen (bekannte oder
gewählte Klartexte) starten kann.
Vollständige Schlüsselsuche
Theoretisch kann Mallory das RSA-Verfahren durch eine vollständige Schlüssel-
suche brechen (dies wäre eine Public-Key-Only-Attacke). Praktisch ist das jedoch
schon bei einer bescheidenen Schlüssellänge von 256 Bit ein mehr als aussichtslo-
ses Unterfangen. Mallory müsste dazu im Schnitt 2
255
Schlüssel durchprobieren
(das ist die Hälfte der 2
256
möglichen Schlüssel). Dies entspricht 10
76
Schlüsseln
- eine Zahl, die größer ist als die Anzahl der Atome im Universum. Da das Uni-
versum »nur« 10
18
Sekunden alt ist, müsste Mallory schon 10
58
Schlüssel pro
Sekunde durchprobieren, um überhaupt in einem erfassbaren Zeitraum einen
Erfolg erwarten zu können. Wenn Mallory also nichts Besseres einfällt als die
vollständige Schlüsselsuche, dann kann Alice und Bob nichts passieren.
Faktorisierungsangriff
Wie bereits erwähnt, ist die vollständige Schlüsselsuche bei weitem nicht der beste
Angriff auf das RSA-Verfahren. Deutlich besser ist folgende naheliegende Public-
Key-Only-Attacke: Mallory nimmt die Zahl
n
aus Alices öffentlichem Schlüssel
und versucht, diese in die zwei Primzahlen
p
und
q
zu zerlegen. Mit
p
und
q
kann