Elgamal-Verschlüsselungsverfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Der Empfänger wählt eine endliche, zyklische Gruppe der Ordnung mit Erzeuger . Die Parameter werden öffentlich gemacht.

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

Schlüsselerzeugung[Bearbeiten | Quelltext bearbeiten]

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

Verschlüsselung[Bearbeiten | Quelltext bearbeiten]

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

Entschlüsselung[Bearbeiten | Quelltext bearbeiten]

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

Denn es gilt:

Ein konkretes Beispiel[Bearbeiten | Quelltext bearbeiten]

Als Wahl für die endliche, zyklische Gruppe haben sich zwei Varianten durchgesetzt. Entweder wird für die multiplikative Einheitengruppe, also mit prim, oder die Menge der -rationalen Punkte einer elliptischen Kurve über gewählt. Aufgrund der besseren Anschaulichkeit wird hier ein Beispiel für die erste Variante mit (unrealistisch) kleinem gewählt.

Für prim ist ein Körper und die Elemente der Einheitengruppe sind alle Zahlen ungleich Null, also . Die Ordnung der Gruppe ist daher . Wie im Abschnitt "Vermeidung von kleinen (Unter-)Gruppen" beschrieben, verlangt die Sicherheit, dass die Gruppenordnung nicht wiederum in viele kleine Teiler zerfällt. Wegen prim, lässt sich als Teiler von nicht vermeiden. Daher wird zumindest so gewählt, dass mit wiederum prim gilt (vgl. Sophie-Germain-Primzahl).

Konkret ergibt sich dann folgender Ablauf:

Parametererzeugung[Bearbeiten | Quelltext bearbeiten]

Der Empfänger wählt und als Erzeuger. (Wegen hat nur zwei Untergruppen.) Er veröffentlicht die Parameter , durch welche die Gruppe festgelegt ist.

Schlüsselerzeugung[Bearbeiten | Quelltext bearbeiten]

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

Verschlüsselung[Bearbeiten | Quelltext bearbeiten]

  1. Der Sender möchte die Nachricht versenden.
  2. Der Sender wählt zufällig die Zahl .
  3. Der Sender berechnet das Gruppenelement .
  4. Der Sender berechnet das Chiffrat .
  5. Der Sender versendet an den Empfänger.

Entschlüsselung[Bearbeiten | Quelltext bearbeiten]

  1. Der Empfänger berechnet .

Sicherheit[Bearbeiten | Quelltext bearbeiten]

Theoretische Sicherheit[Bearbeiten | Quelltext bearbeiten]

Unter einer Sicherheitsprimitive versteht man in der Kryptografie ein gut untersuchtes, mathematisches Standardproblem, das allgemein als "schwer" akzeptiert wird. Lässt sich zeigen, dass das Brechen eines Kryptografieverfahrens äquivalent zum Lösen eines dieser Sicherheitsprimitiven ist, so ist sichergestellt, dass dieses mindestens genauso schwer ist. Die Sicherheit von Elgamal hängt eng mit mehreren mathematischen Standardproblemen zusammen.

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

Das Lösen des Diffie-Hellman-Problems (CDH) ist äquivalent zum Invertieren der Elgamal-Verschlüsselung. Das bedeutet, dass jeder, der mit einer gewissen Wahrscheinlichkeit zu einem beliebigen Elgamal-Chiffrat den zugehörigen Klartext finden kann, mit der gleichen Wahrscheinlichkeit CDH lösen, also zu bekanntem und das Gruppenelement bestimmen kann. Im Unterschied zum Diskreten-Logarithmus-Problems ist nicht gefordert, die Exponenten zu bestimmen. Es genügt bestimmen zu können um die Nachricht zu entschlüsseln.

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

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

Praktische Sicherheit[Bearbeiten | Quelltext bearbeiten]

Auch wenn Elgamal theoretisch sicher ist, gilt diese Aussage nur für den allgemeinen Fall, das heißt ein beliebiges Elgamal-Problem. Durch schlechte Wahl der Parameter oder Fehler in der Implementierung können Spezialfälle erzeugt werden, die dennoch unsicher sind.

Vermeidung der mehrfachen Verwendung des gleichen Multiplikators[Bearbeiten | Quelltext bearbeiten]

Aus Effizienzgründen könnte der Sender auf die Idee kommen, für mehrere Nachrichten an den gleichen Empfänger dieselben zu verwenden. In diesem Fall wäre die (aufwendige) Exponentiation in der Gruppe nur einmal notwendig und es würde eine (einfache) Multiplikation pro Nachricht verbleiben. Dies ist jedoch aus Sicherheitsgründen nicht zu empfehlen, weil es einem Angreifer dadurch möglich wäre, mit einem einmal gefundenen Klartext-Chiffrat-Paar alle vorherigen und nachfolgenden Nachrichten zu entschlüsseln. Dies hängt damit zusammen, dass sich bei bekanntem und nach auflösen lässt. Daraus folgt wiederum, dass zu umgestellt werden kann und da öffentlich ist, sich die Nachricht bestimmen lässt (siehe Known-Plaintext-Angriff).

Vermeidung von kleinen (Unter-)Gruppen[Bearbeiten | Quelltext bearbeiten]

Die Sicherheit von Elgamal beruht darauf, dass es in einer beliebigen zyklischen Gruppe schwierig ist, zu gegebenem den Exponenten mit zu bestimmen. Insbesondere muss also sichergestellt werden, dass nicht zu klein ist, ansonsten könnte der Exponent durch einfaches Aufzählen bestimmt werden. Dieses Problem tritt jedoch auch dann auf, wenn selbst zwar groß ist, aber in viele kleine Untergruppen zerfällt. Nach dem Hauptsatz über endlich erzeugte abelsche Gruppen kann jede endliche, abelsche Gruppe (und zyklische Gruppen sind abelsch) in die direkte Summe von -Untergruppen zerlegt werden, wobei ein Primteiler der Gruppenordnung von ist. Optimalerweise würde man also eine Gruppe wählen, deren Gruppenordnung selbst prim ist. Ansonsten besteht die Gefahr, dass der Empfänger bei der Schlüsselerzeugung einen Index wählt, sodass sein öffentlicher Schlüssel kein Erzeuger mehr von ist, sondern nur noch von einer kleinen Untergruppe von .

Für den schlechten Fall sei an dieser Stelle ein kleines Beispiel gegeben:

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

Allerdings gilt

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

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

Literatur[Bearbeiten | Quelltext bearbeiten]