Cryptography Reference
In-Depth Information
9.2.3 Entschlüsselung
Erhält der Empfänger
E
vom Sender
G
den Geheimtext
, so berechnet
er mit seinem geheimen Schlüssel
a
das Element
B
−
a
c
. Es gilt nämlich wegen
B
C
=(
B
,
c
)
g
b
,
c
A
b
g
a
:
=
=
N
=
und
A
B
−
a
c
g
−
ab
A
b
g
−
ab
g
ab
=
N
=
N
=
N
,
N∈
Z
p
und damit erhält
E
den Klartext
zurück.
Beispiel
Es sei
p
3 ist eine Primitivwurzel modulo 17. Der Empfän-
ger
E
w
äh
lt als geheimen Schlüssel
a
=
17. Das Element
g
=
=
3 und hat somit den öffentlichen Schlüssel
.
Der Sender
G
verschl
ü
s
s
elt den Klartext 5
(
17, 3, 10
)
∈
Z
17
. Er wählt
b
=
2 und erhält den
Geheimtext
, den er an
E
send
e
t.
Der Empfänger
E
erhält nun wegen 9
−
3
(
B
,
c
)=(
9, 7
)
Z
17
durch Berechnen von
=
8in
9
−
3
·
7
=
8
·
7
=
5
den Klartext 5 zurück.
Man kann das ElGamal-Verfahren auf beliebige endliche zyklische Gruppen
G
verallgemeinern. Wir werden das Verfahren in Kapitel 14 für zyklische
Untergruppen von elliptischen Kurven erneut schildern.
=
g
9.2.4 Zur Sicherheit des ElGamal-Verfahrens
Wir versetzen uns in die Situation eines Angreifers: Ein Angreifer, der den Aus-
tausch einer verschlüsselten Nachricht beobachtet, kennt die Größen
g
,
g
a
,
g
b
,
c
g
ab
=
N
.
Kann der Angreifer
A
das Diffie-Hellman-Problem lösen, d. h.,
A
kann aus
g
,
g
a
und
g
b
das Element
g
ab
bestimmen, so kann er auch das ElGamal-Verfahren
brechen. Er berechnet
g
−
ab
c
. Kann andererseits
A
das ElGamal-Verfahren
N
=
g
ab
brechen, d. h.,
A
kann
bestimmen, so kann er
auch das Diffie-Hellman-Problem lösen. Er berechnet
g
ab
N
aus der Gleichung
c
=
N
=
N
−
1
c
. Damit ist
gezeigt: Das Brechen des ElGamal-Verfahrens ist algorithmisch äquivalent zum
Lösen des Diffie-Hellman-Problems.
Das Diffie-Hellman-Problem kann gelöst werden, wenn man diskrete Logarith-
men berechnen kann. Um gegen die bekannten Algorithmen zum Berechnen
der diskreten Logarithmen gewappnet zu sein, sollte die Primzahl, die beim
ElGamal-Verfahren in
Z
p
benutzt wird, etwa von der Größenordnung 1 024 Bit
sein. Wir werden in Kapitel 10 Algorithmen zum Berechnen diskreter Logarith-
men besprechen.
