Cryptography Reference
In-Depth Information
Gegeben ist die Situation des ElGamal-Verschlüsselungsverfahren, es sei
)
der öffentliche Schlüssel und
a
der geheime Schlüssel. Durch eine Modifikation
des Verschlüsselungsverfahrens erhalten wir das
ElGamal-Signaturverfahren
.
(
p
,
g
,
A
N∈
Z
p
:
Signieren eines Datensatzes.
E
signiert ein Dokument
E
wählt ein zufälliges
k
∈{
2, . . . ,
p
−
2
}
mit ggT
(
k
,
p
−
1
)=
1.
g
k
und eine Lösung
s
der Kongruenzgleichung
=
E
berechnet
R
≡N−
(
(
−
))
kX
aR
mod
p
1
.
(dass diese Kongruenzgleichung lösbar ist, folgt aus der Teilerfremdheit von
k
und
p
−
1, vgl. Korollar 4.19)
E
schickt das
signierte
Dokument
(
N
,
R
,
s
)
an einen oder mehrere Teilneh-
mer
T
.
Verifikation der Signatur.
Jeder Teilnehmer
T
kann die Signatur von
E
mittels
des öffentlichen Schlüssels von
E
verifizieren. Dazu berechnet
T
zum einen
g
N
und zum anderen
A
R
R
s
. Diese beiden Größen müssen übereinstimmen, da gilt:
A
R
R
s
g
aR
g
ks
g
aR
+
ks
g
N
.
=
=
=
Da nur
E
den geheimen Schlüssel
a
kennt, kann man dies als einen Beweis dafür
auffassen, dass das Dokument
N
von
E
stammt.
Beispiel
Wir wählen die Primzahl
p
Z
p
=
19, den Erzeuger
g
=
2 der Gruppe
und
=
als geheimen Sc
h
l
üs
sel
a
13. Damit ergibt sich der öffentlichen Schlüssel
(
p
,
g
,
A
)=(
19, 2, 3
)
.
Mit der Nachricht
N
=
5 und der zufälligen Wahl
k
=
7
2
7
ergibt sich
R
=
=
14. Als Lösung der Kongruenzgleichung
7
X
≡
5
−
13
·
14
≡
3
(
mod 18
)
erhalten w
ir
s
=
3. Somit ist dann
(
N
,
R
,
s
)=(
5, 14, 3
)
das signierte Dokument,
(
)
dabei ist
14, 3
die Signatur. Zur Verifikation bestimmt man:
14
3
3
14
2
5
A
R
R
s
13 und
g
N
=
=
·
=
=
13 .
Wegen
A
R
R
s
g
N
wird das signierte Dokument akzeptiert.
=
Die Signatur wird nicht akzeptiert, falls nicht 1
≤
R
≤
p
−
1 gilt. Es könnte Betrug
vorliegen, wie wir gleich zeigen werden.
