Elgamal-Verschlüsselungsverfahren - LinkFang.de





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.

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 [math]G = \langle g \rangle[/math] der Ordnung [math]p[/math] mit Erzeuger [math]g[/math]. Die Parameter [math](G, g)[/math] 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

  1. Der Empfänger wählt zufällig eine Zahl [math]a \in \lbrace 1, \dots, p - 1 \rbrace[/math] mit [math]\operatorname{ggT}(a, p) = 1[/math]. Dies ist der private Schlüssel des Empfängers.
  2. Der Empfänger berechnet das Gruppenelement [math]A = g^a \in G[/math] als seinen öffentlichen Schlüssel und gibt diesen bekannt.

Verschlüsselung

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

Entschlüsselung

  1. Der Empfänger berechnet [math]R^{-a}\cdot c \in G[/math]. (Man beachte: [math]a[/math] ist der private Schlüssel des Empfängers und nur ihm bekannt.)
  2. Bei [math]G=( \Z / p \Z )[/math] gilt [math]R^{p-1-a}\cdot c \in G[/math]

Denn es gilt:

[math]R^{-a}\cdot c = g^{-ra} \cdot A^r \cdot m = \underbrace{g^{-ra} \cdot g^{ar}}_{=1 \in G} \cdot m = m[/math]

Ein konkretes Beispiel

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

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

Konkret ergibt sich dann folgender Ablauf:

Parametererzeugung

Der Empfänger wählt [math]G=( \Z / 23 \Z )^\times[/math] und [math]g=7[/math] als Erzeuger. (Wegen [math]23 - 1 = 2 \cdot 11[/math] hat [math]G[/math] nur zwei Untergruppen.) Er veröffentlicht die Parameter [math](p, g) = (23, 7)[/math], durch welche die Gruppe festgelegt ist.

Schlüsselerzeugung

  1. Der Empfänger wählt zufällig eine Zahl [math]a = 5[/math]. Dies ist der private Schlüssel des Empfängers.
  2. Der Empfänger berechnet das Gruppenelement [math]A = g^a = 7^5 \equiv 17 \mod 23[/math] als seinen öffentlichen Schlüssel und gibt diesen bekannt.

Verschlüsselung

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

Entschlüsselung

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

Sicherheit

Theoretische Sicherheit

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 [math]a[/math] aus dem öffentlichen Schlüssel [math]A=g^a \in G[/math] 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 [math]A = g^a \in G[/math] und [math]R = g^r \in G[/math] das Gruppenelement [math]g^{ar} \in G[/math] bestimmen kann. Im Unterschied zum Diskreten-Logarithmus-Problems ist nicht gefordert, die Exponenten [math]a,r[/math] zu bestimmen. Es genügt [math]g^{ar}[/math] 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

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

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

Vermeidung von kleinen (Unter-)Gruppen

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

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

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

Allerdings gilt

[math]\langle 3 \rangle = \lbrace 1, 3, 9 \rbrace[/math]

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

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

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

Literatur


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Elgamal-Verschlüsselungsverfahren (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.