Cryptography Reference
In-Depth Information
Nun stellt sich die Frage, ob es einen anderen praktikablen Weg zur Berech-
nung der Modulo-Wurzel gibt. Die Antwort: nach heutigem Kenntnisstand nein.
Der Weg über die
-Funktion ist der einzige bekannte. Das Modulo-Potenzieren
ist damit eine Falltürfunktion, wobei die Falltürinformation die Faktorisierung
des Modulus ist. Mit dieser Vorarbeit lässt sich das RSA-Verfahren leicht erklä-
ren. Will Bob eine Nachricht an Alice mit dem RSA-Verfahren verschlüsseln,
dann ergibt sich folgender Ablauf:
ϕ
1.
Zunächst ist etwas Vorarbeit von Alice notwendig: Sie wählt zufällig zwei
große Primzahlen
p
und
q
und berechnet daraus
n
:=
p
·
q
.
2.
Alice wählt wiederum zufällig eine natürliche Zahl
e
, die teilerfremd zu
ϕ
(
n
)
ist (Sie erinnern sich:
(
n
)=(
p
-1)·(
q
-1)). Die Zahlen
n
und
e
bilden zusammen
den öffentlichen Schlüssel, den Alice öffentlich bekannt macht und den ruhig
auch Mallory erfahren darf.
ϕ
Alice berechnet
d
:=
e
-1
(mod
3.
ϕ
(
n
)).
d
ist ihr geheimer Schlüssel, den sie natür-
lich für sich behalten muss.
4.
Kennt Bob Alices öffentlichen Schlüssel
e
, dann verschlüsselt er damit seine
Nachricht
m
, die er wie oben gezeigt als Zahl betrachtet. Dazu berechnet er
c
:=
m
e
(mod
n
).
c
ist der Geheimtext, den er an Alice schickt. Die Verschlüsse-
lung entspicht einer Modulo-Exponentiation.
5.
Die von Bob erhaltene Nachricht
c
kann Alice nun entschlüsseln, indem sie
c
d
(mod
n
) berechnet. Das Ergebnis ist dann genau der Klartext
m
, den Bob
abgeschickt hat. Dieses Entschlüsseln entspricht einem Modulo-Wurzelzie-
hen: Alice zieht die
e
-te Modulo-Wurzel von
c
, indem sie die
d
-te Potenz be-
rechnet. Mallory kann
d
nicht ermitteln, weil er die Faktorisierung von
n
nicht kennt.
Dass Alice nun tatsächlich den Klartext in den Händen hält, zeigt folgende Rech-
nung:
c
d
= (
m
e
)
d
=
m
1(mod ϕ(n))
=
m
(mod n)
Da Bob die Verschlüsselungsfunktion
m
e
(mod
n
) für jede Nachricht
m
an Alice
berechnen muss und das öffentlich bekannte
e
dabei stets gleich ist, liegt es nahe,
für
e
einen vorteilhaften Wert zu wählen. Als besonders praktisch haben sich hier-
für die Primzahlen 3, 17 und 65.537 erwiesen, da diese in ihrer Binärdarstellung
nur wenige Einsen aufweisen und daher eine schnelle Exponentiation ermögli-
chen. Wird eine dieser Zahlen verwendet, dann ist eine RSA-Verschlüsselung logi-
scherweise um ein Vielfaches schneller als die Exponentiation mit einem 1.024-
Bit-Exponenten, wie sie bei Diffie-Hellman benötigt wird. Da
e
somit meist klein
und konstant ist, ist mit Schlüssellänge im Zusammenhang mit dem RSA-Verfah-
ren nahezu immer die Länge der Zahl
n
gemeint.
