Cryptography Reference
In-Depth Information
9 Die Verfahren von Diffie und
Hellman, ElGamal und Rabin
Symmetrische Verschlüsselungsverfahren sind im Allgemeinen effizienter als
Public-Key-Verfahren. Eine Möglichkeit, dies auszunutzen, aber dennoch das
Problem der Schlüsselverwaltung zu bewältigen, haben wir bereits unter dem
Stichwort
Hybridverfahren
kennengelernt: Chiffriere eine Nachricht mit einem (ef-
fizienten) symmetrischen Verfahren und den (kurzen) Schlüssel zum Dechiffrie-
ren dieser Nachricht mit einem Public-Key-Verfahren, und sende dann diese bei-
den Teile an den Empfänger (siehe Abschnitt 7.1.5).
Im vorliegenden Kapitel besprechen wir eine weitere trickreiche Variante, einen
Schlüssel über einen unsicheren Kanal auszutauschen, um dann die Kommuni-
kation mit einem symmetrischen Verfahren sichern zu können.
Beim
Diffie-Hellman-Schlüsselaustausch
wird ein geheimer Schlüssel über eine öf-
fentliche, nicht gesicherte Leitung ausgetauscht. Obwohl ein Angreifer den Aus-
tausch von
Teilen
des geheimen Schlüssels beobachten kann, ist er im Allgemei-
nen nicht in der Lage, aus diesen
Teilen
den Schlüssel selbst zu erzeugen. Die
Sicherheit des Verfahrens ist mit der Schwierigkeit des diskreten Logarithmen-
problems verbunden.
Das
ElGamal-Verschlüsselungsverfahren
ist ein Public-Key-Verfahren, das mit dem
Schlüsselaustausch von Diffie-Hellman zusammenhängt. Daher ist auch die Si-
cherheit des ElGamal-Verfahrens an die Schwierigkeit des diskreten Logarith-
menproblems geknüpft. Während das Public-Key-Verfahren RSA in der Halb-
gruppe
Z
n
realisiert ist, lässt sich das ElGamal-Verfahren in beliebigen endlichen
abelschen Gruppen implementieren. Das ElGamal-Verfahren auf einer
elliptischen
Kurve
- das ist eine endliche abelsche Gruppe (siehe Kapitel 13) - ist die derzeit
wohl bestuntersuchte Alternative zum RSA-Verfahren.
Als weiteres Public-Key-Verfahren stellen wir in diesem Kapitel das
Rabin-Ver-
fahren
vor. Der öffentliche Schlüssel
n
dieses Verfahrens ist ein Produkt zweier
Primzahlen. Das Rabin-Verfahren findet kaum praktische Anwendung, aber es
ist dafür von theoretischem Interesse: Es lässt sich zeigen, dass das Brechen des
Rabin-Verfahrens genauso schwierig ist wie das Faktorisieren von
n
. Beim RSA-
Verfahren ist dies nicht bekannt.
9.1 Der Diffie-Hellman-Schlüsselaustausch
Es sei
p
eine Primzahl. Wir beschreiben den
Diffie-Hellman-Schlüsselaustausch
in
der multiplikativen zyklischen Gruppe
Z
p
der Ordnung
p
−
1 (siehe Satz 6.12).