Asymmetrische Chiffren - Kryptographie und IT-Sicherheit - page 131

4.4 ElGamal-Verfahren

Der Algorithmus wurde von Taber ElGamal 1984 vorgeschlagen [ElG84]. In der Folge wur-
den unterschiedliche Varianten entwickelt. Eine der Varianten, der DSA (Digital Signature
Algorithm) wurde 1991 unter dem Namen DSS (Digital Signature Standard) als Standard ak-
zeptiert [FIPSPUB186]. Davon wird hier eine vereinfachte Version dargestellt.
ElGamal ist ein asymmetrisches Verfahren. Es ermöglicht einerseits digitale Signaturen und
andererseits die vertrauliche Übertragung eines Sitzungsschlüssels (session key). Mathema-
tisch gründet sich das ElGamal-Verfahren auf den diskreten Logarithmus. Allgemein und
öffentlich bekannt sind eine große Primzahl p und eine Basis g aus dem Galois-Körper GF(p).
Die Elemente p und g können für die Schlüssel verschiedener Teilnehmer benutzt werden. Die
Basis g muss Generatorelement *) sein.

g GF(p) g Generatorelement in GF(p)

(4.4-1)

p, g sin d al lg emein und öffentlich

Jeder Teilnehmer wählt individuell einen privaten Schlüssel d und berechnet sich durch Poten-
zierung den zugehörigen öffentlichen Schlüssel e.

d
egm dp e h, d t (4.4-2)

Der Schlüssel (e, g, p) wird veröffentlicht und erforderlichenfalls durch ein Zertifikat beglau-
bigt (Kap. 6.1.1.2). Die Ermittlung des privaten Schlüssels aus dem öffentlichen Schlüssel ist
bei genügend großem Modul p nicht durchführbar. Die inverse Funktion von (4.4-2) ist als
diskreter Logarithmus eine Einwegfunktion.
Die Sicherheit des ElGamal-Verfahrens hängt von der Schwierigkeit ab, den diskreten Loga-
rithmus (DL) zu ermitteln (vgl. Kap. 4.1.4). Die besten Algorithmen für die Berechnung des
diskreten Logarithmus sind für manche Werte des Moduls p ähnlich effektiv wie die Faktori-
sierung großer Zahlen. Deshalb werden für den Modul p bei ElGamal ähnlich große Stellen-
zahlen vorgeschlagen wie bei RSA: (512), 768, 1024, 2096 und 4096 Bit.
*) Anmerkung zu „Generator-Element g“: Ein Generator-Element hat die Eigenschaft, dass jedes Ele-
ment aus [1, p1] als Potenz von g mod p darstellbar ist (vgl. Tab. 4-1 in Kap. 4.1.1). Bei großen Moduln
p ist fast jedes zweite Element ein Generatorelement. Ob ein als Zufallszahl gewähltes Element Genera-
torelement ist, kann durch Tests entschieden werden. Für den Sonderfall, dass die Primzahl p sich aus
p=2·q+1 zusammensetzt (q=prim), lautet der Test: Es ist g genau dann ein Generatorelement, falls beide
Bedingungen erfüllt sind: g 2 mod p1 und g q mod p1. Die Testaussage kann an dem Beispiel von Tab. 4-
2 in Abschn. 4.1.2.4 nachvollzogen werden. Weiterführendes findet sich in [Bu04] und [BNS05].

4.4.1 Schlüsselvereinbarung nach ElGamal
Bei ElGamal werden die beiden Schlüssel eines Paares mit e und d bezeichnet, obwohl sie
nicht direkt zum Verschlüsseln (encode) oder Entschlüsseln (decode) benutzt werden. Falls
Alice an Bob einen Sitzungsschlüssel übermitteln möchte, dann benutzt sie den öffentlichen
Schlüssel e B von Bob. Nur Bob hat Zugriff auf den zugehörigen privaten Schlüssel d B . Der
Übersichtlichkeit halber wird der Index B im Folgenden weggelassen: e=e B , d=d B .