ElGamal

Das bekannteste Public-Key-Verfahren, welches auf dem DLP basiert, ist das Verschlüsselungsverfahren nach T. ElGamal:

Algorithmus 6.5 (ElGamal-Verschlüsselung)  

1. Schlüsselpaar-Erzeugung

   A führt die folgenden Schritte durch:

   • wähle eine Gruppe $G$ der Ordnung $n$ und ein Element $h\in G$ mit Primordnung $r$;
   • wähle eine Zufallszahl $a$ mit $1<a<r$;
   • berechne $\alpha \leftarrow a\cdot h$
   As öffentlicher Schlüssel ist $\left( G,h,\alpha \right)$, As geheimer Schlüssel ist $a$.

2. Verschlüsselung

   B führt die folgenden Schritte durch:

   • besorge As authentischen öffentlichen Schlüssel;
   • kodiere die Nachricht $M$ als Element $\mu$ von $G$;
   • wähle eine Zufallszahl $k$ mit $1<k<r$;
   • berechne $\rho \leftarrow k\cdot h$;
   • berechne $\beta \leftarrow \mu +k\cdot \alpha$.
   $C=\left( \rho ,\beta \right)$ ist die Verschlüsselung von $M$.

3. Entschlüsselung

   A führt die folgenden Schritte durch:

   • berechne mit dem geheimen Schlüssel $a$ die Nachricht $\mu =\beta -a\cdot \rho$;
   • stelle $M$ aus $\mu$ wieder her.

Die ElGamal-Verschlüsselung basiert tatsächlich auf dem DLP, denn um $\mu$ aus $\rho$ und $\beta$ zu rekonstruieren, muß $a=\log _{h}\alpha$ bekannt sein.

Ein Nachteil der ElGamal-Verschlüsselung besteht in der ,,Ciphertext-Expansion'', der Kryptotext $C=\left( \rho ,\beta \right)$ ist nämlich doppelt so lang, wie der Klartext $\mu$. Da Public-Key-Verfahren üblicherweise nur auf kleinen Mengen von Klartext angewendet werden (z.B. auf einen Session-Key für symmetrische Verschlüsselung), ist dies meistens nicht kritisch. Andererseits ist die Text-Expansion die Folge einer anderen, vorteilhaften Eigenschaft: Da bei jeder Verschlüsselung für $k$ eine (andere) Zufallszahl gewählt wird, werden bei verschiedenen Verschlüsselungen mit ansonsten gleichen Parametern gleiche Klartexte auf unterschiedliche Kryptotexte abgebildet. Diese Eigenschaft erschwert den ,,Wörterbuch-Angriff'', bei dem große Mengen an Klartext und korrespondierendem Kryptotext vorausberechnet werden. Mithin ist es kritisch, daß für jede Verschlüsselung ein anderes $k$ gewählt wird. Um das zu sehen, beachte man, daß $\beta _{1}-\beta _{2}=\mu _{1}-\mu _{2}$ ist, wenn $k$ konstant gewählt wird; wenn einem Angreifer bereits z.B. $\mu _{1}$ bekannt ist, kann er daraus $\mu _{2}$ berechnen.