Hauptmenü öffnen

Wikipedia β

Elgamal-Verschlüsselungsverfahren

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

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

Inhaltsverzeichnis

BeschreibungBearbeiten

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.

ParametererzeugungBearbeiten

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üsselerzeugungBearbeiten

  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üsselungBearbeiten

  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üsselungBearbeiten

  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 BeispielBearbeiten

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:

ParametererzeugungBearbeiten

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üsselerzeugungBearbeiten

  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üsselungBearbeiten

  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üsselungBearbeiten

  1. Der Empfänger berechnet  .

SicherheitBearbeiten

Theoretische SicherheitBearbeiten

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 SicherheitBearbeiten

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 MultiplikatorsBearbeiten

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-)GruppenBearbeiten

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.

LiteraturBearbeiten