Cryptography Reference
In-Depth Information
Paar
(
i, t
)
wird als Schlüsselpaar interpretiert, verschlüsselt wird mit
F
und entschlüsselt
mit
I
. Man beachte, dass die Entschlüsselung eindeutig ist, da wir von Einwegpermuta-
tionen ausgehen. Allerdings bieten, gemäß der zugehörigen Sicherheitsdefinitionen, Ein-
wegpermutationen deutlich weniger Sicherheit als asymmetrische Kryptoschemen: Zum
einen sind die Anforderungen an den Invertierer im Vergleich zu den Anforderungen an
einen Angreifer auf ein asymmetrisches Kryptoschema höher. Der Invertierer muss aus
dem Chiffretext den
gesamten
Klartext bestimmen, nicht nur nicht-triviale Informatio-
nen über den Klartext (wie etwa das erste Bit des Klartextes). Zum anderen verlangt
man bei Einwegpermutationen nicht, dass die Entschlüsselung, ohne den privaten Schlüs-
sel zu kennen, für jeden Klartext schwer ist, sondern nur gemittelt über alle Klartexte. Es
kann also durchaus Klartexte geben, für die man leicht vom Chiffretext auf den Klartext
schließen kann. Ist, zum Beispiel, im RSA-Verfahren der Chiffretext
1
∈
Z
n
,dannmuss
auch der Klartext
1
sein.
Wie gesagt, vermutet man, dass RSA eine Familie von Einwegpermutationen mit Hin-
tertür ist. Dies ist die sogenannte RSA-Annahme.
Annahme 6.4.1 (RSA-Annahme). Die
RSA-Annahme
für Parameter
t
und
ε
besagt,
dass die RSA-Familie
E
RSA
(
t, ε
)
-sicher ist gemäß Definition 6.4.6.
Die Vermutung/Hoffnung ist, dass die RSA-Annahme für »große« Werte
t
und »kleine«
Werte
ε
gilt. Wir wollen uns diese Annahme plausibel machen. Natürlich können wir sie
nicht vollends rechtfertigen, da dies auf einen Beweis der Annahme hinauslaufen würde.
Versetzen wir uns dazu in die Lage eines Invertierers, der
(
n, e
)
sowie
y
=
x
e
mod
n
gegeben hat und versucht,
x
zu bestimmen. Ein Invertierer könnte zunächst versuchen,
n
zu faktorisieren, also
p
und
q
mit
n
=
p
q
zu bestimmen. Mit den Primfaktoren könnte
er dann
m
=
φ
(
n
)
berechnen und würde aus
e
dann
d
berechnen können. Wie wir aber
in Abschnitt 6.3 diskutiert haben, wird vermutet, dass das Faktorisieren großer Zahlen
schwer ist. Auf diesem Wege wird der Invertierer also
m
nicht ermitteln können. Nun
könnte es natürlich sein, dass es einen anderen Weg gibt,
m
zu bestimmen. Man kann
sich aber leicht überlegen, dass, wenn man
m
und
n
kennt, auch
p
und
q
bestimmen
kann.DasBestimmenvon
m
ist also so schwierig wie das Faktorisieren von
n
(siehe
Aufgabe 6.7.13). Unter der Annahme, dass das Faktorisieren großer Zahlen schwer ist,
folgt somit, dass man
m
auchnurschwerbestimmenkann.
Es könnte natürlich gelingen,
d
zu bestimmen, ohne den Weg über
m
zu gehen. Rivest,
Shamir und Adleman konnten in ihrer Arbeit aber allgemein zeigen, dass das Bestimmen
von
d
aus
n
und
e
genauso schwer ist, wie das Faktorisieren von
n
(siehe dazu auch
Aufgabe 6.7.14). Wir können also festhalten:
Bemerkung
6.4.1
.
Das Berechnen eines privaten RSA-Schlüssels
(
n, d
)
zu einem gegebe-
nen öffentlichen RSA-Schlüssel
(
n, e
)
ist genauso schwer wie das Faktorisieren von
n
.
·
Das bedeutet natürlich nicht zwingend, dass
x
schwer zu berechnen ist. Es könnte ja
einen Weg geben, bei dem
d
nicht bestimmt werden muss.
Leider ist nicht bekannt, ob die RSA-Annahme äquivalent ist zur Annahme, dass
das Faktorisieren großer Zahlen schwer ist; es gibt Hinweise dafür und dagegen (siehe
Abschnitt 6.8). Da das Faktorisierungsproblem ein altes, viel studiertes Problem in der
Mathematik ist, wäre es natürlich sehr wünschenswert, wenn die erwähnte Äquivalenz
gelten würde.
