Cryptography Reference
In-Depth Information
4.4.2
Digitale Signatur und Verifikation nach ElGamal
Falls Alice eine Nachricht m (oder den Schlüsselwert ) digital signieren möchte, dann benutzt
sie dazu ihren eigenen privaten Schlüssel d
A
. Für die Verifikation der digitalen Signatur, z.B.
durch Bob, muss er den öffentlichen Schlüssel e
A
von Alice benutzen. Dabei muss er sicher
sein, dass der öffentliche Schlüssel e
A
wirklich zu Alice gehört. Der Übersichtlichkeit halber
wird der Index A im Folgenden weggelassen: d=d
A
, e=e
A
.
Digitales Signieren einer Nachricht
Das Verfahren erscheint auf den ersten Blick etwas kompliziert. Die Unterzeichnerin wählt für
jede Nachricht neu eine zu (p1) teilerfremde Zufallszahl r.
(4.4-8)
Sie berechnet bezüglich des Moduls (p1) das multiplikativ inverse Element r
1
, das wegen
ggT(r, p1)=1 auch existiert. Dazu eignet sich der erweiterte Euklidische Algorithmus (Kap.
2.1.3.1). Weiter berechnet sie aus der gewählten Zufallszahl r einen „Nachrichtenbezeichner“
.
r
[1, p
1]
wobei
ggT(r, p
1)
1
1
r
r
1
(mod p
1)
(Zufallszahl)
(4.4-9)
r
3
g
mod p
(Nachrichtenbezeichner)
(4.4-10)
Aus der folgenden Kongruenz mod (p1) berechnet sie ein „Signaturelement“ s. Die Kon-
gruenz kann nach s aufgelöst werden.
dr s
3
m(
p )
(4.4-11)
3
1
s
((m
d
) r
) mod p
1
(Signaturelement)
(4.4-12)
In das Signaturelement s sind eingeflossen: die Nachricht m, der private Schlüssel d und die
Zufallszahl r als Inverse r
1
und als Nachrichtenbezeichner .
Die digital signierte Nachricht besteht aus dem Klartext der Nachricht, dem Nachrichtenbe-
zeichner und dem Signaturelement s.
signierte Nachricht :
(m,
3
, s)
(4.4-13)
Verifizieren einer signierten Nachricht
Für die Prüfung einer signierten Nachricht benötigt der Empfänger, z.B. Bob, den öffentlichen
Schlüssel e der Unterzeichnerin. Er muss sich sicher sein, dass der öffentliche Schlüssel e
wirklich z.B. zu Alice gehört. Diese Sicherheit kann er durch ein Zertifikat von einer PKI
erhalten (PKI, Public Key Infrastructure, Kap. 6.1.1 und 6.1.1.2).
Der Prüfer verifiziert die folgende Kongruenz:
m s
ge
3
3
(
d )
(4.4-14)
Darin ist g das öffentlich bekannte Generatorelement nach (4.4-1). Die Elemente m, und s
entnimmt der Prüfer der empfangenen, signierten Nachricht (4.4-13). Den öffentlichen Schlüs-
sel e der Unterzeichnerin muss sich der Prüfer auf getrenntem Wege, z.B. von einer PKI be-
schaffen.
