Elgamal-Verschlüsselungsverfahren

Das Elgamal-Kryptosystem (auch al-Dschamal-Kryptosystem) ist ein Schema zur Verschlüsselung, das auf dem mathematischen Problem des diskreten Logarithmus beruht. Elgamal ist ein asymmetrischer Verschlüsselungsalgorithmus aufbauend auf der Idee des Diffie-Hellman-Algorithmus (s. dort), der mit diesen diskreten Logarithmen arbeitet.

Elgamal kann sowohl zur Signaturerzeugung als auch zum Verschlüsseln verwendet werden. Elgamal unterliegt keinem Patent.

Wie das Elgamal-Kryptosystem arbeitet auch das Elliptische-Kurven-Kryptosystem auf diskreten Logarithmen.

Geschichte

Das Elgamal-Kryptosystem wurde 1985 von Taher Elgamal (Tahir al-Dschamal) entwickelt.

Schlüsselerzeugung

Wie alle asymmetrischen Kryptosysteme verwendet auch das Elgamal-Kryptosystem einen öffentlichen und einen geheimen Schlüssel. Der öffentliche dient später der Verschlüsselung und kann veröffentlicht werden, während der geheime nur den Empfängern der Nachricht bekannt sein darf.

Es folgt nun eine genaue mathematische Beschreibung der Schlüsselerzeugung:

Zur Schlüsselerzeugung benötigt man eine Primzahl $p$, sodass $p-1$ einen großen Primfaktor $q$ besitzt. Typischerweise wird $q$ vorgewählt und man errechnet $p=2q+1$ und prüft dann die Primzahleigenschaft von $p$ (Sophie-Germain-Primzahl). Außerdem benötigt man eine Primitivwurzel $g\,mod\,p$ der Ordnung $q$ und ein zufälliges, gleichverteiltes $a\in \{0,...,p-2\}$. Man berechne außerdem $A=g^{a}\,mod\,p$. Hierbei steht Fehler beim Parsen (Konvertierungsfehler. Der Server („/media/api/rest_“) hat berichtet: „Cannot get mml. TeX parse error: Extra close brace or missing open brace“): {\displaystyle \mod } für den Modulo-Operator. Für eine Erläuterung solcher Kongruenzbedingungen siehe Modulo.

Der öffentliche Schlüssel besteht nun aus dem Tripel $(p,g,A)$. Der geheime Schlüssel entspricht $a$.

Seien beispielhaft $p=17$ und $a=6$. Als Primitivwurzel sei $g=3$ gewählt. Man berechne $A=g^{a}\,mod\,p=3^{6}\,mod\,17=15$.

Somit ergibt sich im Beispiel der öffentliche Schlüssel $(p=17,g=3,A=15)$ und der geheime Schlüssel $a=6$.

Verschlüsselung

Datei:Verschlüsselung (asymmetrisches Kryptosystem).png

Verschlüsselung

Man kann sich eine Verschlüsselung so vorstellen, dass ein Text, etwa aus einem Buch, durch ein geeignetes Verfahren in eine Zeichenfolge gewandelt wird, die nicht mehr ohne größeren Aufwand lesbar ist.

Nebenstehende Abbildung veranschaulicht die Verschlüsselung von Klartexten mit asymmetrischen Kryptosystemen wie dem in diesem Artikel beschriebenen. Ein Klartext wird in einen Geheimtext unter Verwendung eines öffentlichen Schlüssels verwandelt. Zur Handhabung im Rechner verwendet man jedoch eine Folge von Zahlen, in die sich ein solcher Textabschnitt jedoch leicht verwandeln lässt.

Für das Elgamal-Kryptosystem wird nachfolgend dieser Prozess auf mathematischem Weg präzisiert:

Der Klartext $m$ ist aus der Menge $\{0,...,p-1\}$ zu wählen. Man wähle nun zufällig ein $b\in \{1,...,p-2\}$. Nun berechne man $B=g^{b}\,mod\,p$ und $c=A^{b}m\,mod\,p$. Der Geheimtext besteht nun aus dem Paar $(B,c)$.

In unserem Beispiel sei der Klartext $m=9$. Willkürlich sei $b=5$ gewählt. So berechne sich $B=g^{b}\,mod\,p=3^{5}\,mod\,17=5$ und $c=A^{b}m\,mod\,p=1$. Somit ergibt sich der Geheimtext $(B=5,c=1)$.

Entschlüsselung

Entschlüsselung

Auch die Entschlüsselung in asymmetrischen Kryptosystemen im Allgemeinen und im Elgamal-Kryptosystem im Speziellen ist nebenstehend in einer Abbildung dargestellt. Der zuvor durch Verschlüsselung entstandene Geheimtext wird unter Verwendung des geheimen Schlüssels wieder in den Klartext gewandelt.

Das genaue mathematische Vorgehen wird nun beschrieben:

Zur Entschlüsselung ist $B^{x}c\,mod\,p$ mit $x=p-1-a$ zu berechnen. Dies lässt sich folgendermaßen veranschaulichen:

$B^{x}c=B^{p-1-a}c$ $\equiv g^{b(p-1-a)}A^{b}m$ $\equiv (g^{p-1})^{b}(g^{a})^{-b}A^{b}m$ $\equiv$ (wegen kleiner fermatscher Satz) $\equiv A^{-b}A^{b}m$ $\equiv m\,mod\,p$.

Im Beispiel gilt $m=B^{p-1-a}c\,mod\,p=5^{10}\cdot 1\,mod\,17=9$.

Bewertung

Effektivität

Momentan kann Elgamal als ein effektives Kryptosystem angesehen werden:

Wer diskrete Logarithmen berechnen kann, der kann Elgamal brechen („knacken“)! Die Umkehrung ist nicht bekannt. Es gibt derzeit jedoch keine effizienten Algorithmen zur Berechnung diskreter Logarithmen. Für genügend große Zahlen sind diese in „annehmbarer“ Zeit daher nicht zu berechnen, das Elgamal-Kryptosystem ist daher heute in endlicher Zeit ebenfalls nicht zu brechen, demnach als sicher einzustufen.

Wer nun das Diffie-Hellman-Problem lösen kann, der kann das Elgamal-Kryptosystem brechen. Wer das Elgamal-Kryptosystem brechen kann, der kann $g^{ab}\,mod\,p$ bestimmen.

Effizienz

Zur Verschlüsselung sind beim Elgamal-Kryptosystem zwei modulare Exponentiationen nötig: $A^{b}\,mod\,p$ und $g^{b}\,mod\,p$. Da diese nachrichtenunabhängig sind, sind sie vorberechenbar und abspeicherbar. Die Folge ist nur noch eine Multiplikation modulo $p$.

Das Verfahren erfordert zur Entschlüsselung eine modulare Exponentiation. Im Gegensatz zum Rabin-Kryptosystem lässt es sich nicht mit dem chinesischen Restsatz beschleunigen.

Literatur

• Johannes Buchmann: Einführung in die Kryptographie, 3., erweiterte Auflage. Springer, Berlin u. a. 2004, ISBN 3540405089
• Dietmar Wätjen: Kryptographie, 1. Auflage. Spektrum Akademischer Verlag, Heidelberg, 2004, ISBN 3827414318