Elgamal-Verschlüsselungsverfahren

Das Elgamal-Verschlüsselungsverfahren oder Elgamal-Kryptosystem (auch al-Dschamal-Kryptosystem) ist ein im Jahr 1985 vom Kryptologen Taher Elgamal entwickeltes Public-Key-Verschlüsselungsverfahren, das auf der Idee des Diffie-Hellman-Schlüsselaustauschs aufbaut. Das Elgamal-Verschlüsselungsverfahren beruht, wie auch das Diffie-Hellman-Protokoll, auf Operationen in einer zyklischen Gruppe endlicher Ordnung. Das Elgamal-Verschlüsselungsverfahren ist beweisbar IND-CPA-sicher unter der Annahme, dass das Decisional-Diffie-Hellman-Problem in der zugrundeliegenden Gruppe schwierig ist.

Taher Elgamal (2010), Erfinder des Verfahrens

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

Beschreibung

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. Das heißt, der Empfänger der Nachricht muss einmalig ein Schlüsselpaar aus öffentlichen und privaten Schlüsseln erzeugen. Anschließend kann jeder mithilfe des öffentlichen Schlüssels beliebig oft eine Nachricht verschlüsseln und an den Empfänger senden. In der folgenden Beschreibung wird wie in der Kryptografie davon ausgegangen, dass ein Sender eine Nachricht an einen Empfänger senden will.

Parametererzeugung

Der Empfänger wählt eine endliche, zyklische Gruppe mit primer Ordnung und Erzeuger , so dass groß genug ist um die gewünschte Sicherheit zu bieten. wird veröffentlicht.

Im Folgenden wird , wie in der Kryptographie üblich, multiplikativ geschrieben, d. h. die Gruppenoperation wird durch einen Malpunkt dargestellt, statt wie in weiten Teilen der Mathematik üblich durch ein Plus, und die mehrfache Anwendung derselben wird als Exponent statt als Faktor dargestellt. Beim Exponenten handelt es sich prinzipiell um eine ganze Zahl, allerdings sind im hier betrachteten Fall Exponenten, die ganzzahlige Vielfache von sind, unerheblich für das Ergebnis, weswegen es alternativ legitim ist, Exponenten als Elemente des Restklassenkörpers aufzufassen. Der hierdurch mögliche Exponent 0 führt zwar dazu, dass die Verschlüsselung den unveränderten Klartext enthält, tritt aber nur mit vernachlässigbarer Wahrscheinlichkeit auf und verursacht dadurch bei echt zufälliger Wahl der Exponenten keine Probleme.

Es ist möglich, dass mehrere Parteien die gleiche Gruppe benutzen, in einigen Anwendungen ist die benutzte Gruppe sogar standardisiert.

Schlüsselerzeugung

1. Der Empfänger wählt zufällig einen Exponenten . Dies ist der private Schlüssel des Empfängers.
2. Der Empfänger berechnet das Gruppenelement als seinen öffentlichen Schlüssel und gibt diesen bekannt.

Verschlüsselung

1. Der Sender möchte die Nachricht versenden.
2. Der Sender wählt zufällig einen Exponenten .
3. Der Sender berechnet das Gruppenelement .
4. Der Sender berechnet das Chiffrat . (Man beachte: Der Sender kennt den öffentlichen Schlüssel des Empfängers.)
5. Der Sender versendet an den Empfänger.

Entschlüsselung

1. Der Empfänger berechnet den Klartext als . (Man beachte: ist der private Schlüssel des Empfängers und nur ihm bekannt.)

Gruppenwahl

Als Wahl für die endliche, zyklische Gruppe haben sich zwei Varianten durchgesetzt: Untergruppen von multiplikativen Restklassengruppen und von elliptischen Kurven über endlichen Körpern.

Klassisch ist hierbei die erstere Variante: Für prim ist ein Körper (genauer: Restklassenkörper) und die Elemente der Einheitengruppe (also der „multiplikativen“ Gruppe des Selben) sind alle Zahlen ungleich Null, konkret . Die Ordnung der Gruppe ist daher . Da prim ist, ist aber durch Zwei teilbar und die Einheitengruppe somit für keine Gruppe primer Ordnung. Sei nun ein Teiler von , dann besitzt die Einheitengruppe eine Untergruppe mit Ordnung . Handelt es sich bei um eine Primzahl, besitzt diese Untergruppe somit prime Ordnung und ist für die Verwendung potentiell geeignet. In der Praxis hat sich etabliert so zu wählen, dass geeignet ist. wird dann als sichere Primzahl, als Sophie-Germain-Primzahl bezeichnet. In diesem Fall handelt es sich dann bei der Untergruppe um die Untergruppe der quadratischen Reste, für die gilt, dass jedes Element als mit einem anderen Element geschrieben werden kann.

Analoge Probleme gelten auch für die Benutzung von elliptischen Kurven über endlichen Körpern: Auch diese besitzen zunächst keine prime Ordnung, sodass auch hier zunächst ein geeigneter Erzeuger einer Untergruppe primer Ordnung gesucht werden muss.

Die konkreten Probleme, die die Nutzung einer Gruppe mit nicht primer Ordnung implizieren, werden im Abschnitt Probleme mit Untergruppen näher behandelt und sind unabhängig von der konkret benutzten Gruppe.

Unabhängig von der Sicherheit ist die Wahl der Gruppe auch anderweitig wichtig: Lediglich Elemente der benutzten (Unter-)Gruppe können ver- und entschlüsselt werden, da das Chiffrat ansonsten auch ohne Kenntnis des privaten (und sogar des öffentlichen) Schlüssels Informationen über den Klartext offenbaren würde. Dies hat zur Folge, dass es in der Regel notwendig ist, Klartexte zuvor zu Elementen der Untergruppe zu konvertieren, was nicht immer trivial ist. Der wohl einfachste Fall ergibt sich bei der Benutzung der Restklasse einer sicheren Primzahl : Für alle ganzen Zahlen zwischen (inklusive) und (exklusiv) gilt, dass entweder oder Teil der Untergruppe primer Ordnung ist, so dass einfach das funktionierende Element benutzt werden kann.

Ein konkretes Beispiel

Die hier als verwendete Untergruppe der Quadrate von

	1	2	3	4	6	8	9	12	13	16	18
1	1	2	3	4	6	8	9	12	13	16	18
2	2	4	6	8	12	16	18	1	3	9	13
3	3	6	9	12	18	1	4	13	16	2	8
4	4	8	12	16	1	9	13	2	6	18	3
6	6	12	18	1	13	2	8	3	9	4	16
8	8	16	1	9	2	18	3	4	12	13	6
9	9	18	4	13	8	3	12	16	2	6	1
12	12	1	13	2	3	4	16	6	18	8	9
13	13	3	16	6	9	12	2	18	8	1	4
16	16	9	2	18	4	13	6	8	1	3	12
18	18	13	8	3	16	6	1	9	4	12	2

Die Potenzen der Elemente in

	0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1	1
2	1	2	4	8	16	9	18	13	3	6	12
3	1	3	9	4	12	13	16	2	6	18	8
4	1	4	16	18	3	12	2	8	9	13	6
6	1	6	13	9	8	2	12	3	18	16	4
8	1	8	18	6	2	16	13	12	4	9	3
9	1	9	12	16	6	8	3	4	13	2	18
12	1	12	6	3	13	18	9	16	8	4	2
13	1	13	8	12	18	4	6	9	2	3	16
16	1	16	3	2	9	6	4	18	12	8	13
18	1	18	2	13	4	3	8	6	16	12	9

Als Gruppe wählen wir die Untergruppe der Quadrate von mit als Erzeuger, so dass gilt . Da 23 eine sichere Primzahl ist, gibt es nur eine „große“ Untergruppe die 11 Elemente enthält; hierbei handelt es sich um die sogenannte „Untergruppe der quadratischen Reste“ oder einfacher die „Untergruppe der Quadrate“. Der Name hat seinen Ursprung darin, dass diese Gruppe genau die Elemente enthält, die als Quadrat eines anderen Elements geschrieben werden können. Hierbei handelt es sich stets um exakt die Hälfte aller Gruppenelemente, so dass diese Untergruppe genau dann prime Ordnung hat, wenn der Modulus eine Sichere Primzahl ist, was in unserem Beispiel nach Konstruktion ja der Fall ist.

Da ist, ist ein quadratischer Rest und folglich Teil der Untergruppe. Da für alle Elemente außer dem Neutralelement (hier: „“) in Gruppen primer Ordnung gilt, dass sie die gesamte Gruppe Erzeugen, hat selbst prime Ordnung und ist damit ein geeigneter Erzeuger.

Das Rechnen mit Elementen aus verläuft anschaulich fast genau so wie das Rechnen mit ganzen Zahlen, nur dass im Anschluss an jede Operation stets modulo 23 gerechnet wird (siehe erste Tabelle). Wichtig zu verstehen ist hierbei aber, dass nur 11 Elemente enthält und nicht etwa 22 oder 23.

Das Berechnen von Potenzen funktioniert analog zur normalen Potenzrechnung, so gilt etwa . Allein aus der endlichen Größe der Gruppe folgt allerdings bereits, dass sich Elemente ab einem gewissen Punkt wiederholen müssen. Da bei den hier betrachteten Gruppen primer Ordnung jedes Element außer der 1 (die nur sich selbst erzeugt) ein Erzeuger der gesamten Gruppe ist, gilt dass der Zyklus alle Element umfasst und Länge hat. Da somit für alle Gruppenelemente gilt, dass und damit für alle Exponenten gilt, dass , ist es zur Berechnung beliebiger Potenzen ausreichend die Potenz zum Exponenten modulo zu rechnen. So gilt zum Beispiel: . (Siehe die zweite Tabelle für die Potenzen aller Elemente von .)

Schlüsselerzeugung

1. Der Empfänger zieht einen zufälligen Exponenten . Dies ist der private Schlüssel des Empfängers.
2. Der Empfänger berechnet das Gruppenelement als seinen öffentlichen Schlüssel und gibt diesen bekannt.

Verschlüsselung

1. Der Sender möchte die Nachricht versenden. ( wegen .)
2. Der Sender zieht einen zufälligen Exponenten .
3. Der Sender berechnet das Chiffrat wie folgt:
   • .
   • .
4. Der Sender sendet das Chiffrat an den Empfänger.

Entschlüsselung

1. Der Empfänger berechnet den Klartext wie folgt: .

Man beachte, dass zur Entschlüsselung zwar eigentlich eine Invertierung (also Potenzierung mit −1 im Exponenten) von nötig ist, diese aber durch einfache Subtraktion des geheimen Schlüssels () von der Gruppenordnung () ohne Mehraufwand gemeinsam mit der ohnehin nötigen Potenzierung durchgeführt werden kann: Da das Addieren oder Subtrahieren von im Exponenten keine Auswirkung auf das Ergebnis hat, können so negative Exponenten () durch positive () ersetzt werden. Im Beispiel also: .

Sicherheit

Unter einer Standardannahme versteht man in der Kryptografie die Vermutung, dass ein gut untersuchtes mathematisches Problem "schwer" zu lösen ist. Lässt sich zeigen, dass das Brechen eines Kryptografieverfahrens äquivalent zum Lösen eines dieser Probleme ist, so ist sichergestellt, dass dieses mindestens genauso schwer ist. Die Sicherheit von Elgamal hängt eng mit mehreren Standardannahmen zusammen.

Im Folgenden ist mit einem erfolgversprechenden Angreifer ein Angreifer gemeint, dessen Laufzeit durch ein beliebige aber feste polynomielle Funktion im Logarithmus der Gruppenordnung beschränkt ist (= er ist effizient) und dessen Erfolgswahrscheinlichkeit relativ zum Logarithmus der Gruppenordnung mindestens so groß ist wie das Inverse einer beliebigen aber festen polynomiellen Funktion (= er hat nicht-vernachlässigbare Erfolgswahrscheinlichkeit).

Sicherheit gegen Schlüsselextraktion

Das Berechnen des geheimen Schlüssels aus dem öffentlichen Schlüssel ist genau das Problem diskrete Logarithmen zu ziehen. Zwar existieren hierfür Algorithmen die wesentlich performanter als Brute Force sind, jedoch sind auch diese entweder zu ineffizient um das Problem in hinreichend großen Gruppen zu lösen oder benötigen universelle Quantencomputer. Es ist wichtig die Grenzen dieser Aussage zu verstehen: Prinzipiell ist die Existenz von Angriffen denkbar, die es nicht nötig machen den geheimen Schlüssel zu kennen um Klartexte zu extrahieren, was zur Folge hat, dass die Aussage für sich alleine weitgehend wertlos ist.

Die Annahme, dass diskrete Logarithmen schwer zu ziehen sind, ist eine Standardannahme in der Kryptographie.

Beweis

Das Problem, den geheimen Schlüssel aus dem öffentlichen zu extrahieren, ist genau das Problem, diskrete Logarithmen zu ziehen. Da wir davon ausgehen, dass kein erfolgversprechender Angreifer hierzu in der Lage ist (DLog-Annahme!), gibt es auch keinen erfolgversprechenden Angreifer, der den privaten Schlüssel extrahieren kann.

Sicherheit gegen Klartextextraktion

Der Sicherheitsbegriff, der die praktische Unmöglichkeit bedeutet, zufällig gewählte Klartexte zu extrahieren, heißt „OW-CPA“ (kurz für „One-Way under Chosen Plaintext Attacks“ = „einweg unter Angriffen mit gewählten Klartexten“). Konkret besagt dieser, dass es keinen effizienten Angreifer gibt der eine nicht-vernachlässigbare Erfolgswahrscheinlichkeit hat, zu einem gegebenen öffentlichen Schlüssel und einem Chiffrat mit zufälligem Klartext den Klartext zu finden.

Die OW-CPA-Sicherheit von ElGamal ist äquivalent zur Computational-Diffie-Hellman-Vermutung (CDH). Diese besagt, dass es keinen effizienten Angreifer gibt, der eine nicht-vernachlässigbare Erfolgswahrscheinlichkeit hat, zu einem gegebenen Trippel das Gruppenelement zu finden. Im Unterschied zum Diskreten-Logarithmus-Problems ist nicht gefordert, die Exponenten zu bestimmen. Es genügt bestimmen zu können, um die Nachricht zu entschlüsseln.

Erneut ist es wichtig zu verstehen, dass OW-CPA-Sicherheit für nahezu alle praktischen Anwendungsfälle nicht ausreichend ist: So erlaubt OW-CPA beispielsweise einen signifikanten Anteil des Klartexts zu lernen oder zu überprüfen, ob ein Chiffrat einen bestimmten Klartext enthält.

Die CDH-Annahme ist eine stärkere (also gewagtere) Annahme als die, dass es schwer ist, diskrete Logarithmen zu ziehen, stellt allerdings ebenfalls eine nicht ernsthaft in Frage gestellte kryptographische Standardannahme dar.

Beweis

Zum Beweis der OW-CPA-Sicherheit werden wir einen Angreifer auf die Sicherheit von ElGamal benutzen, um einen Angreifer für das Computational-Diffie-Hellman-Problem zu bauen. Hierzu führen wir zwei Sicherheitsspiele aus: Eines in der Rolle des Angreifers mit einem CDH-Verifizierer und eines mit einem beliebigen Angreifer auf die OW-CPA-Sicherheit von ElGamal in der Rolle des Herausforderers.

1. Erhalte mit und unbekannt vom CDH-Herausforderer.
2. Ziehe einen zufälligen Exponenten .
3. Übergebe (Gruppe, öffentlicher Schlüssel, Chiffrat) an den OW-CPA-Angreifer.
   • Diese Werte sind ununterscheidbar vom solchen in einem echten OW-CPA-spiel, da in beiden Fällen alle Werte echt zufällig gewählt wurden.
4. Erhalte vom OW-CPA-Angreifer einen (vermeintlichen) Klartext .
5. Berechne
6. Übergebe an den CDH-Herausforderer.

Falls der OW-CPA-Angreifer erfolgversprechend ist, wird er mit einer nicht-vernachlässigbaren Wahrscheinlichkeit den eindeutig bestimmten „korrekten“ Klartext ausgeben, so dass , womit die korrekte Antwort im CDH-Spiel ist. Da die Laufzeit des Simulators im Wesentlichen als Summe der (nach Annahme) polynomiellen Laufzeit des OW-CPA-Angreifers und einiger klar effizient Operationen gegeben ist, ist sie ebenfalls polynomiell. Da der Simulator außerdem genau dann Erfolg im CDH-Spiel hat, wenn der OW-CPA-Angreifer Erfolg hat, ist er genau dann ein erfolgversprechender Angreifer, wenn der OW-CPA Angreifer es ist.

Da wir davon ausgehen, dass es keinen erfolgversprechenden CDH-Angreifer gibt (CDH-Annahme!), wir aber gezeigt haben, dass die Existenz eines erfolgversprechenden OW-CPA-Angreifers die Existenz eines Solchen impliziert, kann es keinen erfolgversprechenden OW-CPA-Angreifer geben, womit ElGamal OW-CPA-sicher ist.

Semantische Sicherheit

IND-CPA oder auch „semantische Sicherheit“ bezeichnet den schwächsten Sicherheitsbegriff der in der modernen Kryptographie als akzeptabel für zumindest einzelne Anwendungen betrachtet wird und bedeutet anschaulich, dass ein Angreifer aus dem Chiffrat keinerlei Information über den Klartext gewinnen kann. (Im Gegensatz zum vorherigen Abschnitt darf der Angreifer hier auch keine Teilinformation extrahieren können.) Bei dem hier relevanten Fall asymmetrischer Verschlüsselung kann dieser Begriff wie folgt definiert werden: Der Angreifer erhält einen öffentlichen Schlüssel und darf im Anschluss zwei Klartexte wählen, die er dem Herausforderer gibt. Letzterer wählt nun mit einem Münzwurf einen der beiden Klartexte, verschlüsselt ihn mit dem Verfahren und gibt das Chiffrat zurück an den Angreifer. Existiert kein effizienter Angreifer der nun mit einer nicht vernachlässigbar besseren Wahrscheinlichkeit als (was durch reines raten erreichbar ist) entscheiden kann, welchen der beiden gewählten Klartexte das Chiffrat enthält, so ist das Verfahren semantisch sicher.

Diese Eigenschaft ist für ElGamal äquivalent zur Decisional-Diffie-Hellman-Vermutung. Diese besagt, dass es keinen praktikablen Algorithmus gibt, der für zufällige in der Lage ist signifikant besser von zu unterscheiden als er dies durch reines Raten könnte. Zwar ist diese Annahme noch einmal stärker (also „gewagter“) als die CDH-Annahme, allerdings ist auch sie in der Kryptographie als Standardannahme akzeptiert.

Beweis

Dieser Beweis verläuft ähnlich dem zur OW-CPA-Sicherheit ab, allerdings unterscheiden sich die Spiele: Unser Simulator hat nun die Rolle des Angreifers in einem Decisional-Diffie-Hellman-Spiel (DDH) und die des Herausforderers in einem IND-CPA-Spiel.

1. Erhalte mit unbekannt vom DDH-Herausforderer.
2. Übergebe (Gruppe, öffentlicher Schlüssel) an den IND-CPA-Angreifer.
   • Diese Werte sind ununterscheidbar vom solchen in einem echten IND-CPA-spiel, da in beiden fällen alle Werte echt zufällig gewählt wurden.
3. Erhalte vom IND-CPA-Angreifer zwei verschiedene Klartexte .
4. Ziehe eine zufälliges Bit .
5. Übergebe als Chiffrat an den IND-CPA-Angreifer.
6. Erhalte ein bit vom IND-CPA-Angreifer.
7. Übergebe an den DDH-Herausforderer

Für die Analyse ergeben sich nun zwei Fälle:

• Falls , so ist die IND-CPA-Simulation perfekt. Es sei die Erfolgswahrscheinlichkeit des IND-CPA-Angreifers. Da der Simulator genau dann die korrekte Antwort (1) im DDH-Spiel gibt, wenn der IND-CPA-Angreifer falsch rät, liegt der Simulator in diesem Fall mit der Wahrscheinlichkeit richtig. Dieser Fall tritt mit Wahrscheinlichkeit ein.
• Falls ist, dann ist ein Chiffrat von Zufall. Der IND-CPA-Angreifer kann in diesem Fall inhärent keine bessere Strategie als raten haben, womit er mit der Wahrscheinlichkeit korrekt bzw. falsch rät. Da der Simulator genau dann die korrekte Antwort (0) im DDH-Spiel gibt, wenn der IND-CPA-Angreifer falsch rät, liegt der Simulator in diesem Fall mit der Wahrscheinlichkeit richtig. Dieser Fall tritt insgesamt betrachtet mit einer Wahrscheinlichkeit von ein.

Man beachte, dass im letzteren Fall zwar durch reinen Zufall mit einer Wahrscheinlichkeit von je eine Verschlüsselung von oder sein kann, sich diese Fälle allerdings gegenseitig „aufheben“ und damit nicht ins Gewicht fallen.

Als gewichteter Durchschnitt der Erfolgswahrscheinlichkeit des Simulators im DDH-Spiel ergibt sich somit . Falls der IND-CPA-Angreifer erfolgversprechend wäre, so wäre nicht vernachlässigbar und damit auch . Da die Laufzeit des Simulators klar polynomiell in ist und das Gleiche nach Annahme auch für den IND-CPA-Angreifer gilt, stellt der Simulator genau einen erfolgversprechenden DDH-Angreifer dar, falls der IND-CPA-Angreifer erfolgversprechend ist.

Da wir davon ausgehen, dass es keinen erfolgversprechenden DDH-Angreifer gibt (DDH-Annahme!), wir aber gezeigt haben, dass die Existenz eines erfolgversprechenden IND-CPA-Angreifers die Existenz eines Solchen impliziert, kann es keinen erfolgversprechenden IND-CPA-Angreifer geben, womit ElGamal IND-CPA-sicher ist.

Unsicherheit gegenüber Angriffen mit gewählten Chiffraten

IND-CCA bezeichnet einen weiteren in der modernen Kryptographie etablierten Sicherheitsbegriff, der unter anderem sicherstellt, dass ein Angreifer kein Chiffrat manipuliert, ohne dass entweder die Entschlüsselung fehlschlägt oder der neue Klartext in keinerlei erkennbarer Relation zum Alten steht. Während dies in aller Regel eine wünschenswerte oder gar notwendige Eigenschaft ist, kann sie in speziellen Anwendungsfällen „zu stark“ sein, da sie mit einigen in diesen Anwendungsfällen wünschenswerten Eigenschaften inkompatibel ist. Dies ist auch bei ElGamal der Fall: Aufgrund seiner Homomorphie und Rerandomisierbarkeit kann das Verfahren inhärent keine IND-CCA-Sicherheit bieten.

Sicherheit gegen Angriffe mit nicht-adaptiv gewählten Chiffraten

IND-CCA1 bezeichnet eine abgeschwächte Variante von IND-CCA (welches auch als IND-CCA2 bezeichnet wird), die nicht im Widerspruch zu Homomorphie steht. Unter der Annahme, dass das Decisional-Diffie-Hellman-Problem auch dann schwer bleibt, wenn dem Angreifer temporärer Zugriff auf ein bestimmtes Orakel (Computational Static Diffie-Hellman oracle/ CSDH-Orakel) gewährt wird, erfüllt ElGamal diesen Sicherheitsbegriff. Es muss betont werden, dass es sich bei dieser Annahme einerseits nicht um eine etablierte kryptographische Standardannahme handelt, sie aber andererseits im generischen Gruppenmodell für idealisierte Gruppen bewiesen wurde (was ein starkes Indiz, aber kein Beweis für die Sicherheit in den tatsächlich benutzten Gruppen darstellt).

Beweis

Der Beweis verläuft weitgehend analog zu dem zur IND-CPA-Sicherheit, unterscheidet sich aber dahingehend, dass der IND-CCA1-Angreifer temporären Zugriff auch ein Entschlüsselungsorakel erhält. Zunächst ist es allerdings notwendig, das DDH^CSDH-Spiel zu definieren:

• Der DDH^CSDH-Herausforderer zieht einen zufälligen Exponenten und übergibt an den Angreifer.
• Der Angreifer darf (polynomiell oft) ein Gruppenelement an den Herausforderer übergeben, der mit antwortet.
• Der Herausforderer zieht ein zufälliges Bit und zwei zufällige Exponenten mit . Falls übergibt er dem Angreifer das Tupel , ansonsten .
• Der Angreifer antwortet mit einem Bit und gewinnt genau dann, wenn

Offensichtlich kann ein Angreifer durch Raten eine Erfolgswahrscheinlichkeit von 50 % erreichen. Als erfolgversprechend betrachten wir daher nur effiziente Angreifer, deren Erfolgswahrscheinlichkeit mehr als nur vernachlässigbar höher als 50 % ist. Die DDH^CSDH-Annahme besagt, dass es keine derartigen Angreifer gibt.

Damit können wir nun den Beweis zur DDH-Sicherheit anpassen. Zunächst verändern wir unseren Simulator wie folgt:

1. Erhalte mit unbekannt vom DDH^CSDH-Herausforderer. (Unterschied zum DDH-Beweis: Der Simulator erhält noch kein oder .)
2. Übergebe (Gruppe, öffentlicher Schlüssel) an den IND-CCA1-Angreifer.
3. Beantworte Entschlüsselungsanfragen: (Unterschied zum DDH-Beweis: gesamte Phase)
   • Erhalte ein Chiffrat mit unbekannt vom IND-CCA1-Angreifer.
   • Übergebe als Orakel-Anfrage an den DDH^CSDH-Herausforderer.
   • Erhalte vom DDH^CSDH-Herausforderer.
   • Übergebe an den IND-CCA1-Angreifer
4. Erhalte vom IND-CCA1-Angreifer zwei verschiedene Klartexte .
5. Erhalte mit unbekannt vom DDH^CSDH-Herausforderer. (Unterschied zum DDH-Beweis: Im DDH-Beweis erhält der Simulator diese Werte bereits am Anfang.)
6. Ziehe eine zufälliges Bit .
7. Übergebe als Chiffrat an den IND-CCA1-Angreifer.
8. Erhalte ein bit vom IND-CPA-Angreifer.
9. Übergebe an den DDH-Herausforderer

Die weitere Argumentation ist exakt analog zu der des IND-CPA-Beweises: Die Existenz eines erfolgversprechenden Angreifers auf die IND-CCA1-Sicherheit von ElGamal impliziert die Existenz eines erfolgversprechenden Angreifers auf das DDH^CSDH-Spiel. Da die DDH^CSDH-Annahme einen solchen Angreifer ausschließt, bedeutet dies, dass es keinen erfolgversprechenden Angreifer auf die IND-CCA1-Sicherheit von ElGamal gibt und ElGamal damit IND-CCA1-sicher ist.

Unsicherheit gegenüber Quantencomputern

Quantencomputer sind mit einer Variante des Shor-Algorithmus in der Lage, diskrete Logarithmen in beliebigen zyklischen Gruppen endlicher Ordnung zu ziehen. Dies hat zur Folge, dass ein mit hinreichend vielen verschränkbaren Qubits ausgestatteter Quantencomputer effizient in der Lage wäre, jegliche Variante von ElGamal vollumfänglich zu brechen, indem er den geheimen Schlüssel aus dem öffentlichen berechnet.

Sonstige Eigenschaften

ElGamal bietet neben seiner Sicherheit auch weitere Eigenschaften die in manchen Zusammenhängen nützlich sein können.

Homomorphe Verschlüsselung

Es seien Chiffrate der Klartexte mit den Verschlüsselungszufällen für den Öffentlichen Schlüssel . Dann können diese ohne Kenntnis des geheimen Schlüssels durch komponentenweise Verknüpfung mit der Gruppenoperation zu einem Chiffrat von verknüpft werden:

Rerandomisierbarkeit

Es sei ein Chiffrat eines Klartextes mit Verschlüsselungszufall für den Öffentlichen Schlüssel . Dann kann ohne Kenntnis des geheimen Schlüssels ein Chiffrat mit demselben Klartext berechnet werden, dem dies auch im direkten Vergleich nicht angesehen werden kann. Es sei ein frisch zufällig gewählter Exponent:

In gewisser Weise handelt es sich hierbei um die Nutzung der Homomorphie-Eigenschaft mit einem neu erzeugtem Chiffrat dessen Klartext das neutrale Element („1“) ist.

Ununterscheidbarkeit von Empfängern

ElGamal-Chiffrate bieten Anonymität in dem Sinne, dass einem Chiffrat, selbst bei vom Angreifer gewähltem Klartext, nicht angesehen werden kann, für welchen von mehreren öffentlichen Schlüsseln (aus derselben Gruppe!) es erstellt wurde.

Ein asymmetrisches Verschlüsselungsverfahren ist im hier verwendeten Sinne anonym unter Angriffen mit gewählten Klartexten, wenn es keinen erfolgversprechenden Angreifer gibt, der folgendes Spiel besser als durch bloßes Raten (Erfolgswahrscheinlichkeit ) gewinnen kann:

1. Der Herausforderer erzeugt zwei Schlüsselpaare und übergibt die öffentlichen Schlüssel dem Angreifer
2. Der Angreifer übergibt dem Herausforderer einen gültigen Klartext .
3. Der Herausforderer wählt zufällig einen der beiden öffentlichen Schlüssel, verschlüsselt mit ihm und übergibt das Chiffrat an den Angreifer.
4. Der Angreifer übergibt dem Herausforderer seine Vermutung, mit welchem Schlüssel das Chiffrat erzeugt wurde, und gewinnt genau dann, wenn er recht hat.

Beweis

Der Beweis erfolgt erneut durch Reduktion mit dem folgenden Simulator:

1. Erhalte mit unbekannt vom DDH-Herausforderer.
2. Ziehe ein zufälliges Bit und ein zufälliges Gruppenelement .
3. Falls übergebe an den Angreifer, ansonsten .
4. Erhalte einen Klartext vom Angreifer.
5. Übergebe an den Angreifer
6. Erhalte ein bit vom Angreifer.
7. Übergebe an den DDH-Herausforderer

Die weitere Analyse verläuft nahezu identisch zu der zur semantischen Sicherheit: Auch hier ergeben sich zwei Fälle:

• Falls , dann ist mit überwältigender Wahrscheinlichkeit für keinen der beiden öffentlichen Schlüssel ein Chiffrat von , sondern in beiden Fällen von reinem Zufall. Der Angreifer kann in diesem Fall inhärent keine bessere Strategie als raten haben, womit er mit der Wahrscheinlichkeit korrekt bzw. falsch rät. Da der Simulator genau dann die korrekte Antwort (0) im DDH-Spiel gibt, wenn der IND-CPA-Angreifer falsch rät, liegt der Simulator in diesem Fall mit der Wahrscheinlichkeit richtig.
• Falls , so ist die Simulation perfekt. Es sei die Erfolgswahrscheinlichkeit des Angreifers den öffentlichen Schlüssel korrekt zu erraten. Da der Simulator genau dann die korrekte Antwort (1) im DDH-Spiel gibt, wenn der Angreifer richtig rät, liegt der Simulator in diesem Fall mit der Wahrscheinlichkeit richtig.

Da beide Fälle mit Wahrscheinlichkeit auftreten, ergibt sich für die Erfolgswahrscheinlichkeit des Simulators im DDH-Spiel . Falls der Angreifer erfolgversprechend wäre, so wäre nicht vernachlässigbar und damit auch nicht. Da die Laufzeit des Simulators klar polynomiell im Sicherheitsparameter ist und das Gleiche nach Annahme auch für den Angreifer gilt, stellt der Simulator genau einen erfolgversprechenden DDH-Angreifer dar, falls der Angreifer auf die Ununterscheidbarkeit des Empfängers erfolgversprechend ist.

Da wir davon ausgehen, dass es keinen erfolgversprechenden DDH-Angreifer gibt (DDH-Annahme!), wir aber gezeigt haben, dass die Existenz eines erfolgversprechenden Empfänger-Unterscheiders die Existenz eines Solchen impliziert, kann es keinen erfolgversprechenden Angreifer geben, der einem ElGamal-Chiffrat mit bekanntem (oder gar gewähltem) Klartext ansieht, für welchen Empfänger es bestimmt ist.

Verschlüsseln für mehrere Empfänger

Es seien öffentliche Schlüssel verschiedener Empfänger. Das Produkt dieser Schlüssel ist nun seinerseits ein öffentlicher Schlüssel, dessen privater Schlüssel die Summe der privaten Schlüssel ist. Dies ermöglicht es eine Nachricht so für mehrere Empfänger zu verschlüsseln, dass diese nur gemeinsam in der Lage sind, das Chiffrat zu entschlüsseln. Diese Entschlüsselung kann ferner in beliebiger Reihenfolge erfolgen.

Wir betrachten nun den Fall für nur zwei Parteien: Es sei und ein Chiffrat von mit Verschlüsselungszufall . Beide Parteien können nun beziehungsweise berechnen. Werden diese Werte nun in beliebiger Reihenfolge mit multipliziert, so ergibt sich: .

Zu beachten ist in diesem Zusammenhang auch, dass ein teilweise Entschlüsseltes Chiffrat ein gültiges Chiffrat bezüglich der verbleibenden Schlüssel darstellt. So gilt: , was zusammen mit ein reguläres Chiffrat für den öffentlichen Schlüssel mit Zufall darstellt. Diese Eigenschaft kann insbesondere im Zusammenspiel mit der Rerandomisierbarkeit und Zero-Knowledge-Beweisen beim Entwurf komplexer Protokolle nützlich sein.

Nachträgliches Überverschlüsseln mit bekanntem privatem Schlüssel

Während für das zuvor beschriebene Verschlüsseln für mehrere Empfänger nur die öffentlichen Schlüssel benötigt werden, müssen diese jedoch bereits zum Zeitpunkt der Verschlüsselung vorliegen. Ist andererseits der geheime Schlüssel bekannt, so kann dieser auch nachträglich hinzugefügt werden. Es sei wieder ein Chiffrat eines Klartextes mit Verschlüsselungszufall für den Öffentlichen Schlüssel . Ferner sei ein weiterer öffentlicher Schlüssel, zu dem der private Schlüssel gehört. Eine Partei die diesen privaten Schlüssel und das Chiffrat kennt, kann nun berechnen und dies mit multiplizieren, was ihr das Chiffrat gibt, welches die zuvor beschriebene Struktur eines Chiffrats mit auf mehreren Parteien aufgeteilten Schlüssel hat.

Zu beachten ist in diesem Zusammenhang, dass kein altbekannter Schlüssel sein muss, sondern frisch erzeugt werden kann. Wie auch schon die reguläre Aufteilung eines Schlüssels ist diese Eigenschaft in erster Linie beim Einsatz in komplexeren Protokollen im Zusammenspiel mit weiteren Primitiven nützlich.

Sicherheitsprobleme bei Protokollabweichungen

Auch wenn Elgamal sicher ist, gilt diese Aussage nur für den Fall, dass das Verfahren korrekt implementiert wurde. Durch schlechte Wahl der Parameter oder Fehler in der Implementierung können unsichere Spezialfälle auftreten.

Mehrfache Benutzung des Verschlüsselungszufalls

Aus Effizienzgründen könnte der Sender auf die Idee kommen, für mehrere Nachrichten an den gleichen Empfänger mehrfach denselben Zufall zu verwenden. In diesem Fall wäre die (vergleichsweise aufwendige) Exponentiation in der Gruppe nur einmal notwendig und es würde eine Gruppenoperation pro Nachricht verbleiben.

Ein derartiges Vorgehen ist allerdings höchst unsicher, was bereits daran erkannt werden kann, dass gleiche Klartext auf gleiche Chiffrate abgebildet würden, was unvereinbar mit IND-CPA-Sicherheit ist. Darüber hinaus genügt dem Angreifer ein einziges Klartext-Chiffrat-Paar um alle anderen Nachrichten zu entschlüsseln: Sei das dem Angreifer bekannte Klartext-Chiffrat-Paar und ein weiteres Chiffrat mit demselben Zufall. In diesem Fall gilt und . Selbst wenn kein Klartext-Chiffrat-Paar vorliegt sind die Folgen allerdings potentiell desaströs, da nach wie vor der Quotient der Klartexte gleich dem Quotienten der Chiffrate ist und damit erhebliche Information über die Relation der Klartexte öffentlich wird:

Anschaulich lässt sich all dies dadurch erklären, dass die eigentliche Verschlüsselung bei ElGamal der eines One-Time-Pads ähnelt: Die DDH-Annahme besagt, dass ununterscheidbar von Zufall ist, selbst wenn und bekannt sind. Die eigentlich Verschlüsselung findet dann dadurch statt, dass der Klartext mit diesem pseudozufälligen Element maskiert wird. Die mehrfache Verwendung desselben Zufalls hat nun zur Folge, dass das maskierende Element mehrfach verwendet wird, was der bekanntermaßen unsicheren mehrfachen Verwendung des Verschlüsselungszufalls bei One-Time-Pads entspricht.

Probleme mit Untergruppen

Für die Sicherheit vom ElGamal muss in der verwendeten Gruppe die DDH-Annahme gelten. Eine notwendige Bedingung hierfür ist, dass die Ordnung von prim ist, so dass die triviale Gruppe die einzige echte Untergruppe von ist. Ist dem nicht so, kann dies fatale Folgen haben:

Für jeden Teiler der Gruppenordnung , existiert eine Untergruppe von mit der Ordnung . Ein Element ist genau dann ein Element dieser Untergruppe, falls , womit sich für jedes Element leicht überprüfen lässt, in welchen Untergruppen es vorhanden ist. Dies ermöglicht Unterscheidungsangriffe gegen ElGamal: Seien der öffentliche Schlüssel und das erste Element eines Chiffrats Erzeuger der gesamten Gruppe . In diesem Fall offenbart das Chiffrat für alle bekannten Faktoren von , ob der Klartext in der Untergruppe mit der jeweiligen Ordnung liegt.

Dieses Problem tritt insbesondere bei der Verwendung von Restklassengruppen auf, wenn eine einfache Primzahl als Modulus verwendet wird. Da 0 kein Element der multiplikativen Gruppe ist, ist die Gruppenordnung in diesem Fall . Die korrekte Gegenmaßnahme stellt in diesem Fall die Verwendung einer Untergruppe primer Ordnung dar, wobei sichergestellt sein muss, dass diese Untergruppe nach wie vor groß genug ist, um anderweitigen Angriffen zu widerstehen. In der Praxis wird bei korrekter Verwendung in aller Regel als sichere Primzahl gewählt und die Untergruppe der Quadrate der zugehörigen Einheitengruppe des Primkörpers verwendet. Wichtig ist hierbei aber, dass der Erzeuger tatsächlich ein Quadrat ist, da ansonsten dem Chiffrat angesehen werden kann, ob es sich beim Klartext um ein Quadrat handelt. Während dies auf den ersten Blick nicht besonders schlimm erscheinen mag, gibt es (unter der DDH-Annahme) beweisbar sichere Protokolle, die hierdurch vollumfänglich gebrochen werden

Ein weiteres Problem mit Untergruppen, das bei nicht primer Ordnung auftreten kann, betrifft Elemente, die nur sehr kleine Untergruppen erzeugen:

Falls der Empfänger bei der Schlüsselerzeugung einen Exponenten wählt, sodass sein öffentlicher Schlüssel nur eine sehr kleine Untergruppe erzeugt, so wird auch die durch den Verschlüsselungszufall erzeugte „Maske“ in dieser Untergruppe liegen. Effektiv bedeutet dies, dass sie sich durch vollständige Suche leicht finden lässt und das Chiffrat in der Folge leicht entschlüsselt werden kann. Dieser kann beispielsweise wie folgt aussehen:

1. Der Empfänger wählt die Gruppe mit Erzeuger .
2. Der Empfänger wählt und berechnet als seinen öffentlichen Schlüssel

Allerdings gilt

bzw. . D.h. erzeugt die Untergruppe der Ordnung 3. Denn nach dem Hauptsatz über endlich erzeugte abelsche Gruppen zerfällt gemäß

Die Folge hiervon ist, dass der Sender den Klartext nur noch mit einem von drei Gruppenelementen multipliziert, egal welcher Exponent gewählt wird. Insbesondere ist in einem von drei Fällen das Chiffrat identisch zum Klartext.

Hat keine großen Faktoren, lässt sich dieser Angriff sogar auf alle Elemente von ausweiten: Durch potenzieren des Gruppenelements mit den verschiedenen Faktoren der Gruppenordnung, lässt sich jedes Gruppenelement in alle Untergruppen abbilden, in denen dann der Modulus relativ zur Untergruppenordnung bestimmt werden kann; durch kombinieren dieser Moduli relativ zu den Untergruppenordnungen lässt sich dann der Modulus des ursprünglichen Elements in Erfahrung bringen (Pohlig-Hellman-Algorithmus).

Literatur

• Taher ElGamal: A public key cryptosystem and a signature scheme based on discrete logarithms. Juli 1985. (englisch)
• 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.
• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography. 5. Auflage. CRC Press, 2001, ISBN 0-8493-8523-7, 8.4 ElGamal public-key encryption, S. 294 (englisch).  Auch online verfügbar. Mit Beschreibung des Algorithmus'.

Einzelnachweise

1. Helger Lipmaa: „On the CCA1-Security of Elgamal and Damgård’s Elgamal“, 2008 (englisch)
2. Mihir Bellare, Alexandra Boldyreva, Anand Desai, David Pointcheval: Key-Privacy in Public-Key Encryption
3. Florian Weber: „On Generators of Diffie-Hellman-Groups“ (englisch)