Cryptography Reference
In-Depth Information
P
wählt eine Zahl
e
∈{
2, . . . ,
p
−
2
}
mit ggT
(
e
,
p
−
1
)=
1. Es ist
e
der ge-
meinsame, geheime Schlüssel von
P
und
H
.
∈{
−
}
≡
(
−
)
H
bestimmt
d
2, . . . ,
p
2
mit
ed
1
mod
p
1
mit dem euklidischen
Algorithmus.
Chiffrierung und Dechiffrierung einer Nachricht.
Der Sender
P
verschlüsselt
seine Nachricht mit dem geheimen Schlüssel
e
und sendet diese an den Empfän-
ger
H
;
H
entschlüsselt die Nachricht mithilfe der Zahl
d
:
N∈
Z
p
dar.
P
stellt seine Nachricht als Element
e
mit dem geheimen Schlüssel
e
.
C
=
N
P
bildet die Potenz
:
P
sendet den Geheimtext
C
an
H
.
d
ed
Z
p
und erhält so den
H
erhält
C
, berechnet die Potenz
C
=
N
=
N
in
N
Klartext
.
Beispiel
Gegeben ist die Primzahl
p
=
(
)=
=
257. Wegen ggT
29, 256
1 können wir
e
29
wählen. Wir bestimmen
d
mit dem euklidischen Algorithmus:
=
·
+
=
−
256
8
29
24
1
5
4
29
=
1
·
24
+
5
=
5
·
5
−
24
=
·
+
=
−
·
+
·
24
4
5
4
6
24
5
29
=
·
+
5
1
4
1.
=
53
·
29
−
6
·
256 .
=
Damit ist
d
53.
Die Schlüsselerzeugung ist hiermit abgeschlossen.
P
hat den geheimen Schlüssel
e
N∈
Z
257
und
H
hat die (geheime)
=
29 zum Verschlüsseln eines Klartextes
=
Zahl
d
53 zum Entschlüsseln eines erhaltenen Ge
h
eimtextes.
Der Sender
P
verschlüsselt etwa den Klartext
N
=
3:
3
29
C
=
=
69 .
C
=
Der Empfänger
H
entschlüsselt den erhaltenen Geheimtext
69:
69
53
d
C
=
=
3.
=
Bereits dieses einfache Beispiel mit der kleinen Primzahl
p
257 verdeutlicht ein
Problem des Verfahrens - die rechenaufwändige Exponentiation. Im folgenden
Abschnitt zeigen wir, wie diese Aufgabe effizient gelöst werden kann.
Bemerkung
Das RSA-Verschlüsselungsverfahren, das wir in Kapitel 7 ausführlich beschrei-
ben werden, ist eine Chiffre vom hier beschriebenen
Exponentiationstyp
. Dabei
