DSA

Der größte Teil der Berechnungen beim ElGamal-Signaturverfahren wird für die Exponentiationen (d.h. skalare Multiplikationen) verwendet. Die drei Exponentiationen bei der Verifikation lassen sich durch die Methode der ,,simultanen Exponentiation'' durch einige Verbesserungen zu einer einzigen Exponentiation zusammenfassen. Eine weitere Möglichkeit besteht darin, das Hamming-Gewicht der Exponenten (d.h. der skalaren Faktoren) zu begrenzen; genau dies wird bei DSA (Digital Signature Algorithm) gemacht:

Algorithmus 7.2 (verallgemeinerte DSA-Signatur)  

1. Schlüsselpaar-Erzeugung

   A führt die folgenden Schritte durch:

   • wähle eine Primzahl $q$, so daß $2^{159}<q<2^{160}$ ist;
   • wähle eine Gruppe $G$ der Ordnung $n$, so daß $q\vert n$ gilt; bestimme ein Element $h\in G$ mit Primordnung $q$
   • wähle eine Zufallszahl $a$ mit $1<a<q$;
   • 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<q$;
   • 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 q$
   As Signatur von $M$ ist $\left( \rho ,s\right)$.

3. Verifikation

   B führt die folgenden Schritte durch:

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

Die Verifikation funktioniert folgendermaßen:

$$v = \left( i\left( M\right) w\right) \cdot h+\left( g\left( \rho \right) w\right) \cdot \alpha$$

$$= \left( i\left( M\right) s^{-1}\right) \cdot h+\left( g\left( \rho \right) s^{-1}a\right) \cdot h$$

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

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

$$= k\cdot h$$

$$= \rho$$

DSA ist mit $G=\mathbb{Z}_{p}^{*}$ Teil des DSS (Digital Signature Standard), und da DSA ein enger Verwandter der ElGamal-Signatur ist, gelten die Sicherheitshinweise für ElGamal auch für DSA.

Angenommen, das DLP ist für $q\sim 2^{160}$ nicht mehr effizient lösbar, dann können wir einen großen Vorteil des DSA über elliptischen Kurven (EC DSA) gegenüber RSA und allgemeinem DSA feststellen, weil der Schlüssel und die Signaturgrößen bei gleicher Sicherheit viel kleiner sind:

System	Systemparameter	öffentlicher Schlüssel	privater Schlüssel	Signaturgröße
RSA	-	1088	2048	1024
DSA	2208	1024	160	320
EC DSA	481	161	160	320

Vergleich der Schlüssel- und Signaturgrößen einer 2000 Bit langen Nachricht