Cryptography Reference
In-Depth Information
Aus
de
r Kenntnis von
g
und
c
=
a
·
g
kann leicht der diskrete Logarithmus
a
=
Log
g
c
berechnet werden. Es ist hierzu nur die Kongruenzgleichung:
Xg
≡
(
)
c
mod
n
zu lösen. Dies ist mit mithilfe des euklidischen Algorithmus aus Satz 4.10 effizient
machbar: Man bestimme Zahlen
x
,
y
∈
Z
mit
=
(
)=
+
1
ggT
g
,
n
xg
yn
.
=(
)
+
≡
(
)
=
Es gilt dann
c
xc
. Folglich ist nur
die ganze Zahl
x
zu bestimmen, um den diskreten Logarithmus
a
zu erhalten.
Wegen ggT
xc
g
ycn
, also
ag
c
mod
n
mit
a
:
(
)=
+
g
,
n
1 ist
a
n
Z
nach Korollar 4.19 die Menge aller Lösungen.
Bemerkung
Man erkennt hier, dass es nicht die
Struktur
der Gruppe ist, die das DLP schwie-
rig macht - alle zyklischen Gruppen derselben Ordnung sind isomorph. Es ist
vielmehr die Art der
Beschreibung
, die das bewirkt.
9.2 Das ElGamal-Verschlüsselungsverfahren
Das ElGamal-Verfahren ist verwandt mit dem Diffie-Hellman-Verfahren. Aber es
ist ein asymmetrisches Verschlüsselungsverfahren und kein Schlüsselaustausch.
Es gibt einen öffentlichen Schlüssel
(
)
p
,
g
,
A
und einen geheimen Schlüssel
a
.
Wir schildern die Funktionsweise.
C
=(
B
,
c
)
G
E
(
)
p
,
g
,
A
9.2.1 Schlüsselerzeugung
Gegeben seien eine Primzahl
p
, eine Primitivwurzel
g
modulo
p
und ein festes
a
g
a
. Beim
ElGamal-Verschlüsselungsver-
∈{
2, . . . ,
p
−
2
}
. Wir setzen
A
:
=
fahren
sind
•
(
p
,
g
,
A
)
der öffentliche Schlüssel;
g
a
) der geheime Schlüssel des Empfängers
E
.
•
a
(das
a
mit
A
=
9.2.2 Verschlüsselung
Der Sender
G
sendet an
E
eine verschlüsselte Nachricht. Dazu besorgt sich
G
den
öffentlichen Schlüssel
N∈
Z
p
der Klartext.
(
p
,
g
,
A
)
von
E
. Es sei
∈{
−
}
G
wählt zufällig eine Zahl
b
2, . . . ,
p
2
.
g
b
∈
Z
p
und
c
:
A
b
N∈
Z
p
.
=
=
G
berechnet
B
:
C
=(
)
G
sendet den Geheimtext
B
,
c
an
E
.
