Elgamal-Kryptosystem

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, der mit diesen diskreten Logarithmen arbeitet.

Verwandt mit dem hier beschriebenen Verschlüsselungsverfahren (aber nicht mit diesem identisch) ist das Elgamal-Signaturverfahren. Elgamal unterliegt keinem Patent.

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 Schlüssel dient der Verschlüsselung und kann veröffentlicht werden, während der geheime Schlüssel der Entschlüsselung dient und 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 (manchmal auch "Generator" genannt) $g \, \bmod \, p$ der Ordnung p − 1 und ein gleichverteilt zufälliges $a \in \{ 2, \ldots, p-2 \}$. Man berechne außerdem $A = g^a \, \bmod \, p$. Hierbei steht 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. Die so erzeugten Schlüssel lassen sich auch für die Elgamal-Signatur verwenden.

Seien beispielhaft p = 17 und a = 6. Als Primitivwurzel sei g = 3 gewählt. Man berechne $A = g^a \, \bmod \, p = 3^6 \, \bmod \, 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

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, \ldots, p-1 \}$ zu wählen. Man wähle nun zufällig ein $b \in \{ 2, \ldots, p-2 \}$. Nun berechne man $B = g^b \, \bmod \, p$ und $c = A^bm \, \bmod \, 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 \, \bmod \, p = 3^5 \, \bmod \, 17 = 5$ und $c = A^bm \, \bmod \, 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^xc \, \bmod \, p$ mit x = p − 1 − a zu berechnen. Dies lässt sich folgendermaßen veranschaulichen:

$B^xc = B^{p-1-a}c \equiv g^{b(p-1-a)}A^bm$ $\equiv (g^{p-1})^b(g^a)^{-b}A^bm$ $\equiv$ (vgl. kleiner fermatscher Satz) $\equiv A^{-b}A^bm$ $\equiv m \, \bmod \, p$.

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

oder einfach zum selber nachrechnen: $m=(B^a)^{-1}\cdot c$ wobei mit hoch − 1 die multiplikative Inverse nach EEA gemeint ist.

Bewertung

Sicherheit

Die Sicherheit von Elgamal hängt eng mit mehreren mathematischen Standardproblemen zusammen.

Das Brechen von Elgamal durch Berechnen des geheimen Schlüssels aus dem öffentlichen ist genau das Diskreter-Logarithmus-Problem. Es gibt derzeit jedoch keine effizienten Algorithmen zur Berechnung diskreter Logarithmen, so dass sich diese – für genügend große Moduln – nicht in „annehmbarer“ Zeit berechnen lassen.

Das Lösen des Diffie-Hellman-Problems (CDH) ist äquivalent zum Invertieren der Elgamal-Verschlüsselung. Das bedeutet, dass jeder, der mit einer gewissen Wahrscheinlichkeit zu einem beliebigen Elgamal-Chiffrat den zugehörigen Klartext finden kann, mit der gleichen Wahrscheinlichkeit CDH lösen, also zu gegebenen g^a,g^b $g^{ab} \, \bmod \, p$ bestimmen kann. Wer CDH lösen kann, der findet auch zum öffentlichen Schlüssel g^a und dem ersten Teil des Chiffrats g^b das gemeinsame g^ab und somit die Nachricht. Umgekehrt kann jeder, der zum öffentlichen Schlüssel g^a und Chiffrat g^b,g^abm die Nachricht m findet, auch aus g^abm g^ab berechnen und somit CDH lösen.

Die stärkere Sicherheitseigenschaft IND-CPA ist äquivalent zum Decisional-Diffie-Hellman-Problem.

Alle drei Annahmen sind Standardannahmen in der Kryptographie. Deshalb wird heute davon ausgegangen, dass das Elgamal-Kryptosystem nicht in vertretbarer Zeit im Sinne der obigen Sicherheitsbegriffe gebrochen werden kann.

Effizienz

Zur Verschlüsselung sind beim Elgamal-Kryptosystem zwei modulare Exponentiationen nötig: $A^b \, \bmod \, p$ und $g^b \, \bmod \, 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.

Um jedoch Angriffe zu vermeiden, sollte immer ein neues b für jede neue Nachricht gewählt werden. So steigt zwar der Datenaufwand und die Anzahl der Verschlüsselungsschritte, jedoch ist es einem Angreifer nicht möglich, mit einem einmal gefundenem m alle vorherigen und nachfolgenden Nachrichten zu entschlüsseln. Dies hängt damit zusammen, dass sich $c_1=m_1\cdot A^b$ bei bekanntem m₁ und c₁ nach $A^b=c_1\cdot m_1^{-1}$ auflösen und ausrechnen lässt. Daraus folgt wiederum, dass $c_2=m_2\cdot A^b$ zu $c_2\cdot (A^b)^{-1}=m_2$ umgestellt werden kann und da c₂ öffentlich ist, sich die Nachricht m₂ bestimmen lässt (siehe Known-Plaintext-Angriff).

Literatur

• Johannes Buchmann: Einführung in die Kryptographie, 3., erweiterte Auflage. Springer, Berlin u. a. 2004, ISBN 3-540-40508-9.
• Dietmar Wätjen: Kryptographie, 1. Auflage. Spektrum Akademischer Verlag, Heidelberg, 2004, ISBN 3-8274-1431-8.