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]

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 eine Schlüsselpaar aus öffentlichen und privaten Schlüssel 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]

Der Empfänger wählt eine endliche, zyklische Gruppe G = \langle g \rangle mit Erzeuger g.

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

Schlüsselerzeugung[Bearbeiten]

  1. Der Empfänger wählt zufällig eine Zahl j \in \lbrace 0, \dots, \left\vert G \right\vert - 1 \rbrace mit \operatorname{ggT} \left( j, \left\vert G \right\vert \right) = 1. Dies ist der private Schlüssel des Empfängers.
  2. Der Empfänger berechnet das Gruppenelement h = g^j \in G als seinen öffentlichen Schlüssel.
  3. Der Empfänger gibt \left( G, g, h \right) bekannt.

Verschlüsselung[Bearbeiten]

  1. Der Sender möchte die Nachricht m \in G versenden.
  2. Der Sender wählt zufällig eine Zahl k \in \lbrace 0, \dots, \left\vert G \right\vert - 1 \rbrace mit \operatorname{ggT} \left( k, \left\vert G \right\vert \right) = 1.
  3. Der Sender berechnet das Gruppenelement f = g^k \in G.
  4. Der Sender berechnet das Chiffrat c = h^k \cdot m \in G. (Man beachte: Der Sender kennt den öffentlichen Schlüssel h des Empfängers.)
  5. Der Sender versendet \left( f, c \right) an den Empfänger.

Entschlüsselung[Bearbeiten]

  1. Der Empfänger berechnet f^{-j}\cdot c \in G. (Man beachte: j ist der private Schlüssel des Empfängers und nur ihm bekannt.)

Denn es gilt:

f^{-j}\cdot c = g^{-kj} \cdot h^k \cdot m = \underbrace{g^{-kj} \cdot g^{jk}}_{=1 \in G} \cdot m = m

Ein konkretes Beispiel[Bearbeiten]

Als Wahl für die endliche, zyklische Gruppe G haben sich zwei Varianten durchgesetzt. Entweder wird für G die multiplikative Einheitengruppe, also G=( \Z / p \Z )^\times mit p prim, oder die Menge der q-rationalen Punkte einer elliptischen Kurve über \mathbb{F}_q gewählt. Aufgrund der besseren Anschaulichkeit wird hier ein Beispiel für die erste Variante mit (unrealistisch) kleinem p gewählt.

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

Konkret ergibt sich dann folgender Ablauf:

Parametererzeugung[Bearbeiten]

Der Empfänger wählt G=( \Z / 23 \Z )^\times und g=7 als Erzeuger. (Wegen 23 - 1 = 2 \cdot 11 hat G nur zwei Untergruppen.)

Schlüsselerzeugung[Bearbeiten]

  1. Der Empfänger wählt zufällig eine Zahl j = 5. Dies ist der privater Schlüssel des Empfängers.
  2. Der Empfänger berechnet das Gruppenelement h \equiv 7^5 \equiv 17 \mod 23 als seinen öffentlichen Schlüssel.
  3. Der Empfänger gibt (G, g, h) = (( \Z / 23 \Z )^\times, 7, 17) bekannt.

Verschlüsselung[Bearbeiten]

  1. Der Sender möchte die Nachricht m = 8 versenden.
  2. Der Sender wählt zufällig die Zahl k = 3.
  3. Der Sender berechnet das Gruppenelement f \equiv 7^3 \equiv 21 \mod 23.
  4. Der Sender berechnet das Chiffrat c \equiv 17^3 \cdot 8 \equiv 20 \mod 23.
  5. Der Sender versendet \left( 21, 20 \right) an den Empfänger.

Entschlüsselung[Bearbeiten]

  1. Der Empfänger berechnet m \equiv 21^{-5}\cdot 20 \equiv 8 \mod 23.

Sicherheit[Bearbeiten]

Theoretische Sicherheit[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 j aus dem öffentlichen Schlüssel h=g^j \in G 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 h = g^j \in G und f = g^k \in G das Gruppenelement g^{jk} \in G bestimmen kann. Im Unterschied zum Diskreten-Logarithmus-Problems ist nicht gefordert, die Exponenten j,k zu bestimmen. Es genügt g^{jk} 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]

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]

Aus Effizienzgründen könnte der Sender auf die Idee kommen, für mehrere Nachrichten m_1, m_2, \dots an den gleichen Empfänger dieselben k,f,h^k zu verwenden. In diesem Fall wäre die (aufwendige) Exponentation 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 gefundenem Klartext-Chiffrat-Paar \left( m_1, c_1 \right) alle vorherigen und nachfolgenden Nachrichten zu entschlüsseln. Dies hängt damit zusammen, dass sich c_1= h^k \cdot m_1 bei bekanntem m_1 und c_1 nach h^{-k} = c_1^{-1}\cdot m_1 auflösen lässt. Daraus folgt wiederum, dass c_2=h^k \cdot m_2 zu c_2 \cdot h^{-k} = m_2 umgestellt werden kann und da c_2 öffentlich ist, sich die Nachricht m_2 bestimmen lässt (siehe Known-Plaintext-Angriff).

Vermeidung von kleinen (Unter-)Gruppen[Bearbeiten]

Die Sicherheit von Elgamal beruht darauf, dass es in einer beliebigen zyklischen Gruppe G = \langle g \rangle schwierig ist, zu gegeben h \in G den Exponenten j mit h=g^j zu bestimmen. Insbesondere muss also sichergestellt werden, dass G nicht zu klein ist, ansonsten könnte der Exponent durch einfaches Aufzählen bestimmt werden. Dieses Problem tritt jedoch auch dann auf, wenn G selbst zwar groß ist, aber in vielen 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 p-Untergruppen zerlegt werden, wobei p ein Primteiler der Gruppenordnung von G ist. Optimalerweise würde man also eine Gruppe G wählen, deren Gruppenordnung selbst prim ist. Ansonsten besteht die Gefahr, dass der Empfänger bei der Schlüsselerzeugung einen Index j wählt, sodass sein öffentlicher Schlüssel h=g^j kein Erzeuger mehr von G ist, sondern nur noch von einer kleinen Untergruppe von G.

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

  1. Der Empfänger wählt die Gruppe G = \left( \Z / 13\Z \right)^\times mit Erzeuger g=2.
  2. Der Empfänger wählt j=4 und berechnet h \equiv 2^4 \equiv 3 \mod 13 als seinen öffentlichen Schlüssel

Allerdings gilt

\langle 3 \rangle = \lbrace 1, 3, 9 \rbrace

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

\left( \left( \Z / 13\Z \right)^\times, \cdot \right) \cong \left( \Z / 3\Z,+ \right) \times \left( \Z / 4\Z,+ \right)

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

Literatur[Bearbeiten]