Elgamal-Verschlüsselungsverfahren

Der Empfänger wählt eine endliche, zyklische Gruppe ${\displaystyle \mathbb {G} =\langle g\rangle }$ mit primer Ordnung ${\displaystyle q}$ und Erzeuger ${\displaystyle g}$, so dass ${\displaystyle q}$ groß genug ist um die gewünschte Sicherheit zu bieten. ${\displaystyle \mathbb {G} }$ wird veröffentlicht.

Im Folgenden wird ${\displaystyle \mathbb {G} }$, 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 ${\displaystyle q}$ sind, unerheblich für das Ergebnis, weswegen es alternativ legitim ist, Exponenten als Elemente des Restklassenkörpers ${\displaystyle \mathbb {Z} _{q}}$ 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.

1. Der Empfänger wählt zufällig einen Exponenten ${\displaystyle a\leftarrow \mathbb {Z} _{q}}$. Dies ist der private Schlüssel des Empfängers.
2. Der Empfänger berechnet das Gruppenelement ${\displaystyle \left[g^{a}\right]\in \mathbb {G} }$ als seinen öffentlichen Schlüssel und gibt diesen bekannt.

1. Der Sender möchte die Nachricht ${\displaystyle m\in \mathbb {G} }$ versenden.
2. Der Sender wählt zufällig einen Exponenten ${\displaystyle r\leftarrow \mathbb {Z} _{q}}$.
3. Der Sender berechnet das Gruppenelement ${\displaystyle c_{0}=g^{r}\in \mathbb {G} }$.
4. Der Sender berechnet das Chiffrat ${\displaystyle c_{1}=\left[g^{a}\right]^{r}\cdot m\in \mathbb {G} }$. (Man beachte: Der Sender kennt den öffentlichen Schlüssel ${\displaystyle \left[g^{a}\right]}$ des Empfängers.)
5. Der Sender versendet ${\displaystyle (c_{0},c_{1})}$ an den Empfänger.

1. Der Empfänger berechnet den Klartext ${\displaystyle m}$ als ${\displaystyle c_{0}^{-a}\cdot c_{1}=\left[g^{r}\right]^{-a}\cdot \left[g^{ar}\cdot m\right]=g^{-ra+ar}\cdot m=g^{0}\cdot m=1\cdot m=m}$. (Man beachte: ${\displaystyle a}$ ist der private Schlüssel des Empfängers und nur ihm bekannt.)

1. Der Empfänger zieht einen zufälligen Exponenten ${\displaystyle a:=5}$. Dies ist der private Schlüssel des Empfängers.
2. Der Empfänger berechnet das Gruppenelement ${\displaystyle g^{a}=2^{5}\equiv 9\mod 23}$ als seinen öffentlichen Schlüssel und gibt diesen bekannt.

1. Der Sender möchte die Nachricht ${\displaystyle m=8}$ versenden. (${\displaystyle 8\in \mathbb {G} }$ wegen ${\displaystyle 13^{2}=169\equiv 8\mod 23}$.)
2. Der Sender zieht einen zufälligen Exponenten ${\displaystyle r=7}$.
3. Der Sender berechnet das Chiffrat ${\displaystyle c}$ wie folgt:
   • ${\displaystyle c_{0}:=g^{r}=2^{7}\equiv 13\mod 23}$.
   • ${\displaystyle c_{1}:=\left[g^{a}\right]^{r}\cdot m=9^{7}\cdot 8\equiv 9\mod 23}$.
   • ${\displaystyle c:=(c_{0},c_{1})=(13,9)}$
4. Der Sender sendet das Chiffrat ${\displaystyle c}$ an den Empfänger.

1. Der Empfänger berechnet den Klartext ${\displaystyle m}$ wie folgt: ${\displaystyle m:=c_{0}^{-a}\cdot c_{1}=13^{-5}\cdot 9\equiv 13^{11-5}\cdot 9\equiv 13^{6}\cdot 9\equiv 6\cdot 9\equiv 8\mod 23}$.

Man beachte, dass zur Entschlüsselung zwar eigentlich eine Invertierung (also Potenzierung mit −1 im Exponenten) von ${\displaystyle (c_{0})^{a}}$ nötig ist, diese aber durch einfache Subtraktion des geheimen Schlüssels (${\displaystyle a}$) von der Gruppenordnung (${\displaystyle q}$) ohne Mehraufwand gemeinsam mit der ohnehin nötigen Potenzierung durchgeführt werden kann: Da das Addieren oder Subtrahieren von ${\displaystyle q}$ im Exponenten keine Auswirkung auf das Ergebnis hat, können so negative Exponenten (${\displaystyle -a}$) durch positive (${\displaystyle q-a}$) ersetzt werden. Im Beispiel also: ${\displaystyle 13^{-5}\equiv 13^{11-5}=13^{6}\mod 23}$.

Das Berechnen des geheimen Schlüssels ${\displaystyle a}$ aus dem öffentlichen Schlüssel ${\displaystyle \left[g^{a}\right]\in \mathbb {G} }$ 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.

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.

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 ${\displaystyle (g,g^{x},g^{y})\in \mathbb {G} ^{3}}$ das Gruppenelement ${\displaystyle g^{xy}\in \mathbb {G} }$ zu finden. Im Unterschied zum Diskreten-Logarithmus-Problems ist nicht gefordert, die Exponenten ${\displaystyle x,y}$ zu bestimmen. Es genügt ${\displaystyle g^{xy}}$ 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.

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 ${\displaystyle \mathbb {G} ,(g^{x},g^{y})\in \mathbb {G} ^{2}}$ mit ${\displaystyle x}$ und ${\displaystyle y}$ unbekannt vom CDH-Herausforderer.
2. Ziehe einen zufälligen Exponenten ${\displaystyle r\leftarrow \mathbb {Z} _{q}}$.
3. Übergebe ${\displaystyle \mathbb {G} ,g^{x},(g^{y},g^{r})}$ (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 ${\displaystyle m\in \mathbb {G} }$.
5. Berechne ${\displaystyle h:=g^{r}\cdot m^{-1}}$
6. Übergebe ${\displaystyle h}$ an den CDH-Herausforderer.

Falls der OW-CPA-Angreifer erfolgversprechend ist, wird er mit einer nicht-vernachlässigbaren Wahrscheinlichkeit den eindeutig bestimmten „korrekten“ Klartext ${\displaystyle m}$ ausgeben, so dass ${\displaystyle g^{r}=g^{xy}\cdot m}$, womit ${\displaystyle h}$ 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.

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 ${\textstyle {\frac {1}{2}}}$ (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 ${\displaystyle x,y,z\leftarrow \mathbb {Z} _{p}}$ in der Lage ist ${\displaystyle g^{x},g^{y},g^{xy}\in \mathbb {G} }$ signifikant besser von ${\displaystyle g^{x},g^{y},g^{z}\in \mathbb {G} }$ 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.

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 ${\displaystyle \mathbb {G} ,(g^{x},g^{y},g^{z})\in \mathbb {G} ^{3}}$ mit ${\displaystyle x,y,z}$ unbekannt vom DDH-Herausforderer.
2. Übergebe ${\displaystyle \mathbb {G} ,g^{x}}$ (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 ${\displaystyle m_{0},m_{1}\in \mathbb {G} }$.
4. Ziehe eine zufälliges Bit ${\displaystyle b\leftarrow \mathbb {B} }$.
5. Übergebe ${\displaystyle c:=(g^{y},g^{z}\cdot m_{b})}$ als Chiffrat an den IND-CPA-Angreifer.
6. Erhalte ein bit ${\displaystyle b'\in \mathbb {B} }$ vom IND-CPA-Angreifer.
7. Übergebe ${\displaystyle b'':=(b=b')}$ an den DDH-Herausforderer

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

• Falls ${\displaystyle xy=z}$, so ist die IND-CPA-Simulation perfekt. Es sei ${\textstyle {\frac {1}{2}}+\epsilon }$ 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 ${\textstyle {\frac {1}{2}}+\epsilon }$ richtig. Dieser Fall tritt mit Wahrscheinlichkeit ${\textstyle {\frac {1}{2}}}$ ein.
• Falls ${\displaystyle xy\neq z}$ ist, dann ist ${\displaystyle c}$ ein Chiffrat von Zufall. Der IND-CPA-Angreifer kann in diesem Fall inhärent keine bessere Strategie als raten haben, womit er ${\displaystyle b}$ mit der Wahrscheinlichkeit ${\textstyle {\frac {1}{2}}}$ 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 ${\textstyle {\frac {1}{2}}}$ richtig. Dieser Fall tritt insgesamt betrachtet mit einer Wahrscheinlichkeit von ${\textstyle {\frac {1}{2}}}$ ein.

Man beachte, dass im letzteren Fall ${\textstyle c}$ zwar durch reinen Zufall mit einer Wahrscheinlichkeit von je ${\textstyle {\frac {1}{|\mathbb {G} |}}}$ eine Verschlüsselung von ${\textstyle m_{0}}$ oder ${\textstyle m_{1}}$ 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 ${\textstyle {\frac {1}{2}}\times \left({\frac {1}{2}}+\epsilon \right)+{\frac {1}{2}}\times {\frac {1}{2}}={\frac {1}{2}}+{\frac {\epsilon }{2}}}$. Falls der IND-CPA-Angreifer erfolgversprechend wäre, so wäre ${\displaystyle \epsilon }$ nicht vernachlässigbar und damit auch ${\textstyle {\frac {\epsilon }{2}}}$. Da die Laufzeit des Simulators klar polynomiell in ${\displaystyle p}$ 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.

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.

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).[1]

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 ${\displaystyle x\leftarrow \mathbb {Z} _{q}}$ und übergibt ${\displaystyle g^{x}}$ an den Angreifer.
• Der Angreifer darf (polynomiell oft) ein Gruppenelement ${\displaystyle h\in \mathbb {G} }$ an den Herausforderer übergeben, der mit ${\displaystyle h^{x}}$ antwortet.
• Der Herausforderer zieht ein zufälliges Bit ${\displaystyle b\in \mathbb {B} }$ und zwei zufällige Exponenten ${\displaystyle y,z\in \mathbb {Z} _{q}}$ mit ${\displaystyle xy\neq z}$. Falls ${\displaystyle b=0}$ übergibt er dem Angreifer das Tupel ${\displaystyle g^{y},g^{z}}$, ansonsten ${\displaystyle g^{y},g^{x\cdot y}}$.
• Der Angreifer antwortet mit einem Bit ${\displaystyle b'\in \mathbb {B} }$ und gewinnt genau dann, wenn ${\displaystyle b=b'}$

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 ${\displaystyle \mathbb {G} ,g^{x}\in \mathbb {G} }$ mit ${\displaystyle x}$ unbekannt vom DDH^CSDH-Herausforderer. (Unterschied zum DDH-Beweis: Der Simulator erhält noch kein ${\displaystyle g^{y}}$ oder ${\displaystyle g^{z}}$.)
2. Übergebe ${\displaystyle \mathbb {G} ,g^{x}}$ (Gruppe, öffentlicher Schlüssel) an den IND-CCA1-Angreifer.
3. Beantworte Entschlüsselungsanfragen: (Unterschied zum DDH-Beweis: gesamte Phase)
   • Erhalte ein Chiffrat ${\displaystyle g^{a},g^{b}}$ mit ${\displaystyle a,b}$ unbekannt vom IND-CCA1-Angreifer.
   • Übergebe ${\displaystyle g^{a}}$ als Orakel-Anfrage an den DDH^CSDH-Herausforderer.
   • Erhalte ${\displaystyle g^{xa}}$ vom DDH^CSDH-Herausforderer.
   • Übergebe ${\displaystyle g^{b}\cdot \left[g^{xa}\right]^{-1}}$ an den IND-CCA1-Angreifer
4. Erhalte vom IND-CCA1-Angreifer zwei verschiedene Klartexte ${\displaystyle m_{0},m_{1}\in \mathbb {G} }$.
5. Erhalte ${\displaystyle g^{y},g^{z}\in \mathbb {G} ^{2}}$ mit ${\displaystyle y,z}$ 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 ${\displaystyle b\leftarrow \mathbb {B} }$.
7. Übergebe ${\displaystyle c:=(g^{y},g^{z}\cdot m_{b})}$ als Chiffrat an den IND-CCA1-Angreifer.
8. Erhalte ein bit ${\displaystyle b'\in \mathbb {B} }$ vom IND-CPA-Angreifer.
9. Übergebe ${\displaystyle b'':=(b=b')}$ 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.

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.

Es seien ${\displaystyle c,c'}$ Chiffrate der Klartexte ${\displaystyle m,m'}$ mit den Verschlüsselungszufällen ${\displaystyle r,r'}$ für den Öffentlichen Schlüssel ${\displaystyle \left[g^{a}\right]}$. Dann können diese ohne Kenntnis des geheimen Schlüssels durch komponentenweise Verknüpfung mit der Gruppenoperation zu einem Chiffrat von ${\displaystyle m\cdot m'}$ verknüpft werden:

${\displaystyle (c_{0},\ c_{1})\cdot (c_{0}',c_{1}')=(c_{0}\cdot c_{0}',\ c_{1}\cdot c_{1}')=\left(g^{r}\cdot g^{r'},\ g^{ar}\cdot m\cdot g^{ar'}\cdot m'\right)=\left(g^{r+r'},\ g^{ar+ar'}\cdot m\cdot m'\right)=\left(g^{r+r'},\ g^{a(r+r')}\cdot m\cdot m'\right)}$

Es sei ${\displaystyle c=:(c_{0},\ c_{1})}$ ein Chiffrat eines Klartextes ${\displaystyle m}$ mit Verschlüsselungszufall ${\displaystyle r}$ für den Öffentlichen Schlüssel ${\displaystyle \left[g^{a}\right]}$. Dann kann ohne Kenntnis des geheimen Schlüssels ein Chiffrat ${\displaystyle c'}$ mit demselben Klartext berechnet werden, dem dies auch im direkten Vergleich nicht angesehen werden kann. Es sei ${\displaystyle r'}$ ein frisch zufällig gewählter Exponent:

${\displaystyle (c_{0},\ c_{1})\cdot \left(g^{r'},\left[g^{a}\right]^{r'}\right)=\left(g^{r}\cdot g^{r'},\ g^{ar}\cdot m\cdot g^{ar'}\right)=\left(g^{r+r'},\ g^{ar+ar'}\cdot m\right)=\left(g^{r+r'},\ g^{a(r+r')}\cdot m\right)}$

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.

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.[2]

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 ${\textstyle {\frac {1}{2}}}$) 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 ${\displaystyle m}$.
3. Der Herausforderer wählt zufällig einen der beiden öffentlichen Schlüssel, verschlüsselt ${\displaystyle m}$ 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.

Der Beweis erfolgt erneut durch Reduktion mit dem folgenden Simulator:

1. Erhalte ${\displaystyle \mathbb {G} ,(g^{x},g^{y},g^{z})\in \mathbb {G} ^{3}}$ mit ${\displaystyle x,y,z}$ unbekannt vom DDH-Herausforderer.
2. Ziehe ein zufälliges Bit ${\displaystyle b\leftarrow \mathbb {B} }$ und ein zufälliges Gruppenelement ${\displaystyle h\leftarrow \mathbb {G} }$.
3. Falls ${\displaystyle b=0}$ übergebe ${\displaystyle g^{x},h}$ an den Angreifer, ansonsten ${\displaystyle h,g^{x}}$.
4. Erhalte einen Klartext ${\displaystyle m\in \mathbb {G} }$ vom Angreifer.
5. Übergebe ${\displaystyle (g^{y},g^{z}\cdot m)}$ an den Angreifer
6. Erhalte ein bit ${\displaystyle b'\in \mathbb {B} }$ vom Angreifer.
7. Übergebe ${\displaystyle b'':=(b=b')}$ an den DDH-Herausforderer

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

• Falls ${\displaystyle xy\neq z}$, dann ist ${\displaystyle (g^{y},g^{z})}$ mit überwältigender Wahrscheinlichkeit für keinen der beiden öffentlichen Schlüssel ein Chiffrat von ${\displaystyle m}$, sondern in beiden Fällen von reinem Zufall. Der Angreifer kann in diesem Fall inhärent keine bessere Strategie als raten haben, womit er ${\displaystyle b}$ mit der Wahrscheinlichkeit ${\textstyle {\frac {1}{2}}}$ 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 ${\textstyle {\frac {1}{2}}}$ richtig.
• Falls ${\displaystyle xy=z}$, so ist die Simulation perfekt. Es sei ${\textstyle {\frac {1}{2}}+\epsilon }$ 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 ${\textstyle {\frac {1}{2}}+\epsilon }$ richtig.

Da beide Fälle mit Wahrscheinlichkeit ${\textstyle {\frac {1}{2}}}$ auftreten, ergibt sich für die Erfolgswahrscheinlichkeit des Simulators im DDH-Spiel ${\textstyle {\frac {1}{2}}\left({\frac {1}{2}}+{\frac {1}{2}}+\epsilon \right)={\frac {1}{2}}+{\frac {\epsilon }{2}}}$. Falls der Angreifer erfolgversprechend wäre, so wäre ${\displaystyle \epsilon }$ nicht vernachlässigbar und damit auch ${\textstyle {\frac {\epsilon }{2}}}$ 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.

Es seien ${\displaystyle g^{x_{0}},g^{x_{1}},\dots ,g^{x_{n}}}$ ö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 ${\displaystyle g^{y}=g^{x_{0}+x_{1}}=g^{x_{0}}\cdot g^{x_{1}}}$ und ${\displaystyle c=(c_{0},\ c_{1})=(g^{r},\ g^{yr}\cdot m)}$ ein Chiffrat von ${\displaystyle m}$ mit Verschlüsselungszufall ${\displaystyle r}$. Beide Parteien können nun ${\displaystyle g^{-r\cdot x_{0}}}$ beziehungsweise ${\displaystyle g^{-r\cdot x_{1}}}$ berechnen. Werden diese Werte nun in beliebiger Reihenfolge mit ${\displaystyle c_{1}}$ multipliziert, so ergibt sich: ${\displaystyle g^{yr}\cdot m\cdot g^{-r\cdot x_{0}}\cdot g^{-r\cdot x_{1}}=g^{(x_{0}+x_{1})r}\cdot g^{-rx_{0}}\cdot g^{-rx_{1}}\cdot m=g^{r(x_{0}+x_{1}-x_{0}-x_{1})}\cdot m=g^{0}\cdot m=m}$.

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: ${\displaystyle g^{yr}\cdot m\cdot g^{-r\cdot x_{0}}=g^{(x_{0}+x_{1})r}\cdot g^{-rx_{0}}\cdot m=g^{r(x_{0}+x_{1}-x_{0})}\cdot m=g^{rx_{1}}}$, was zusammen mit ${\displaystyle c_{0}}$ ein reguläres Chiffrat für den öffentlichen Schlüssel ${\displaystyle g^{x_{1}}}$ mit Zufall ${\displaystyle r}$ darstellt. Diese Eigenschaft kann insbesondere im Zusammenspiel mit der Rerandomisierbarkeit und Zero-Knowledge-Beweisen beim Entwurf komplexer Protokolle nützlich sein.

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 ${\displaystyle c=:(c_{0},\ c_{1})=:\left(g^{r},g^{rx}\cdot m\right)}$ ein Chiffrat eines Klartextes ${\displaystyle m}$ mit Verschlüsselungszufall ${\displaystyle r}$ für den Öffentlichen Schlüssel ${\displaystyle \left[g^{a}\right]}$. Ferner sei ${\displaystyle g^{y}}$ ein weiterer öffentlicher Schlüssel, zu dem der private Schlüssel ${\displaystyle y}$ gehört. Eine Partei die diesen privaten Schlüssel und das Chiffrat kennt, kann nun ${\displaystyle \left[g^{r}\right]^{y}=g^{ry}}$ berechnen und dies mit ${\displaystyle c_{1}}$ multiplizieren, was ihr das Chiffrat ${\displaystyle c'=:(c_{0}',\ c_{1}')=:\left(g^{r},g^{rx}\cdot g^{ry}\cdot m\right)=\left(g^{r},g^{r(x+y)}\cdot m\right)}$ gibt, welches die zuvor beschriebene Struktur eines Chiffrats mit auf mehreren Parteien aufgeteilten Schlüssel hat.

Zu beachten ist in diesem Zusammenhang, dass ${\displaystyle g^{y}}$ 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.

Aus Effizienzgründen könnte der Sender auf die Idee kommen, für mehrere Nachrichten ${\displaystyle m_{0},m_{1},\dots }$ an den gleichen Empfänger mehrfach denselben Zufall ${\displaystyle r}$ 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 ${\displaystyle m_{0},(c_{0},c_{1})}$ das dem Angreifer bekannte Klartext-Chiffrat-Paar und ${\displaystyle (c_{0}',c_{1}')}$ ein weiteres Chiffrat mit demselben Zufall. In diesem Fall gilt ${\displaystyle c_{0}=c_{0}'}$ und ${\textstyle {\frac {c_{1}'\cdot m_{0}}{c_{1}}}={\frac {\left(g^{ar}\cdot m_{1}\right)\cdot m_{0}}{g^{ar}\cdot m_{0}}}=m_{1}}$. 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: ${\textstyle {\frac {c_{1}}{c_{1}'}}={\frac {g^{ar}\cdot m_{0}}{g^{ar}\cdot m_{1}}}={\frac {m_{0}}{m_{1}}}}$

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 ${\displaystyle g^{ar}}$ ununterscheidbar von Zufall ist, selbst wenn ${\displaystyle g^{a}}$ und ${\displaystyle g^{r}}$ 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.

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

Für jeden Teiler ${\displaystyle n}$ der Gruppenordnung ${\displaystyle q}$, existiert eine Untergruppe von ${\displaystyle \mathbb {G} }$ mit der Ordnung ${\displaystyle n}$. Ein Element ${\displaystyle h\in \mathbb {G} }$ ist genau dann ein Element dieser Untergruppe, falls ${\displaystyle h^{n}=1}$, 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 ${\displaystyle g^{a}}$ und das erste Element eines Chiffrats ${\displaystyle g^{r}}$ Erzeuger der gesamten Gruppe ${\displaystyle \mathbb {G} }$. In diesem Fall offenbart das Chiffrat für alle bekannten Faktoren von ${\displaystyle q}$, 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 ${\displaystyle p}$ als Modulus verwendet wird. Da 0 kein Element der multiplikativen Gruppe ist, ist die Gruppenordnung in diesem Fall ${\displaystyle p-1}$. 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 ${\displaystyle p}$ 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[3]

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 ${\displaystyle a}$ wählt, sodass sein öffentlicher Schlüssel ${\displaystyle g^{a}}$ nur eine sehr kleine Untergruppe erzeugt, so wird auch die durch den Verschlüsselungszufall erzeugte „Maske“ ${\displaystyle \left[g^{a}\right]^{r}}$ 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 ${\displaystyle \mathbb {G} =\mathbb {Z} _{13}^{\times }}$ mit Erzeuger ${\displaystyle g=2}$.
2. Der Empfänger wählt ${\displaystyle a=4}$ und berechnet ${\displaystyle A\equiv 2^{4}\equiv 3\mod 13}$ als seinen öffentlichen Schlüssel

Allerdings gilt

${\displaystyle \langle 3\rangle =\lbrace 1,3,9\rbrace }$

bzw. ${\displaystyle 3^{3}\equiv 1\mod 13}$. D.h. ${\displaystyle 3}$ erzeugt die Untergruppe der Ordnung 3. Denn nach dem Hauptsatz über endlich erzeugte abelsche Gruppen zerfällt ${\displaystyle \mathbb {G} }$ gemäß

${\displaystyle \mathbb {Z} _{13}^{\times }\cong \mathbb {Z} _{3}^{+}\times \mathbb {Z} _{4}^{+}}$

Die Folge hiervon ist, dass der Sender den Klartext ${\displaystyle m}$ nur noch mit einem von drei Gruppenelementen ${\displaystyle \lbrace 1,3,9\rbrace }$ multipliziert, egal welcher Exponent ${\displaystyle k}$ gewählt wird. Insbesondere ist in einem von drei Fällen das Chiffrat identisch zum Klartext.

Hat ${\displaystyle p-1}$ keine großen Faktoren, lässt sich dieser Angriff sogar auf alle Elemente von ${\displaystyle \mathbb {G} }$ 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).