Elgamal-Verschlüsselungsverfahren

Taher Elgamal (2010), Erfinder des Verfahrens

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.

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 $\mathbb {G} =\langle g\rangle$ mit primer Ordnung $q$ und Erzeuger $g$, so dass $q$ groß genug ist um die gewünschte Sicherheit zu bieten. $\mathbb {G}$ wird veröffentlicht.

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

Schlüsselerzeugung

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

Verschlüsselung

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

Entschlüsselung

1. Der Empfänger berechnet den Klartext $m$ als $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: $a$ ist der private Schlüssel des Empfängers und nur ihm bekannt.)

Gruppenwahl

Als Wahl für die endliche, zyklische Gruppe $\mathbb {G}$ 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 $p$ prim ist $\mathbb {Z} /p\mathbb {Z}$ ein Körper (genauer: Restklassenkörper) und die Elemente der Einheitengruppe (also der „multiplikativen“ Gruppe des Selben) sind alle Zahlen ungleich Null, konkret $G=\lbrace 1,\dots ,p-1\rbrace$. Die Ordnung der Gruppe ist daher $p-1$. Da $p$ prim ist, ist $p-1$ aber durch Zwei teilbar und die Einheitengruppe somit für $p>3$ keine Gruppe primer Ordnung. Sei nun $q$ ein Teiler von $p-1$, dann besitzt die Einheitengruppe eine Untergruppe mit Ordnung $q$. Handelt es sich bei $q$ um eine Primzahl, besitzt diese Untergruppe somit prime Ordnung und ist für die Verwendung potentiell geeignet. In der Praxis hat sich etabliert $p$ so zu wählen, dass ${\textstyle {\frac {p-1}{2}}=q}$ geeignet ist. $p$ wird dann als sichere Primzahl, $q$ 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h^2} mit einem anderen Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 2q+1} : Für alle ganzen Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} (inklusive) und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} (exklusiv) gilt, dass entweder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p-n} Teil der Untergruppe primer Ordnung ist, so dass einfach das funktionierende Element benutzt werden kann.

Ein konkretes Beispiel

Die hier als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}} verwendete Untergruppe der Quadrate von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Z_{23}^\times}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \times}	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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^x}	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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=\Z_{23}^\times} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g=2} als Erzeuger, so dass gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle g\rangle = \mathbb{G} \subset G} . 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 5 \cdot 5 \equiv 2 \pmod {23}} ist, ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2} ein quadratischer Rest und folglich Teil der Untergruppe. Da für alle Elemente außer dem Neutralelement (hier: „Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} “) in Gruppen primer Ordnung gilt, dass sie die gesamte Gruppe Erzeugen, hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2} selbst prime Ordnung und ist damit ein geeigneter Erzeuger.

Das Rechnen mit Elementen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Z_{23}^\times} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}} nur 11 Elemente enthält und nicht etwa 22 oder 23.

Das Berechnen von Potenzen funktioniert analog zur normalen Potenzrechnung, so gilt etwa Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^3 = g\cdot g\cdot g} . 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} hat. Da somit für alle Gruppenelemente Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h} gilt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h^q = 1 = h^0} und damit für alle Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} gilt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h^{q+x} = 1 \cdot h^x = h^x} , ist es zur Berechnung beliebiger Potenzen ausreichend die Potenz zum Exponenten modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=11} zu rechnen. So gilt zum Beispiel: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{27} = 2^{2\cdot 11 + 5} \equiv 2^5 \equiv 9} . (Siehe die zweite Tabelle für die Potenzen aller Elemente von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}} .)

Schlüsselerzeugung

1. Der Empfänger zieht einen zufälligen Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a := 5} . Dies ist der private Schlüssel des Empfängers.
2. Der Empfänger berechnet das Gruppenelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^a = 2^5 \equiv 9 \mod 23} als seinen öffentlichen Schlüssel und gibt diesen bekannt.

Verschlüsselung

1. Der Sender möchte die Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m = 8} versenden. (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 8 \in \mathbb{G}} wegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 13^2 = 169 \equiv 8 \mod 23} .)
2. Der Sender zieht einen zufälligen Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r = 7} .
3. Der Sender berechnet das Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} wie folgt:
   • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_0 := g^r = 2^7 \equiv 13 \mod 23} .
   • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_1 := \left[g^a\right]^r\cdot m = 9^7 \cdot 8 \equiv 9 \mod 23} .
   • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c := (c_0, c_1) = (13, 9)}
4. Der Sender sendet das Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} an den Empfänger.

Entschlüsselung

1. Der Empfänger berechnet den Klartext Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} wie folgt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (c_0)^a} nötig ist, diese aber durch einfache Subtraktion des geheimen Schlüssels (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ) von der Gruppenordnung (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} ) ohne Mehraufwand gemeinsam mit der ohnehin nötigen Potenzierung durchgeführt werden kann: Da das Addieren oder Subtrahieren von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} im Exponenten keine Auswirkung auf das Ergebnis hat, können so negative Exponenten (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -a} ) durch positive (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q-a} ) ersetzt werden. Im Beispiel also: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 13^{-5} \equiv 13^{11-5} = 13^6\mod 23} .

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} beschränkt ist (= er ist effizient) und dessen Erfolgswahrscheinlichkeit relativ zum Logarithmus der Gruppenordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} aus dem öffentlichen Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (g, g^x, g^y) \in \mathbb{G}^3} das Gruppenelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^{xy} \in \mathbb{G}} zu finden. Im Unterschied zum Diskreten-Logarithmus-Problems ist nicht gefordert, die Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x,y} zu bestimmen. Es genügt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}, (g^x, g^y) \in \mathbb{G}^2} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} unbekannt vom CDH-Herausforderer.
2. Ziehe einen zufälligen Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r \leftarrow \Z_q} .
3. Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m\in\mathbb{G}} .
5. Berechne Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h := g^r \cdot m^{-1}}
6. Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} ausgeben, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^{r} = g^{xy}\cdot m} , womit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x, y, z \leftarrow \mathbb{Z}_p} in der Lage ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^x, g^y, g^{xy} \in \mathbb{G}} signifikant besser von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}, (g^x, g^y, g^z) \in \mathbb{G}^3} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x,y,z} unbekannt vom DDH-Herausforderer.
2. Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_0, m_1 \in\mathbb{G}} .
4. Ziehe eine zufälliges Bit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b \leftarrow \mathbb{B}} .
5. Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c:=(g^y, g^z\cdot m_b)} als Chiffrat an den IND-CPA-Angreifer.
6. Erhalte ein bit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b' \in \mathbb{B}} vom IND-CPA-Angreifer.
7. Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b'' := (b = b')} an den DDH-Herausforderer

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

• Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle xy = z} , so ist die IND-CPA-Simulation perfekt. Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \frac{1}{2}+\epsilon} richtig. Dieser Fall tritt mit Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \frac{1}{2}} ein.
• Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle xy \neq z} ist, dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} ein Chiffrat von Zufall. Der IND-CPA-Angreifer kann in diesem Fall inhärent keine bessere Strategie als raten haben, womit er Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} mit der Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \frac{1}{2}} richtig. Dieser Fall tritt insgesamt betrachtet mit einer Wahrscheinlichkeit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \frac{1}{2}} ein.

Man beachte, dass im letzteren Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle c} zwar durch reinen Zufall mit einer Wahrscheinlichkeit von je Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \frac{1}{|\mathbb{G}|}} eine Verschlüsselung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle m_0} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \epsilon} nicht vernachlässigbar und damit auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \frac{\epsilon}{2}} . Da die Laufzeit des Simulators klar polynomiell in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \leftarrow \Z_q} und übergibt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^x} an den Angreifer.
• Der Angreifer darf (polynomiell oft) ein Gruppenelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h \in \mathbb{G}} an den Herausforderer übergeben, der mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h^x} antwortet.
• Der Herausforderer zieht ein zufälliges Bit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b \in \mathbb{B}} und zwei zufällige Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y, z \in \Z_q} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle xy \neq z} . Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b=0} übergibt er dem Angreifer das Tupel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^y, g^z} , ansonsten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^{y}, g^{x\cdot y}} .
• Der Angreifer antwortet mit einem Bit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b' \in \mathbb{B}} und gewinnt genau dann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}, g^x \in \mathbb{G}} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} unbekannt vom DDH^CSDH-Herausforderer. (Unterschied zum DDH-Beweis: Der Simulator erhält noch kein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^y} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^z} .)
2. Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^a, g^b} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a,b} unbekannt vom IND-CCA1-Angreifer.
   • Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^a} als Orakel-Anfrage an den DDH^CSDH-Herausforderer.
   • Erhalte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^{xa}} vom DDH^CSDH-Herausforderer.
   • Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^b \cdot \left[g^{xa}\right]^{-1}} an den IND-CCA1-Angreifer
4. Erhalte vom IND-CCA1-Angreifer zwei verschiedene Klartexte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_0, m_1 \in\mathbb{G}} .
5. Erhalte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^y, g^z \in \mathbb{G}^2} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b \leftarrow \mathbb{B}} .
7. Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c:=(g^y, g^z\cdot m_b)} als Chiffrat an den IND-CCA1-Angreifer.
8. Erhalte ein bit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b' \in \mathbb{B}} vom IND-CPA-Angreifer.
9. Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c, c'} Chiffrate der Klartexte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m, m'} mit den Verschlüsselungszufällen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r, r'} für den Öffentlichen Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m \cdot m'} verknüpft werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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)}

Rerandomisierbarkeit

Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c =: (c_0,\ c_1)} ein Chiffrat eines Klartextes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} mit Verschlüsselungszufall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} für den Öffentlichen Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left[g^a\right]} . Dann kann ohne Kenntnis des geheimen Schlüssels ein Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c'} mit demselben Klartext berechnet werden, dem dies auch im direkten Vergleich nicht angesehen werden kann. Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r'} ein frisch zufällig gewählter Exponent:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

Ununterscheidbarkeit von Empfängern

ElGamal-Chiffrat bieten Anonymität in dem Sinne, dass einem Chiffrat, selbst bei vom Angreifer gewähltem Klartext, nicht angesehen werden, 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} .
3. Der Herausforderer wählt zufällig einen der beiden öffentlichen Schlüssel, verschlüsselt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

Beweis

Der Beweis erfolgt erneut durch Reduktion mit dem folgenden Simulator:

1. Erhalte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}, (g^x, g^y, g^z) \in \mathbb{G}^3} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x,y,z} unbekannt vom DDH-Herausforderer.
2. Ziehe ein zufälliges Bit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b \leftarrow \mathbb{B}} und ein zufälliges Gruppenelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h \leftarrow \mathbb{G}} .
3. Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b = 0} übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^x, h} an den Angreifer, ansonsten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h, g^x} .
4. Erhalte einen Klartext Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m\in\mathbb{G}} vom Angreifer.
5. Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (g^y, g^z\cdot m)} an den Angreifer
6. Erhalte ein bit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b' \in \mathbb{B}} vom Angreifer.
7. Übergebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle xy \neq z} , dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (g^y, g^z)} mit überwältigender Wahrscheinlichkeit für keinen der beiden öffentlichen Schlüssel ein Chiffrat von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} mit der Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \frac{1}{2}} richtig.
• Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle xy = z} , so ist die Simulation perfekt. Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \frac{1}{2}+\epsilon} richtig.

Da beide Fälle mit Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \frac{1}{2}} auftreten, ergibt sich für die Erfolgswahrscheinlichkeit des Simulators im DDH-Spiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \epsilon} nicht vernachlässigbar und damit auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

Verschlüsseln für mehrere Empfänger

Es seien Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^y = g^{x_0 + x_1} = g^{x_0} \cdot g^{x_1}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c = (c_0,\ c_1) = (g^r,\ g^{yr} \cdot m)} ein Chiffrat von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} mit Verschlüsselungszufall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} . Beide Parteien können nun Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^{-r \cdot x_0}} beziehungsweise Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^{-r \cdot x_1}} berechnen. Werden diese Werte nun in beliebiger Reihenfolge mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_1} multipliziert, so ergibt sich: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_0} ein reguläres Chiffrat für den öffentlichen Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^{x_1}} mit Zufall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c =: (c_0,\ c_1) =: \left(g^r, g^{rx}\cdot m\right)} ein Chiffrat eines Klartextes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} mit Verschlüsselungszufall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} für den Öffentlichen Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left[g^a\right]} . Ferner sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^y} ein weiterer öffentlicher Schlüssel, zu dem der private Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} gehört. Eine Partei die diesen privaten Schlüssel und das Chiffrat kennt, kann nun Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left[g^r\right]^y = g^{ry}} berechnen und dies mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_1} multiplizieren, was ihr das Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_0, m_1, \dots} an den gleichen Empfänger mehrfach denselben Zufall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_0, (c_0, c_1)} das dem Angreifer bekannte Klartext-Chiffrat-Paar und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (c_0', c_1')} ein weiteres Chiffrat mit demselben Zufall. In diesem Fall gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_0 = c_0'} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^{ar}} ununterscheidbar von Zufall ist, selbst wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}} prim ist, so dass die triviale Gruppe die einzige echte Untergruppe von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}} ist. Ist dem nicht so, kann dies fatale Folgen haben:

Für jeden Teiler Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} der Gruppenordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} , existiert eine Untergruppe von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}} mit der Ordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} . Ein Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h \in \mathbb{G}} ist genau dann ein Element dieser Untergruppe, falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^a} und das erste Element eines Chiffrats Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^r} Erzeuger der gesamten Gruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}} . In diesem Fall offenbart das Chiffrat für alle bekannten Faktoren von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} als Modulus verwendet wird. Da 0 kein Element der multiplikativen Gruppe ist, ist die Gruppenordnung in diesem Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} wählt, sodass sein öffentlicher Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g^a} nur eine sehr kleine Untergruppe erzeugt, so wird auch die durch den Verschlüsselungszufall erzeugte „Maske“ Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G} = \Z_{13}^\times} mit Erzeuger Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g=2} .
2. Der Empfänger wählt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a=4} und berechnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \equiv 2^4 \equiv 3 \mod 13} als seinen öffentlichen Schlüssel

Allerdings gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle 3 \rangle = \lbrace 1, 3, 9 \rbrace}

bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3^3 \equiv 1 \mod 13} . D.h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3} erzeugt die Untergruppe der Ordnung 3. Denn nach dem Hauptsatz über endlich erzeugte abelsche Gruppen zerfällt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{G}} gemäß

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Z_{13}^\times \cong \Z_3^+ \times \Z_4^+}

Die Folge hiervon ist, dass der Sender den Klartext Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} nur noch mit einem von drei Gruppenelementen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lbrace 1, 3, 9 \rbrace} multipliziert, egal welcher Exponent Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} gewählt wird. Insbesondere ist in einem von drei Fällen das Chiffrat identisch zum Klartext.

Hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p-1} keine großen Faktoren, lässt sich dieser Angriff sogar auf alle Elemente von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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).

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'.