Digitale Signaturen - Kryptografie - page 205

uns zwei davon anschauen: ElGamal und der Digital Signature Algorithm (DSA).
Weitere DLSSs, auf die ich nicht näher eingehen werde, sind am Ende dieses
Unterkapitels aufgeführt.

12.3.1 ElGamal-Verfahren

Das einfachste DLSS ist das von Taher ElGamal entwickelte ElGamal-Verfahren
[ElGama]. Dieses wird zwar in seiner ursprünglichen Form in der Praxis so gut
wie nie eingesetzt, es bildet jedoch die Basis des DSA-Verfahrens, zu dem wir spä-
ter kommen.

Funktionsweise des ElGamal-Verfahrens

Für eine ElGamal-Signatur benötigen wir erst einmal eine große Primzahl p und
eine Zahl g , die ein Generator von Z( p ,·) ist (das alles kommt Ihnen hoffentlich
noch von Diffie-Hellman bekannt vor). Alice, die ihre Nachrichten signieren will,
benötigt einen geheimen Schlüssel x < p , aus dem sie den öffentlichen Schlüssel
g x (mod p ) berechnet. Diesen öffentlichen Schlüssel lässt Alice Bob zukommen, er
benötigt ihn zum Verifizieren von Alices Signaturen. Immer wenn Alice nun eine
Nachricht m unterschreiben will, berechnet sie eine Zufallszahl y , die zu p -1 rela-
tiv prim ist (also außer 1 keinen gemeinsamen Teiler hat). Aus y berechnet sie die
Zahl r = g y (mod p ) und stellt anschließend folgende Gleichung auf:

m = x · r + y · s (mod p -1)

Hierbei sind x , y , m und g bekannt. Die neu eingeführte Variable s ist von diesen
Größen abhängig und kann von Alice durch eine algebraische Umformung
berechnet werden. Die beiden Zahlen r und s bilden zusammen die digitale Signa-
tur zur Nachricht m . Wie Bob die Unterschrift verifizieren kann, sieht man, wenn
man die obige Gleichung als Exponent zur Basis g nimmt. Dabei muss der in
Abschnitt 11.1.1 beschriebene Satz beachtet werden, der besagt, dass a 1 (mod ϕ (n)) =
a (mod n ) gilt, wenn a und n natürliche Zahlen ( a < n ) sind. Aus diesem folgt, dass
a k (mod ϕ (n)) = a k (mod n ) gilt ( k ist eine natürliche Zahl). Nun ergibt sich:

m = x · r + y · s (mod p -1)
=> g m = g x·r + y·s (mod p-1)
=> g m = g x·r + y·s (mod p ) (dies ergibt sich aus dem genannten Satz)
=> g m = g x·r · r s (mod p )

In der letzten Gleichung sehen Sie, dass Bob beide Seiten berechnen kann, ohne
die geheimen Zahlen x und y zu kennen. Er benötigt dazu lediglich die ihm
bekannten Zahlen g , m , den öffentlichen Schlüssel g x sowie die Variablen r und s,
die ja die Signatur bilden. Genau mit dieser Gleichung verifiziert Bob die digitale