mini|Taher Elgamal (2010), Erfinder des Verfahrens

Das Elgamal-Verschlüsselungsverfahren oder Elgamal-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 mit primer Ordnung und Erzeuger , so dass groß genug ist um die gewünschte Sicherheit zu bieten. wird veröffentlicht.

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

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

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

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

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

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

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

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

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

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

Ein konkretes Beispiel + Die hier als verwendete Untergruppe der Quadrate von 1 2 3 4 6 8 9 12 13 16 18 1 1 2 3 4 6 8 9 12 13 16 18 2 2 4 6 8 12 16 18 1 3 9 13 3 3 6 9 12 18 1 4 13 16 2 8 4 4 8 12 16 1 9 13 2 6 18 3 6 6 12 18 1 13 2 8 3 9 4 16 8 8 16 1 9 2 18 3 4 12 13 6 9 9 18 4 13 8 3 12 16 2 6 1 12 12 1 13 2 3 4 16 6 18 8 9 13 13 3 16 6 9 12 2 18 8 1 4 16 16 9 2 18 4 13 6 8 1 3 12 18 18 13 8 3 16 6 1 9 4 12 2

+ Die Potenzen der Elemente in 0 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 4 8 16 9 18 13 3 6 12 3 1 3 9 4 12 13 16 2 6 18 8 4 1 4 16 18 3 12 2 8 9 13 6 6 1 6 13 9 8 2 12 3 18 16 4 8 1 8 18 6 2 16 13 12 4 9 3 9 1 9 12 16 6 8 3 4 13 2 18 12 1 12 6 3 13 18 9 16 8 4 2 13 1 13 8 12 18 4 6 9 2 3 16 16 1 16 3 2 9 6 4 18 12 8 13 18 1 18 2 13 4 3 8 6 16 12 9

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

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

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

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

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

Verschlüsselung Der Sender möchte die Nachricht versenden. ( wegen .) Der Sender zieht einen zufälligen Exponenten . Der Sender berechnet das Chiffrat wie folgt: . .

Der Sender sendet das Chiffrat an den Empfänger.

Entschlüsselung Der Empfänger berechnet den Klartext wie folgt: .

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

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

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

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

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

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

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