ElGamal

Algorithmus 7.1 (ElGamal-Signatur)  

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. Signatur

   A führt die folgenden Schritte durch:

   • wähle eine Zufallszahl $k$ mit $1<k<r$;
   • berechne $\rho \leftarrow k\cdot h$
   • berechne den Hash-Wert $i\left( M\right)$ der Nachricht $M$;
   • berechne $s\leftarrow k^{-1}\left( i\left( M\right) -ag\left( \rho \right) \right) \mod n$.
   As Signatur ist $\left( \rho ,s\right)$.

3. Verifikation

   B führt die folgenden Schritte durch:

   • besorge As authentischen, öffentlichen Schlüssel;
   • berechne $v_{1}\leftarrow g\left( \rho \right) \cdot \alpha +s\cdot \rho$;
   • berechne $v_{2}\leftarrow i\left( M\right) \cdot h$;
   B akzeptiert die Signatur $S$ genau dann, wenn $v_{1}=v_{2}$ ist.

Die Verifikation funktioniert folgendermaßen:

$$v_{1} = g\left( \rho \right) \cdot \alpha +s\cdot \rho$$

$$= ag\left( \rho \right) \cdot h+k^{-1}\left( i\left( M\right) -ag\left( \rho \right) \right) \cdot k\cdot h$$

$$= i\left( M\right) \cdot h$$

$$= v_{2}$$

Um eine Signatur zu fälschen, muß $a=\log _{h}\alpha$ bekannt sein, alternativ muß $k=\log _{h}\rho$ aus einer Signatur rekonstruiert werden, um $a$ zu berechnen:

$$s \equiv k^{-1}\left( i\left( M\right) -ag\left( \rho \right) \right) \mod n$$

$$\rightarrow \, a \equiv \frac{i\left( M\right) -ks}{g\left( \rho \right) }\mod n$$

Die ElGamal-Signatur basiert daher auch auf dem DLP. Für die ElGamal-Signatur gelten dieselben Hinweise, wie für die ElGamal-Verschlüsselung: Die Signatur ist etwas doppelt so lang, wie der Text, jedoch gilt auch hier, daß üblicherweise nur kleine Mengen an Text (nämlich der Hash-Wert der Nachricht $M$) signiert werden, so daß dies in den meisten Fällen kein Problem ist.

Die Verwendung einer Hash-Funktion ist aber ohnehin aus Gründen der Sicherheit zwingend erforderlich: Wird bei dem Signatur-Verfahren keine Hash-Funktion auf die Nachricht $M$ angewendet, dann wird in Schritt $\left( 2\right)$ $s$ durch $k^{-1}\left( M-ag\left( \rho \right) \right) \mod n$ berechnet. In diesem Fall kann ein Angreifer E eine beliebige Signatur ohne Kenntnis des geheimen Schlüssels $a$ erzeugen, indem E folgende Schritte (anstelle des 2. Schrittes) ausführt:

• wähle zwei Zufallszahlen $u$ und $v$, so daß $0<u,v<n$ und $v$ kein Teiler von $n$ ist;
• berechne $\rho \leftarrow u\cdot h+v\cdot \alpha =\left( u+av\right) \cdot h$;
• berechne $s\leftarrow -g\left( \rho \right) v^{-1}\mod n$

Das Paar $S=\left( \rho ,s\right)$ ist eine gültige Signatur für $M\equiv su\mod n$, denn die Verifikation ergibt

$$v_{1} = g\left( \rho \right) \cdot \alpha +s\cdot \rho$$

$$= ag\left( \rho \right) \cdot h+\left( s\left( u+av\right) \right) \cdot h$$

$$= \left( ag\left( \rho \right) +su+sav\right) \cdot h$$

$$= \left( ag\left( \rho \right) +su-ag\left( \rho \right) \right) \cdot h$$

$$= \left( su\right) \cdot h$$

$$= M\cdot h$$

$$= v_{2}$$

Da $u$ und $v$ mehr oder weniger beliebig ausgewählt werden können, kann praktisch für jede beliebige Nachricht eine gültige Signatur erzeugt werden. Dies wird verhindert, indem anstelle von $M$ der Hash-Wert $i\left( M\right)$ signiert wird; hier ist es offensichtlich von Bedeutung, daß das Urbild $i\left( M\right)$ nicht effizient berechnet werden kann.

Außerdem muß für jede Signatur eine neue Zufallszahl $k$ gewählt werden, andernfalls kann ein Angreifer mit hoher Wahrscheinlichkeit $k$ und den geheimen Schlüssel $a$ aufdecken: Seien $S_{1}=\left( \rho _{1},s_{1}\right)$ und $S_{2}=\left( \rho _{2},s_{2}\right)$ die Signaturen von $M_{1}$ und $M_{2}$. Dann ist $\rho _{1}=\rho _{2}=\rho =k\cdot h$ und

$$s_{1} \equiv k^{-1}\left( i\left( M_{1}\right) -ag\left( \rho \right) \right) \mod n,$$

$$s_{2} \equiv k^{-1}\left( i\left( M_{2}\right) -ag\left( \rho \right) \right) \mod n.$$

Es folgt $\left( s_{1}-s_{2}\right) k\equiv i\left( M_{1}\right) -i\left( M_{2}\right) \mod n$, und wenn $\left( s_{1}-s_{2}\right) \mod n$ invertierbar ist, dann ist

$$k\equiv \frac{i\left( M_{1}\right) -i\left( M_{2}\right) }{s_{1}-s_{2}}\mod n.$$

Wenn $g\left( \rho \right) \mod n$ invertierbar ist, dann kann daraus $a\equiv \frac{i\left( M\right) -ks}{g\left( \rho \right) }\mod n$ für $M=M_{1}$ oder $M=M_{2}$ berechnet werden.

Die Wahl eines unterschiedlichen $k$ für jede Signatur führt nebenbei auch dazu, daß bei ansonsten gleichen Parametern ein Text unterschiedliche Signaturen erzeugen kann.