Elgamal-Signaturverfahren
Elgamal-Signaturverfahren

== Vorbereitung ==
Wie bei allen Verfahren mit diskretem Logarithmus arbeitet man in einer abelschen Gruppe ''G'' mit einem Erzeuger ''g''. In der Originalversion des Verfahrens ist diese Gruppe eine Untergruppe großer Primordnung  der multiplikativen Gruppe  des Restklassenkörpers modulo einer Primzahl . Es ist jedoch genauso möglich, das Verfahren auf Grundlage einer anderen endlichen Gruppe zu realisieren. Insbesondere kann zu diesem Zweck eine elliptische Kurve benutzt werden.
In der Praxis heißt das, dass man eine Primzahl ''q'' derart wählt, dass ''p = 2q+1'' ebenfalls eine Primzahl ist (mittels zufälliger Wahl von q und Testen von p, wiederholen bis eine gefunden wird). Dann erzeugen alle Elemente (außer 1 und −1) von  entweder die gesamte Gruppe (der Ordnung ), oder die Untergruppe der Ordnung ''q'', und man wählt eines als ''g'', welches die Untergruppe (multiplikativ) erzeugt, üblicherweise die Restklasse von 2 oder 3 in .
Diese Auswahl von ''p'', ''q'' und ''g'' kann für alle Teilnehmer gemeinsam getroffen werden. Die Größe von ''q'' bestimmt die Sicherheit des Verfahrens. Außerdem muss eine kollisionsresistente Hashfunktion ''H'' fixiert werden.